LinkList(双向链表实现)

LinkedList是用链表结构存储数据的，比较适合数据的动态插入和删除，随机访问和遍历速度比较慢，还提供了List接口i中没有定义的方法，专门用于操作表头和表尾的元素，所以可以当作堆栈、队列和双向队列来使用。LInkedList持有头节点和尾节点的引用，有两个构造器，一个是无参构造器，另一个是传入外部集合构造器，它没有像ArrayList一样的初始大小的构造器。

  1 //集合元素个数
  2 
  3 transient int size = 0;
  4 
  5  
  6 
  7 //头结点引用
  8 
  9 transient Node<E> first;
 10 
 11  
 12 
 13 //尾节点引用
 14 transient Node<E> last;
 15 
 16 //无参构造器
 17 public LinkedList() {} 
 18 
 19 //传入外部集合的构造器
 20 public LinkedList(Collection<? extends E> c) {
 21     this();
 22     addAll(c);
 23 }
 24 
 25 //增(添加)
 26 public boolean add(E e) {
 27   
 28      //在链表尾部添加
 29     linkLast(e);
 30     return true;
 31 }
 32 
 33  
 34 //增(插入)
 35 public void add(int index, E element) {
 36 
 37     checkPositionIndex(index);
 38 
 39     if (index == size) {
 40         //在链表尾部添加
 41         linkLast(element);
 42     } else {
 43         //在链表中部插入
 44         linkBefore(element, node(index));
 45     }
 46 }
 47 
 48  
 49 
 50 //删(给定下标)
 51 public E remove(int index) {
 52 
 53     //检查下标是否合法
 54     checkElementIndex(index);
 55     return unlink(node(index));
 56 }
 57 
 58 //删(给定元素)
 59 public boolean remove(Object o) {
 60     if (o == null) {
 61         for (Node<E> x = first; x != null; x = x.next) {
 62             if (x.item == null) {
 63                 unlink(x);
 64                 return true;
 65             }
 66         }
 67     } else {
 68         //遍历链表
 69         for (Node<E> x = first; x != null; x = x.next) {
 70             if (o.equals(x.item)) {
 71                 //找到了就删除
 72                 unlink(x);
 73                 return true;
 74             }
 75         }
 76     }
 77     return false;
 78 }
 79 
 80  
 81 
 82 //改
 83 public E set(int index, E element) {
 84 
 85     //检查下标是否合法
 86     checkElementIndex(index);
 87 
 88     //获取指定下标的结点引用
 89     Node<E> x = node(index);
 90 
 91     //获取指定下标结点的值
 92 
 93     E oldVal = x.item;
 94 
 95     //将结点元素设置为新的值
 96 
 97     x.item = element;
 98 
 99     //返回之前的值
100 
101     return oldVal;
102 
103 }
104 
105 
106 //查
107 public E get(int index) {
108 
109     //检查下标是否合法
110     checkElementIndex(index);
111 
112     //返回指定下标的结点的值
113     return node(index).item;
114 }

LinkedList的添加元素的方法主要是调用LinkLast和LinkBefore两个方法，LinkLast方法是在链表后面链接一个元素，LinkBefore方法是在链表中间插入一个元素。LinkedList的删除方法通过调用unlink方法将某个元素从链表中移除。下面是链表的插入和删除操作的核心代码。

 1 //链接到指定结点之前
 2 void linkBefore(E e, Node<E> succ) {
 3 
 4     //获取给定结点的上一个结点引用
 5     final Node<E> pred = succ.prev;
 6 
 7     //创建新结点, 新结点的上一个结点引用指向给定结点的上一个结点
 8     //新结点的下一个结点的引用指向给定的结点
 9     final Node<E> newNode = new Node<>(pred, e, succ);
10 
11     //将给定结点的上一个结点引用指向新结点
12     succ.prev = newNode;
13 
14     //如果给定结点的上一个结点为空, 表明给定结点为头结点
15     if (pred == null) {
16 
17         //将头结点引用指向新结点
18         first = newNode;
19     } else {
20         //否则, 将给定结点的上一个结点的下一个结点引用指向新结点
21         pred.next = newNode;
22     }
23 
24     //集合元素个数加一
25     size++;
26 
27     //修改次数加一
28     modCount++;
29 
30 }
31 
32  
33 
34 //卸载指定结点
35 E unlink(Node<E> x) {
36 
37     //获取给定结点的元素
38     final E element = x.item;
39 
40     //获取给定结点的下一个结点的引用
41     final Node<E> next = x.next;
42 
43     //获取给定结点的上一个结点的引用
44     final Node<E> prev = x.prev;
45 
46     //如果给定结点的上一个结点为空, 说明给定结点为头结点
47     if (prev == null) {
48 
49         //将头结点引用指向给定结点的下一个结点
50         first = next;
51     } else {
52         //将上一个结点的后继结点引用指向给定结点的后继结点
53         prev.next = next;
54         //将给定结点的上一个结点置空
55         x.prev = null;
56 
57     }
58 
59     //如果给定结点的下一个结点为空, 说明给定结点为尾结点
60     if (next == null) {
61 
62         //将尾结点引用指向给定结点的上一个结点
63         last = prev;
64     } else {
65 
66         //将下一个结点的前继结点引用指向给定结点的前继结点
67         next.prev = prev;
68         x.next = null;
69 
70     }
71 
72     //将给定结点的元素置空
73     x.item = null;
74 
75     //集合元素个数减一
76     size--;
77     //修改次数加一
78     modCount++;
79     return element;
80 
81 }

View Code

通过源码的分析，对链表的插入和删除的时间复杂度都是O(1)，而对链表的查找和修改操作都需要遍历链表进行元素的定位，这两个操作都是调用的node(int index) 方法定位元素，如下代码演示根据下标来定位元素。

 1 //根据指定位置获取结点
 2 Node<E> node(int index) {
 3     //如果下标在链表前半部分, 就从头开始查起
 4     if (index < (size >> 1)) {
 5         Node<E> x = first;
 6         for (int i = 0; i < index; i++) {
 7             x = x.next;
 8         }
 9         return x;
10     } else {
11         //如果下标在链表后半部分, 就从尾开始查起
12         Node<E> x = last;
13         for (int i = size - 1; i > index; i--) {
14             x = x.prev;
15         }
16         return x;
17     }
18 }

View Code

通过下标定位时先判断是在链表的上半部还是下半部

上半部：从头开始找；

下半部：从尾开始找；

因此通过下标的查找和修改操作的时间复杂度是O(n/2)，通过对双向链表的操作还可以实现单项队列，双向队列和栈的功能。

单向队列的操作的代码：

 1 //获取头结点
 2 public E peek() {
 3     final Node<E> f = first;
 4     return (f == null) ? null : f.item;
 5 }
 6  
 7 //获取头结点
 8 public E element() {
 9     return getFirst();
10 }
11  
12 //弹出头结点
13 public E poll() {
14     final Node<E> f = first;
15     return (f == null) ? null : unlinkFirst(f);
16 }
17  
18 //移除头结点
19 public E remove() {
20     return removeFirst();
21 }
22  
23 //在队列尾部添加结点
24 public boolean offer(E e) {
25     return add(e);
26 }

View Code

双向队列的操作：

 1 //在头部添加
 2 public boolean offerFirst(E e) {
 3     addFirst(e);
 4     return true;
 5 }
 6  
 7 //在尾部添加
 8 public boolean offerLast(E e) {
 9     addLast(e);
10     return true;
11 }
12  
13 //获取头结点
14 public E peekFirst() {
15     final Node<E> f = first;
16     return (f == null) ? null : f.item;
17  }
18  
19 //获取尾结点
20 public E peekLast() {
21     final Node<E> l = last;
22     return (l == null) ? null : l.item;
23 }

View Code

栈操作：

1 //入栈
2 public void push(E e) {
3     addFirst(e);
4 }
5  
6 //出栈
7 public E pop() {
8     return removeFirst();
9 }

View Code

对LindedList，有：

1. LinkedList是基于双向链表实现的，不论是增删改查方法还是队列和栈的实现，都可通过操作结点实现

2. LinkedList无需提前指定容量，因为基于链表操作，集合的容量随着元素的加入自动增加

3. LinkedList删除元素后集合占用的内存自动缩小，无需像ArrayList一样调用trimToSize()方法

4. LinkedList的所有方法没有进行同步，因此它也不是线程安全的，应该避免在多线程环境下使用

5. 以上分析基于JDK1.7，其他版本会有些出入，因此不能一概而论

以上内容部分借鉴于：https://blog.csdn.net/iteen/article/details/83109717