零, 前言
链表是一种数据结构, 用来承载数据, 每个表节点装载一个数据元素
双链表是每个节点出来数据元素外还分别持有前, 后两个节点的引用
为了统一节点的操作, 一般在真实链表的首尾各加一个虚拟节点, 称为头节点和尾节点
一, 链表的操作
下图是一个三个节点的双链表
双链表. PNG
- /**
- * 作者: 张风捷特烈
- * 时间: 2018/9/18 0018:7:35
- * 邮箱: 1981462002@qq.com
- * 说明: 双链表
- */
- public class DoubleLink<T> {
- /**
- * 虚拟头结点
- */
- private Node headNode;
- /**
- * 虚拟尾节点
- */
- private Node tailNode;
- /**
- * 链表长度 (节点数)
- */
- private int size;
- /**
- * 节点类
- * @param <T>
- */
- private static class Node<T> {
- /**
- * 数据
- */
- public T data;
- /**
- * 前节点
- */
- public Node prev;
- /**
- * 后节点
- */
- public Node next;
- public Node(Node prev, Node next, T data) {
- this.data = data;
- this.prev = prev;
- this.next = next;
- }
- }
- }
1. 插入操作: addBefore()
假如在第二个元素处插入, 会发生什么:
1--- 新建一个 node, 将前, 后指向分别指向目标前节点和目标节点
2--- 目标前节点 next 指向新节点
3--- 目标节点 prev 指向新节点
3--- 链表长度 + 1
双链表前插入. PNG
- /**
- * 根据目标节点插入新节点
- * @param target 目标节点
- * @param data 新节点数据
- */
- private void addNodeBefore(Node<T> target, T data) {
- // 新建一个 node, 将前, 后指向分别指向目标前节点和目标节点
- Node<T> newNode = new Node<>(target.prev, target, data);
- // 目标前节点 next 指向新节点
- target.prev.next = newNode;
- // 目标节点 prev 指向新节点
- target.prev = newNode;
- // 链表长度 + 1
- size++;
- }
2. 移除操作: removeNode()
假如在删除第二个元素, 会发生什么:
1--- 目标前节点的 next 指向目标节点后节点
2--- 目标后节点的 prev 指向目标节点前节点
3--- 链表长度 - 1
4--- 返回删除的数据
双链表移除节点. PNG
- /**
- * 移除目标节点
- *
- * @param target 目标节点
- * @return 目标节点数据
- */
- private T removeNode(Node<T> target) {
- // 目标前节点的 next 指向目标节点后节点
- target.prev.next = target.next;
- // 目标后节点的 prev 指向目标节点前节点
- target.next.prev = target.prev;
- // 链表长度 - 1
- size--;
- return target.data;
- }
3. 清空操作: clearNode()
思路和删除一样: 首尾虚拟节点互指, 中间的元素就被孤立了, 从而从链表上全部删除
1--- 实例化头结点
2--- 实例化尾节点, 并将 prev 指向头
3--- 头结点的 next 指向尾节点
4--- 链表长度置零
双链表清空. PNG
- /**
- * 清空所有节点
- */
- private void clearNode() {
- // 实例化头结点
- headNode = new Node<T>(null, null, null);
- // 实例化尾节点, 并将 prev 指向头
- tailNode = new Node<T>(headNode, null, null);
- headNode.next = tailNode;
- // 链表长度置零
- size = 0;
- }
4. 获取操作: getNode
思路: 链表查找只能一个一个挨着找, 就像排队报数样.
为了尽量高效, 判断一下索引在前半还是后半, 来采取前报数, 还是后报数.
- /**
- * 根据索引获取节点
- *
- * @param index 索引
- * @return 索引处节点
- */
- private Node<T> getNode(int index) {
- // 声明目标节点
- Node<T> targetNode;
- // 索引越界处理
- if (index <0 || index> size - 1) {
- throw new IndexOutOfBoundsException();
- }
- // 如果索引在前半, 前序查找
- if (index <size / 2) {
- targetNode = headNode.next;
- for (int i = 0; i < index; i++) {
- targetNode = targetNode.next;
- }
- } else { // 如果索引在后半, 反序查找
- targetNode = tailNode.prev;
- for (int i = size - 1; i < index; i++) {
- targetNode = targetNode.prev;
- }
- }
- return targetNode;
- }
二, 利用链表实现对数据的操作
链表只是对节点的操作, 只是一种结构, 并非真正目的, 在集合类中要让链表对外完全不可见, 就像人的骨骼之于躯体
躯体的任何动作是骨骼以支撑, 而骨骼并不可见, 从外来看只是躯体的动作而已, 数据结构就是这样的骨架, 数据便是躯体.
我们需要的是按照这种结构对数据进行增删改查等操作, 并暴露接口由外方调用
1. 普通集合操作: 增删改查
- public class DoubleLinkedGroup<T> extends Group<T> {
- /**
- * 虚拟头结点
- */
- private Node headNode;
- /**
- * 虚拟尾节点
- */
- private Node tailNode;
- public DoubleLinkedGroup() {
- clear();
- }
- @Override
- public void add(int index, T el) {
- if (index <0 || index> size) {
- throw new IllegalArgumentException("Add failed. Illegal index");
- }
- addNodeBefore(getNode(index), el);
- }
- @Override
- public T remove(int index) {
- if (index <0 || index> size) {
- throw new IllegalArgumentException("Remove failed. Illegal index");
- }
- return removeNode(getNode(index));
- }
- @Override
- public void clear() {
- clearNode();
- }
- @Override
- public T set(int index, T el) {
- if (index <0 || index> size) {
- throw new IllegalArgumentException("Set failed. Illegal index");
- }
- Node<T> node = getNode(index);
- T oldData = node.el;
- node.el = el;
- return oldData;
- }
- @Override
- public T get(int index) {
- if (index <0 || index> size) {
- throw new IllegalArgumentException("Get failed. Illegal index");
- }
- return getNode(index).el;
- }
- @Override
- public void addLast(T el) {
- add(size, el);
- }
- }
2. 普通方法测试:
- private static void baseTest() {
- DoubleLinkedGroup<String> list = new DoubleLinkedGroup<>();
- // 添加测试
- list.addFirst("特");
- list.addFirst("张");
- list.add(1,"风");
- list.add(2,"捷");
- list.addLast("烈");
- // 输出测试
- System.out.println(list);
- //head: 张 -> 风 -> 捷 -> 特 -> 烈 ->null->
- // 移除测试
- list.remove(3);
- System.out.println(list);
- //head: 张 -> 风 -> 捷 -> 烈 ->null->
- // 修改测试
- list.set(2,"神");
- System.out.println(list);
- //head: 张 -> 风 -> 神 -> 烈 ->null->
- // 获取测试
- for (int i = 0; i <list.size(); i++) {
- System.out.print(list.get(i));// 张风神烈
- }
- // 大小测试
- System.out.println(list.size());//4
- // 是否为空测试
- System.out.println(list.isEmpty());//false
- // 清空测试
- list.clear();
- System.out.println(list.isEmpty());//true
- }
- }
二, 其他方法测试
定元素查询索引, 删除
两个双链表式集合定点连接
1. 代码实现
- @Override
- public int[] getIndex(T el) {
- // 临时数组
- int[] tempArray = new int[size];
- // 重复个数
- int index = 0;
- int count = 0;
- Node node = headNode.next;
- while (node != null) {
- if (el.equals(node.el)) {
- tempArray[index] = -1;
- count++;
- }
- index++;
- node = node.next;
- }
- // 将临时数组压缩
- int[] indexArray = new int[count];
- int indexCount = 0;
- for (int i = 0; i < tempArray.length; i++) {
- if (tempArray[i] == -1) {
- indexArray[indexCount] = i;
- indexCount++;
- }
- }
- return indexArray;
- }
- @Override
- public Group<T> contact(int index, Group<T> group) {
- if (index <0 || index> size) {
- throw new IllegalArgumentException("Contact failed. Illegal index");
- }
- DoubleLinkedGroup linkedGroup = (DoubleLinkedGroup) group;
- Node targetNode = getNode(index);
- Node targetNextNode = targetNode.next;
- // 目标节点的 next 指向待接链表的第一个节点
- targetNode.next = linkedGroup.getHeadNode().next;
- // 向待接链表的第一个节点的 prev 指向目标节点
- linkedGroup.getHeadNode().next.prev = targetNode;
- // 目标节点的下一节点指的 prev 向待接链表的最后一个节点
- targetNextNode.prev = linkedGroup.getTailNode().prev;
- // 向待接链表的最后一个节点的 next 指向目标节点的下一节点的
- linkedGroup.getTailNode().prev.next = targetNextNode;
- return this;
- }
- public Node getHeadNode() {
- return headNode;
- }
- public Node getTailNode() {
- return tailNode;
- }
2. 其他方法测试
- /**
- * 其他方法测试
- */
- private static void otherTest() {
- DoubleLinkedGroup<String> linkedGroup = new DoubleLinkedGroup<>();
- linkedGroup.addLast("a");
- linkedGroup.addLast("b");
- linkedGroup.addLast("a");
- linkedGroup.addLast("c");
- linkedGroup.addLast("a");
- System.out.println(linkedGroup);
- //head: a->b->a->c->a->null->
- // 获取 a 元素的所有索引位置
- int[] as = linkedGroup.getIndex("a");
- for (int a : as) {
- System.out.print(a + " ");//0 2 4
- }
- // 删除 a 元素第一次出现的地方 ---
- linkedGroup.removeEl("a");
- System.out.println(linkedGroup);
- //head: b->a->c->a->null->
- // 查看 a 元素是否存在
- boolean b = linkedGroup.contains("a");
- System.out.println(b);//true
- // 删除所有 a 元素出现的地方 ---
- linkedGroup.removeEls("a");
- System.out.println(linkedGroup);
- //head: b->c->NULL
- // 双链表合并测试
- DoubleLinkedGroup<String> linkedGroup2 = new DoubleLinkedGroup<>();
- linkedGroup2.addLast("1");
- linkedGroup2.addLast("3");
- linkedGroup2.addLast("2");
- linkedGroup.contact(0, linkedGroup2);
- System.out.println(linkedGroup);
- //head: b->1->3->2->c->null->
- }
后记,
1. 声明:
[1] 本文由张风捷特烈原创, 各图均由本人亲自所画, 转载请注明
[2] 欢迎广大编程爱好者共同交流
[3] 个人能力有限, 如有不正之处欢迎大家批评指证, 必定虚心改正
[4] 你的喜欢与支持将是我最大的动力
来源: http://www.jianshu.com/p/e6cefe097c3a