JDK源代码之LinkedList

Posted on | Views:
Symbols count in article: 9.7k | Reading time ≈ 16 mins.

LinkedList特性

底层数据结构

LinkedList不同于ArrayList的数组，它基于链表。

效率

LinkedList的插入删除快，遍历慢（ArrayList正好相反）

实现的接口

1
2
3
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList实现了List接口、Deque双向队列接口（既可以当作FILO队列也可以当作FIFO栈）、Cloneable接口、序列化接口。
值得注意的是，LinkedList继承自AbstractSequentialList（AbstractSequentialList和ArrayList一样继承自AbstractList），也就是说，LinkedList比ArrayList更细化了一层。

细化的那层AbstractSequentialList实现了“链表”版的get/set/add/remove方法，这使得LinkedList和ArrayList有了质的差别（毕竟彼此的基因遗传都不同）。

同步机制

与ArrayList一样，LinkedList也是不同步的，可以用包装器来创造一个支持同步的List:

1
List list = Collections.synchronizedList(new LinkedList(...));

LinkedList字段

1
2
3
4
5
transient int size = 0;

transient Node<E> first;

transient Node<E> last;

很明显，LinkedList用了first节点和last节点来保存整个链表（ArrayList用的是数组）。
注：transient关键字的作用是防止该字段被序列化（一些敏感的信息不能序列化然后在网络上传输）。

LinkedList方法分析

linkFirst(E e) （将一个元素插入链表头部）

1
2
3
4
5
6
7
8
9
10
11
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

先建立一个以first为后继的新节点，令first为该新节点；然后再修改第二个节点的prev变量使其指向新头部（如果没有第二个节点就修改last）

linkLast(E e)（将一个元素插入链表尾部）

机制与linkFirst(E e)相似，只需将first替换为last

linkBefore(E e, Node succ) （将一个元素插到一个节点之前）

1
2
3
4
5
6
7
8
9
10
11
12
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

该方法会判断另一个节点之前是否有节点存在，没有就修改first。

unlinkFirst(Node f)（将链表头部节点剔除）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

该方法中有条垃圾回收优化的语句：

1
f.next = null; // help GC

强行令变量为null，不再引用该对象，该对象便会在下一轮的GC中被回收。
此外，该方法会判断第二个元素是否存在，没有就修改last。

unlinkLast(Node l)（将链表尾部节点剔除）

与unlinkFirst(Node<E> f)类似

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;
}

该方法需要判断前面的元素和后面的元素是否存在。

getFirst/getLast/removeFirst/removeLast/addFirst/addLast（会抛异常的获取增加与删除）

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
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

public void addFirst(E e) {
    linkFirst(e);
}

public void addLast(E e) {
    linkLast(e);
}

以上方法调用了之前的linkFirst、linkLast、unlinkFirst、unlinkLast等方法。

remove(Object o)（删除某个特定对象）

根据该对象是否为空分2种情况处理：

  1. 为空，从头扫到尾，利用==null来判断
  2. 不为空，从头扫到尾，利用equals来判断
    注：删除的时候，最终都是要找到要删除的节点，利用链表的解绑来删除。

addAll(int index, Collection<? extends E> c)（插入一个集合到特定的位置）

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
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

使用node(index)找到插入时的后继节点和前继节点（如果是插到尾部则后继节点为空而前继节点为last），中一一插入元素（根据前继节点来做关联），最后加入后继节点。

get(int index)（获取某个位置的数据）

该方法表现得很像数组有没有，可以获取特定位置的元素！
该方法调用了node(index)来获取该位置的节点，再获取该节点的数据，那么node(index)的原理是什么呢？

node(index)（获取某个位置的节点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Node<E> node(int index) {

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

这个方法很巧妙，先判断下标大小，超过一半就从后面开始遍历，否则从前面开始遍历！

add(int index, E element)（往某个位置插入一个数据）

1
先判断是否是尾部，是就调用linkLast(element)，不是就调用linkBefore(element, node(index))

isPositionIndex(int index) （判断一个位置是否能合法地插入数据）

1
2
3
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

indexOf(Object o)（查找某个对象的下标）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

从头往后遍历，复杂度较高。

peek()（获取头部数据，不会抛出异常只会返回null）

poll()(获取并移除头部数据，不会抛出异常只会返回null)

offer(E e)（将数据插入尾部）

针对双向队列实现的方法

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
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

public boolean offerLast(E e) {
    addLast(e);
    return true;
}

public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
 }

public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

以上方法均不会抛出异常，offer是添加，peek是获取，poll是获取并移除。

针对栈实现的方法

1
2
3
4
5
6
7
public void push(E e) {
    addFirst(e);
}

public E pop() {
    return removeFirst();
}

Iterator详解

java中的Iterator是神奇的东西，主要有hasNext()和next()方法供使用，前者判断是否还有元素可以遍历，后者将返回下一个元素。

Iterarot字段

1
2
3
4
private Node<E> lastReturned = null;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;

lastReturned是上一个返回的节点，next则是下一个将返回的节点。

Iterator方法

next()（返回下一个节点）
1
2
3
4
5
6
7
8
9
10
public E next() {
    checkForComodification();
    if (!hasNext())
        throw new NoSuchElementException();

    lastReturned = next;
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}

从这里可以看出，每次调用next()方法时，next字段相当于current，我们将返回这个current节点，令lastReturned指向current节点，最后，让next指向下一个准备返回的节点。
所以总结地说：该方法返回当前next指向的节点，并让next指向下一个节点。

previous()

1
2
3
4
5
6
7
8
9
public E previous() {
    checkForComodification();
    if (!hasPrevious())
        throw new NoSuchElementException();

    lastReturned = next = (next == null) ? last : next.prev;
    nextIndex--;
    return lastReturned.item;
}

该方法和next()类似，让next指向上一个节点，返回当前next指向的节点。
在该方法执行后，lastReturned和next指向同一个节点。

似乎next()方法和previous()方法的实现不太一致，原理不一样？
previous()方法并不会返回next指向的节点，而是返回next前面的节点。似乎把下标定义在previous和next之间会比较好一点。
比如有队列：

0 1 2 3 4 5 6

再定义一个iterator：

1
ListIterator<Integer> iterator = list.listIterator(3);

该iterator其实并不是指向第四个元素（因为从0开始计，所以参数是3而实际上是第四个元素），也就是3，而是指向2和3之间的空隙。
下标指向的位置如下：

0 1 2 ‘下标在这里(距离右边的3更近一点)’ 3 4 5 6

此时我们若调用next()者则返回右边的3，并将下标往右移动；若调用previous()则返回左边的2，并将下标往左移动。

remove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void remove() {
    checkForComodification();
    if (lastReturned == null)
        throw new IllegalStateException();

    Node<E> lastNext = lastReturned.next;
    unlink(lastReturned);
    if (next == lastReturned)
        next = lastNext;
    else
        nextIndex--;
    lastReturned = null;
    expectedModCount++;
}

删除之前被返回的节点，if (next == lastReturned)处理调用previous()方法后的情况。

内部类DescendingIterator（反向的iterator）

调用next()实际上会调用previous()，所以它实际上是个单向的，从后向前的iterator（虽然语法上它一直在调用next()）

toArray(T[] a)（将内容放到特定的数组中去）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        a = (T[])java.lang.reflect.Array.newInstance(
                            a.getClass().getComponentType(), size);
    int i = 0;
    Object[] result = a;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;

    if (a.length > size)
        a[size] = null;

    return a;
}

该方法中，如果目标数码长度不够，就利用反射的方法重新创建一个足够大的数组。

writeObject(java.io.ObjectOutputStream s)

将LinkedList内容写入到流中去。

readObject(java.io.ObjectInputStream s)

从流中读出一个LinkedList。

静态内部类LLSpliterator

该类有待继续深入研究。

Related Posts