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     transient int size = 0; 
2     
3     transient Node<E> first; 
4     
5     transient Node<E> last;  

 1     /**
 2      * 返回指定位置处节点的元素值
 3      *
 4      * @param 指定位置
 5      * @return 节点元素
 6      * @throws 越界异常
 7      */
 8     public E get(int index) {
 9         checkElementIndex(index);  //检查用户指定索引位置是否越界
10         return node(index).item;  //返回指定索引处节点的元素值
11     }
12     
13     /**
14      * 返回指定索引位置处的节点
15      */
16     Node<E> node(int index) {
17         // LinkedList是双向链表，所以可以进行双向查找，效率提高
18         if (index < (size >> 1)) {  //如果指定位置在list节点数量的一半之前，则从前向后查找
19             Node<E> x = first;  //首先x保存的是头节点
20             for (int i = 0; i < index; i++)
21                 x = x.next;  //循环往后查找，每次循环前都将x的引用指向当前节点的下一个节点
22             return x;  //跳出循环时x的引用就是index位置处的节点对象
23         } else {   //如果指定位置在list节点数量的一半之后，则从后向前查找
24             Node<E> x = last;
25             for (int i = size - 1; i > index; i--)
26                 x = x.prev;
27             return x;
28         }
29     }

 1     /**
 2      * 将指定位置处节点的元素值替换为自定义的值
 3      *
 4      * @param 指定索引位置
 5      * @param 要替换成自定义的值
 6      * @return 原先被替换了的值
 7      * @throws 越界异常
 8      */
 9     public E set(int index, E element) {
10         checkElementIndex(index);  //检查索引是否越界
11         Node<E> x = node(index);  //获取指定索引处原先的节点对象
12         E oldVal = x.item;  //将原先该节点的值保存下来
13         x.item = element;  //将该节点的元素值替换为新值
14         return oldVal;  //返回该节点原先的元素值
15     }

 1     /**
 2      * add方法，默认把元素添加到链表的尾部
 3      *
 4      * @param e 要添加的元素
 5      * @return true 添加成功
 6      */
 7     public boolean add(E e) {
 8         linkLast(e);   //实际调用的是linkLast(e)这个方法
 9         return true;
10     }
11     
12     /**
13      * 将元素e设置为链表尾部节点
14      */
15     void linkLast(E e) {
16         final Node<E> l = last;  //将原先的尾节点赋值给 l变量(可能为空)
17         final Node<E> newNode = new Node<>(l, e, null); //新建一个保存元素e的节点，前驱指向原来的尾节点 l，后驱指向为null
18         last = newNode;  //将当前的尾节点更新为新建的这个节点
19         if (l == null)  //若原先尾节点为null，说明这个链表原先就是空的，此次放入的e元素是其第一个节点
20             first = newNode;  //将当前链表的头节点设置为新增的e元素节点（此时链表中有且只有一个节点,头节点和尾节点都指向这个e元素节点）
21         else  //若原先尾节点不是null，则说明原先链表里就存在节点
22             l.next = newNode;  //那么将原先的尾节点(已经在上面第16行赋值给了 l 变量)的后驱指向新建的这个节点即可(这个新建节点已经在上面第18行设置为了当前链表的尾节点)
23         size++;   //链表节点数量加1
24         modCount++;
25     }

 1     /**
 2      * 删除链表中第一个和指定元素相同的节点，删除成功返回true
 3      * 链表中没有要删除的元素节点，则返回false
 4      *
 5      * @param o 需要删除的元素
 6      * @return true/false
 7      */
 8     public boolean remove(Object o) {
 9         if (o == null) {   //如果要删除的元素为 null
10             for (Node<E> x = first; x != null; x = x.next) {
11                 if (x.item == null) {   //找到第一个为null的元素
12                     unlink(x);  //调用unlink()方法删除节点
13                     return true;
14                 }
15             }
16         } else {   //如果要删除元素非null
17             for (Node<E> x = first; x != null; x = x.next) {
18                 if (o.equals(x.item)) {   //找到第一个和该元素相等的节点
19                     unlink(x);  //调用unlink()方法删除节点
20                     return true;
21                 }
22             }
23         }
24         return false;
25     }
26     
27     /**
28      * 删除节点
29      */
30     E unlink(Node<E> x) {
31         // assert x != null;        
32         final E element = x.item;   //分别获取要删除节点的  前驱节点、元素、后驱节点
33         final Node<E> next = x.next;
34         final Node<E> prev = x.prev;
35 
36         if (prev == null) {  //如果当前要删除节点指向的前驱节点为空，则说明要删除的节点就是头节点
37             first = next;  //将头节点变更为当前删除节点的下一个节点
38         } else {   //如果当前要删除的节点不是头节点
39             prev.next = next;  //将前一个节点的后驱指向当前被删除节点的下一个节点
40             x.prev = null;  //被删除节点的前驱置为null
41         }
42 
43         if (next == null) {   //如果当前要删除节点指向的后驱节点为空，则说明要删除的节点就是尾节点
44             last = prev;  //将尾节点变更为当前删除节点的前一个节点
45         } else {   //如果当前要删除的节点不是尾节点
46             next.prev = prev;  //将当前删除节点后一个节点的前驱指向当前被删除节点的上一个节点
47             x.next = null;  //被删除节点的后驱置为null
48         }
49 
50         x.item = null;  //被删除节点元素置为null
51         size--;  //链表节点数量减1
52         modCount++;
53         return element;  //返回被删除节点的元素
54     }