LinkedList源码分析

发表于   |   分类于   |     |   本文总阅读量 次

#成员变量

1
2
3
transient int size = 0; //LinkedList的大小
transient Node<E> first; //链表中第一个节点
transient Node<E> last; //链表中最后一个节点

Node类是ListedList的一个内部类，其结构如下：

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

item表示当前节点的值，next引用指向下一个节点，prev引用指向前一个节点，这就是双向链表的特征

#构造方法

1
2
3
4
5
6
7
8
//构造一个无参
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

所有实现Collection接口的容器类，都一定有两个构造方法，一个无参，一个有参（参数为所有实现Collection的对象）

LinkedList(Collection< ? extends E> c) ：构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列

首先调用this()生成一个空的LinkedList对象，然后调用addAll，把参数的Collection添加到LinkedList中，addAll（Collection< ? extends E> c）代码如下：

1
2
3
public boolean addAll(Collection<? extends E> c) {
       return addAll(size, c);
   }

addAll方法有两个：
addAll(Collection< ? extends E> c) ： 把Collection添加到LinkedList的尾端
addAll(int index, Collection< ? extends E> c)：把Collection添加到LinkedList的index位置

在构造方法中调用一参的addAll，从而调用二参的addAll，此时index为成员变量size，即把Collection添加到LinkedList的尾端

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public boolean addAll(int index, Collection<? extends E> c) {
       //检查index位置是否超出边界
       checkPositionIndex(index);
       //把Collection转为数组   
       Object[] a = c.toArray();
       int numNew = a.length;
       //如果Collection为空，返回false，表示添加失败
       if (numNew == 0)
           return false;
       //pred指向前一个节点，succ指向下一个节点
       Node<E> pred, succ;
       //如果在链尾添加，下一个节点为空，pred指向当前链表最后一个节点
       if (index == size) {
           succ = null;
           pred = last;
       } else {
           /**
           如果不在链尾添加，调用node（index），内部通过遍历离链表取得index位置的节点，并把succ指向index位置的节点，pred指向index位置节点的前一个节点
           **/
           succ = node(index);
           pred = succ.prev;
       }
       //执行插入，注意pred
       for (Object o : a) {
           @SuppressWarnings("unchecked") E e = (E) o;
           Node<E> newNode = new Node<>(pred, e, null);
           //如果把o插入到链头
           if (pred == null)
               first = newNode;
           else
               //让index位置的前一个节点的next指向包含o的新节点
               pred.next = newNode;
           //把newNode节点作为pred
           pred = newNode;
       }
       //更新pred和succ
       if (succ == null) {
           last = pred;
       } else {
           pred.next = succ;
           succ.prev = pred;
       }
       //增加LinkedList的大小
       size += numNew;
       //LinkedList用modCount变量来记录链表改变的次数
       modCount++;
       return true;
   }

node(index)方法非常重要，LinkedList很多方法都是通过node(index)才取得index位置的节点，从而进一步操作：
例如set（int index， E e），就是要通过node（index）取得index位置的node，从而设置node.item = e；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//遍历链表从而取得index位置节点
   Node<E> node(int index) { //如果index 小于 size/2 则从头开始查找
       if (index < (size >> 1)) {
           Node<E> x = first;
           for (int i = 0; i < index; i++)
               x = x.next;
           return x;
       } else { //如果index 大于 size/2 则从尾部开始查找
           Node<E> x = last;
           for (int i = size - 1; i > index; i--)
               x = x.prev;
           return x;
       }
   }

增加方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
add(E e) ：将指定元素添加到此列表的结尾 
add(int index, E element)：在此列表中指定的位置插入指定的元素 
当index == size时，两个方法等效，都是添加到链表的尾部
接下来看看add(int index, E element)的源码：
 public void add(int index, E element) {
        checkPositionIndex(index);
        //当在链尾添加时，调用linkLast(element)，add(E e) 方法内部也是调用linkLast(element)
        if (index == size)
            linkLast(element);
        else
            //如果不是在链尾添加，则把element添加到index位置节点前
            linkBefore(element, node(index));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//succ是index位置的节点
   void linkBefore(E e, Node<E> succ) {
       // assert succ != null;
       //pred指向要添加的位置的前一个节点
       final Node<E> pred = succ.prev;
       //创建一个新节点
       final Node<E> newNode = new Node<>(pred, e, succ);
       //把新节点插入到index位置前
       succ.prev = newNode;
       //如果是在链表头部添加
       if (pred == null)
           first = newNode;
       else
           //把新节点插入到index位置前一个节点的后面，这样就把新节点插入到了index位置
           pred.next = newNode;
       //容量加1
       size++;
       //修改次数加1
       modCount++;
   }

除了linkBefore，linkFirst和linkLast也是其它增加方法的核心
例如addFirst内部是调用linkFirst，push()也是调用linkFirst，addLast()内部调用的是linkLast

#删除方法

remove(Object o)：从此列表中移除首次出现的指定元素（如果存在）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean remove(Object o) {
       if (o == null) {
           for (Node<E> x = first; x != null; x = x.next) {
               if (x.item == null) {
                   unlink(x);
                   return true;
               }
           }
       } else {
           for (Node<E> x = first; x != null; x = x.next) {
               if (o.equals(x.item)) {
                   unlink(x);
                   return true;
               }
           }
       }
       return false;
   }

这段代码很简单，就是遍历链表，把删除掉第一次出现参数值得节点，如果找不到，返回false

remove调用了unlink(x)方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
E unlink(Node<E> x) {
       // assert x != null;
       final E element = x.item;
       final Node<E> next = x.next;
       final Node<E> prev = x.prev;
       if (prev == null) {
           first = next;
       } else {
           prev.next = next;
           x.prev = null;
       }
       if (next == null) {
           last = prev;
       } else {
           next.prev = prev;
           x.next = null;
       }
       x.item = null;
       size--;
       modCount++;
       return element;
   }

#总结

LinkedList的实现是很简单的，数据结构是一个双向链表。

热评文章