线性链表 LinkedList 学习，比起 HashMap 真是简单多了。

@[toc]

LinkedList

特点

• 有序，但内存空间中可能比较分散；
• 存储相对较快、获取相对较慢；
• 存储的数据可以为 null；
• 线程不安全。

LinkedList 继承/实现

• 继承 AbstractSequentialList：
  线性序列结构的抽象，继承于 AbstractList；
  抽象方法 listIterator()，子类必须实现此方法用于创建迭代器；
  内部封装使用该迭代器实现的 add()、set()、remove()等方法。

public abstract ListIterator<E> listIterator(int index);

• 实现 List 接口：具有线性表的特性。
• 实现 Deque 接口：该接口继承于 Queue 接口，具有队列特性。

参数以及构造函数

• 参数

// 结点数量
transient int size = 0;
// 头结点
transient Node<E> first;
// 尾结点
transient Node<E> last;

• 构造函数

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

传入 Collection c参数的构造函数的实现就是遍历将结点存入 LinkedList 中。

基础元素

比较简单的一个静态内部类，一个双向结点。

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

添加元素 add(E e) / offer(E e)

添加单个元素

public boolean offer(E e) {
    return add(e);
}
public boolean add(E e) {
    linkLast(e);
    return true;
}

重要函数： linkLast() 向队尾添加元素，多个添加元素的功能都依靠该方法实现。

void linkLast(E e) {
    // 先找到尾结点
    final Node<E> l = last;
    // 创建新结点，新结点的前一结点指向尾结点，后一结点为 null
    final Node<E> newNode = new Node<>(l, e, null);
    // 新加入的结点要作为最后一个结点记录
    last = newNode;
    if (l == null) // 如果尾结点为 null，说明是空的，将首结点也置为新结点
        first = newNode;
    else // 尾结点存在，新结点放到尾结点后面
        l.next = newNode;
    size++;
    modCount++;
}

• 新结点创建后，把头结点指向队列的尾结点，尾结点指向 null。注意此时只是新结点指向了前一结点指向了尾结点；
• 尾结点为 null 说明队列是空的，需要把头结点也指向新结点；
• 如果队列不为空，需要把尾结点的下一结点指向新结点。双向链表的一种体现，新结点的前方指向尾结点、尾结点的后方指向新结点。

指定位置添加元素

LinkedList 是有序的，所以是可以往中间插入数据的：

public void add(int index, E element) {
    // 1. 检查下标
    checkPositionIndex(index);
    // 2. 尾部插入数据
    if (index == size)
        linkLast(element);
    else // 3. 指定位置插入数据
        linkBefore(element, node(index));
}

1. 检查下标，大于等于零且小于等于结点数量 size；
2. 如果要插入的数据位置等于 size，说明要添加到链表尾部，调用上面的 linkLast 方法插入即可；
3. 指定位置添加的话先找到这个位置的数据：

Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}

• 查找时二分了一下，后面还是遍历。
• 有意思的是前半截查找是正着遍历，后半截查找是倒着遍历。
• 正序遍历只需找到所查元素的前一个元素即可，结果是前一结点的 next；
• 倒序遍历同理，找到所查元素后一个元素，结果是 prev 结点。

找到 index 位置的元素之后，就可以掰断链表，再把新数据链接进来：

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

添加一堆元素

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

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index); // 判断下标是否越界，需要 >=0 && <=size
    // 转换为数组
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    // 如果是在尾部添加，当前结点是 null，前一结点是最后结点
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        // 否则找到当前下标的结点，pred 记录前一结点
        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 指向新结点，下次遍历接着往后添加
        pred = newNode;
    }
    // 如果是在链表尾部添加的，last 结点标记为最后添加的结点
    if (succ == null) {
        last = pred;
    } else {
        // 如果不是在链表尾部添加，last 结点不用动
        // 并且把最后遍历的结点和插入位置的结点连起来，放在了前面
        pred.next = succ;
        succ.prev = pred;
    }
    // 标记次数
    size += numNew;
    modCount++;
    return true;
}

添加元素到头尾

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

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

public void addLast(E e) {
    linkLast(e);
}
// 上文有写到该方法，往链表后添加大多调用次方法
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

清空元素 clear()

public void clear() {
    // 遍历置空，从头开始
    for (Node<E> x = first; x != null; ) {
        // 先找到 x 的下一个元素，遍历完赋值给 x
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    // 归零
    first = last = null;
    size = 0;
    modCount++;
}

获取元素

获取下标 indexOf(Object o) & 是否包含 contains(Object o)

获取下标 indexOf() 方法，找到返回下标，找不到返回 -1：

// 主要就是遍历，注意区分查询 null 值的情况
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;
}

contains 调用的是 indexOf() 方法，返回 -1 说明没查到，反之返回 true。

public boolean contains(Object o) {
    return indexOf(o) != -1;
}

获取某元素 get()

首先查询下标是否越界，越界抛异常。

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

接着还是调用 node() 方法传入下标，返回获取到的数据即可。

Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}

获取头元素 element() peek()

element() 是从 Queue 接口实现来的方法，功能是返回头元素，特点是查不到抛出NoSuchElementException 异常。

public E element() {
    return getFirst();
}

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

peek() 方法元素返回头元素，查不到返回 null，不会抛出异常：

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

删除元素 remove() poll()

remove() 方法默认删除的是头元素，如果是 null 的话会抛 NoSuchElementException异常：

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

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

会调用 unlinkFirst() 方法移除首元素：

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

poll() 方法不会抛出异常：

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

删除某位置的元素 remove(int index)

涉及下标的依旧先确定下标是否越界，然后找到改位置的元素：

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

调用 node(index) 方法查找元素，之前多次见过，就是那个把数据分成两半去查询的。

然后再调用 unlink() 方法把该元素从链中移除，要注意头尾结点的处理：

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;
    }
    // 置空、元素数量 -1
    x.item = null;
    size--;
    modCount++;
    return element;
}

删除某元素 remove(Object o)

删除某元素就是根据值遍历找到该元素，执行 unlink() 断链删除，注意删除 null 值的情况。

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

设置某位置的值 set()

检查下标、找到该位置的数据、更新值即可。

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

迭代器

线性迭代器 ListItr

常用的获取迭代器：

 LinkedList linkedList = new LinkedList();
 linkedList.iterator();// 会创建 LinkedList 的线性迭代器，

该方法调用 LinkedList 的 listIterator() 方法：

public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

ListItr 源码：

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;

    ListItr(int index) {
        // 默认传的 0，next 值为头结点
        // 倒序迭代器会传元素数量 size，next 为 null
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean hasNext() {
        return nextIndex < size;
    }

    public E next() {
        // 判断遍历过程中数据是否被修改，出现问题抛异常
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();
        // 记录最后返回的值，然后指针后移
        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }
    // 是否包含前一个元素，下标 >=0 说明存在前一元素
    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();
        // 倒序遍历用，记录的前一数据为 null 则返回 LinkedList 的最后一个数据
        // 下次遍历，next 就不为 null 了，返回 前一个元素
        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }

    public int nextIndex() {
        return nextIndex;
    }

    public int previousIndex() {
        return nextIndex - 1;
    }

    public void remove() {
        checkForComodification();
        if (lastReturned == null)
            throw new IllegalStateException();
        // 先记录要移除的下一元素 next 结点
        Node<E> lastNext = lastReturned.next;
        // 把下一结点移除
        unlink(lastReturned);
        // 如果指针结点就是要移除的结点，后移一下
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        expectedModCount++;
    }

    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        // 默认设置最后返回数据的值
        lastReturned.item = e;
    }

    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        // next 为 null 说明后面没数据了，添加到队尾
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }

    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (modCount == expectedModCount && nextIndex < size) {
            action.accept(next.item);
            lastReturned = next;
            next = next.next;
            nextIndex++;
        }
        checkForComodification();
    }
    // 检测是否被修改（强一致性特点）
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

倒序迭代器

private class DescendingIterator implements Iterator<E> {
    // 传入 size 创建倒序迭代器
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

• 因为创建时传递的是 size，迭代器创建时指针结点 next 为 null，调用 previous() 方法会返回最后一个元素。下次就会返回最后一个元素的前一元素。

同步性

• 不同步，遍历时如果数据修改会抛异常；
• 多线程下可能造成数据覆盖、丢失。

解决方法：

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

总结及对比

ArrayList

• 基于数组，查询速度较快，时间复杂度 O(1)；
• 添加删除需要复制数据，影响效率；
• 容量不足时需要扩容。

LinkedList

• 基于链表，元素必须挨个查询。下标查询或许可以通过二分提高效率；
• 头尾添加删除数据较快，往固定位置添加数据还是需要遍历查找位置；
• 无需扩容，只有内存够，使劲添加。