Java Collection框架 - LinkedList

基于jdk1.8

简介

LinkedList采用链表作为内部数据结构。它的新增和删除操作的时间复杂度都是O(1)，查找跟修改的时间复杂度是O(n)。但在插入和删除节点之前必须先找到该节点，因此除了头尾的插入和删除操作是O(1)外，其它节点最差的情况下是O(n)。LinkedList也不是线程安全的

数据结构

先看一下数据结构：

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

LinkedList的每个节点都包括三个属性：前后节点引用和节点的值。LinkedList还用first和last两个属性记录了链表的头尾节点

主要属性与方法列表

//链表容量
size : int
//链表头
first : Node<E>
//链表尾
last : Node<E>

getFirst() : E
getLast() : E
removeFirst() : E
removeLast() : E
addFirst(E) : void
addLast(E) : void
contains(Object) : boolean
size() : int
add(E) : boolean
remove(Object) : boolean
addAll(Collection<? extends E>) : boolean
addAll(int, Collection<? extends E>) : boolean
clear() : void
get(int) : E
set(int, E) : E
add(int, E) : void
remove(int) : E
indexOf(Object) : int
lastIndexOf(Object) : int
peek() : E
element() : E
poll() : E
remove() : E
offer(E) : boolean
offerFirst(E) : boolean
offerLast(E) : boolean
peekFirst() : E
peekLast() : E
pollFirst() : E
pollLast() : E
push(E) : void
pop() : E
removeFirstOccurrence(Object) : boolean
removeLastOccurrence(Object) : boolean
listIterator(int) : ListIterator<E>
descendingIterator() : Iterator<E>
clone() : Object
toArray() : Object[]
toArray(T[]) <T> : T[]

主要代码分析

由于LinkedList同时实现了List和Deque两个接口，因此LinkedList中的方法可以大致分为两种：

• List系：方法名中包括get、add、set、remove等字眼
• Deque系：方法名中包括peek、offer、push、pull、pop、first、last等字眼

1. 查找

LinkedList提供了下列方法用于读取链表节点：
* get(int index)
* getFirst()
* getLast()
* peek()
* peekFirst()
* peekLast()
* element() ==> getFirst()

其中getFirst()和peekFirst()、getLast()和peekLast()分别用于获取链表的头尾节点。getFirst()和getLast()在获取节点时，如果链表为空，则会抛出NoSuchElementException，peekFirst()和peekLast()只会返回null值，不抛出异常。peek()与peekFirst()完全相同。element()内部调用的getFirst()

• getFirst()：获取链表的头节点

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

• getLast()：获取链表的尾节点

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

• peek()/peekFirst()：获取链表头节点

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

• peekLast()：获取链表尾节点

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

• get(int index)：获取指定索引处的节点

    public E get(int index) {
        //检查index值是否合法
        checkElementIndex(index);
        return node(index).item;
    }
  

  get(int index)依赖node(int index)，实际上，在LinkedList中每个与索引有关的方法都依赖node(int index)。下面是node(int index)的代码：

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

  node(int index)使用二分查找来提高查找效率

2. 增加

LinkedList提供了下列方法用于向链表中添加节点：
* add(E e) ==> linkLast(E e)
* add(int index, E e)
* addFirst(E e) ==> linkFirst(E e)
* addLast(E e) ==> linkLast(E e)
* offer(E e) ==> add(E e)
* offerFirst(E e) ==> addFirst(E e)
* offerLast(E e) ==> addLast(E e)
* push(E e) ==> addFirst(E e)
* addAll(Collection<? extends E> c) ==> addAll(int index, Collection<? extends E> c)
* addAll(int index, Collection<? extends E> c)

从上面可以看出LinkedList有很多种添加方法，但实际上大多数方法依赖linkFirst(E e)和linkLast(E e)作为实现。根据返回值可以分为两类：
* 没有返回值的方法，如addFirst(E e)、addLast(E e)和push(E e)
* 返回boolean的方法，如add(E e)、offer(E e)、offerFirst(E e)和offerLast(E e)

既然linkFirst(E e)跟linkLast(E e)这么重要，就先看它们的代码
* linkFirst(E e)：向链表头添加节点

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

* ``linkLast(E e)``：向链表尾添加节点

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

那些依赖linkFirst(E e)跟linkLast(E e)的方法就不一一列出了，直接看别的方法

• add(int index, E e)：将节点添加到指定索引位置

    public void add(int index, E element) {
        //检查index值是否合法
        checkPositionIndex(index);
  
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
  

  可以看到，add(int index, E e)是依赖linkBefore(E e, Node<E> succ)实现的，直接看linkBefore(E e, Node<E> succ)的代码：

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

3. 修改

LinkedList提供了set(int index, E e)用于修改链表

• set(int index, E e)：修改指定索引对应节点的值

    public E set(int index, E element) {
        //检查index值是否合法
        checkElementIndex(index);
        //获取节点
        Node<E> x = node(index);
        //修改节点值
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }
  

  set(int index, E e)中没有modCount++这句代码（作用是更新链表的修改计数器，与ConcurrentModificationException异常有关），因为该方法并没有改变链表的结构，只是更新节点的值

4. 删除

LinkedList提供了下列方法用于删除链表中的节点：
* remove(int index)
* remove(Object o)
* remove() ==> removeFirst()
* removeFirst() ==> unlinkFirst(Node<E> n)
* removeLast() ==> unlinkLast(Node<E> n)
* poll() ==> unlinkFirst(Node<E> n)
* pollFirst() ==> unlinkFirst(Node<E> n)
* pollLast() ==> unlinkLast(Node<E> n)
* pop() ==> removeFirst()
* removeFirstOccurrence(Object o) ==> remove(Object o)
* removeLastOccurrence(Object o)

与添加类似，大多数方法依赖unlinkFirst(Node<E> n)跟unlinkLast(Node<E> n)，可以分为两种：
* 抛出NoSuchElementException异常，如remove()、removeFirst()、removeLast()和pop()
* 不抛出异常，如poll()、pollFirst()和pollLast()

unlinkFirst(Node<E> n)跟unlinkLast(Node<E> n)的代码：
* unlinkFirst(Node<E> n)：删除头节点

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

* ``unlinkLast(Node<E> n)``：删除尾节点

  ```java
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        //更新尾节点
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }
  ```

• remove(int index)：根据索引删除节点

    public E remove(int index) {
        //检查index值是否合法
        checkElementIndex(index);
        return unlink(node(index));
    }
  

  remove(int index)内部使用unlink(Node<E> n)作为实现，unlink(Node<E> n)的代码如下：

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

• remove(Object o)：根据节点值删除节点

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

  可以看到remove(Object o)其实也是依赖unlink(Node<E> n)实现的。removeFirstOccurrence(Object o)则是依赖remove(Object o)实现的所以就不列出了

• removeLastOccurrence(Object o)：删除倒数第一个找到的节点

    public boolean removeLastOccurrence(Object o) {
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
  

  removeLastOccurrence(Object o)与remove(Object o)的实现几乎相同，只不过一个是倒序查找，一个是正序查找

总结

LinkedList虽然实现了很多操作链表的方法，但大多数都依赖以下几个方法：

• linkFirst(E e)
• linkLast(E e)
• linkBefore(E e, Node<E> succ)
• unlinkFirst(Node<E> f)
• unlinkLast(Node<E> l)
• unlink(Node<E> x)
• node(int index)

LinkedList通过这些方法，将实际数据结构与接口方法实现分离开来