LinkedList 常用方法

LinkedList 是使用双向链表的形式存储数据 

 1 private static class Node<E> {
 2     E item;
 3     Node<E> next;
 4     Node<E> prev;
 5
 6     Node(Node<E> prev, E element, Node<E> next) {
 7         this.item = element;
 8         this.next = next;
 9         this.prev = prev;
10     }
11 }

构造方法：

 1 public LinkedList() { // ？？？
 2 }
 3 public LinkedList(Collection<? extends E> c) { //
 4     this();
 5     addAll(c);
 6 }
 7 public boolean addAll(Collection<? extends E> c) {
 8     return addAll(size, c);
 9 }
10
11 public boolean addAll(int index, Collection<? extends E> c) {
12     checkPositionIndex(index); //检查 下标是否正确
13
14     Object[] a = c.toArray(); //将要插入的集合转成数组
15     int numNew = a.length;
16     if (numNew == 0)
17         return false;
18
19     Node<E> pred, succ;
20     if (index == size) { //如果要插入的下标正好是链表的末尾
21         succ = null;
22         pred = last; //则前一个元素正好是last
23     } else {
24         succ = node(index);  //会根据插入的位置，选择较快的方式找到当前index位置的元素，并保存下来
25         pred = succ.prev;
26     }
27
28     for (Object o : a) { //遍历每一个元素
29         @SuppressWarnings("unchecked") E e = (E) o;
30         Node<E> newNode = new Node<>(pred, e, null); //创建新的元素，并使它的pred指向前一个元素
31         if (pred == null) //如果前一个元素为null 当前元素就是first 调用第二个构造函数传入collection或是index为0
32             first = newNode;
33         else
34             pred.next = newNode;  //使前一个元素的next 指向新插入的元素
35         pred = newNode; //把当前节点作为pred
36     }
37
38     if (succ == null) {
39         last = pred;
40     } else {          // 把之前保存下来的 index 位置上的元素及其之后的节点 接上
41         pred.next = succ;
42         succ.prev = pred;
43     }
44
45     size += numNew;
46     modCount++;
47     return true;
48 }

add()

 1 public boolean add(E e) {
 2     linkLast(e);
 3     return true;
 4 }
 5
 6 void linkLast(E e) {
 7     final Node<E> l = last; //得到最后一个节点
 8     final Node<E> newNode = new Node<>(l, e, null); //把当前节点的pred指向last节点
 9     last = newNode; //把当前节点作为last节点
10     if (l == null)
11         first = newNode;
12     else
13         l.next = newNode;
14     size++;
15     modCount++;
16 }

set();

1 public E set(int index, E element) {
2     checkElementIndex(index);
3     Node<E> x = node(index);
4     E oldVal = x.item;
5     x.item = element; //更换 item
6     return oldVal;
7 }

remove（）

 1 public E remove(int index) { //根据 下标 删
 2     checkElementIndex(index);
 3     return unlink(node(index)); //根据下标拿到Node节点
 4 }
 5
 6 E unlink(Node<E> x) {
 7     // assert x != null;
 8     final E element = x.item;
 9     final Node<E> next = x.next;
10     final Node<E> prev = x.prev;
11
12     if (prev == null) { //如果当前节点时first 则把next设为 first
13         first = next;
14     } else { //否则 则把 前一个节点的 next 指向 当前节点的next
15         prev.next = next;
16         x.prev = null; //断开对前一个节点的引用
17     }
18
19     if (next == null) { //如果next是null 则上一个节点就是 last
20         last = prev;
21     } else {
22         next.prev = prev; //把next的prev 指向 x的上一个节点
23         x.next = null;
24     }
25
26     x.item = null;
27     size--;
28     modCount++;
29     return element;
30 }