LinkedList

概览

LinkedList类扩展AbstractSeqentialList并执行List，queue接口。
基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。
LinkedList在随机访问方面相对比较慢，但它的特性集较ArrayList更大。LinkedList 还可以用作栈、队列和双向队列。

总结：

• 对于链表头尾的操作，实现deque接口，效率都比较高，LinkedList 保存了头尾两个节点，以及节点数
• 对于关于索引，会判断在前半部分还是后半部分，进行遍历
• 关于元素，根据元素是否为空决定比较地址还是内容，根据是第一次出现还是最后一次出现决定遍历方向

LinkedList本身定义了一些主要用于操作和访问列表的方法：

public void push(E e) // 等同于 addFirst
public boolean offerFirst(E e) // 等同于 addFirst
public void addFirst(E e) // 在列头加元素 == private void linkFirst(E e)
public boolean offerLast(E e) // 等同于 addLast
public void addLast(E e) // 在列尾加元素 == void linkLast(E e)
public boolean add(E e) // 在列尾加元素 == void linkLast(E e)
public void add(int index, E element) // linkLast(element) or linkBefore(element, node(index))
public boolean addAll(Collection<? extends E> c)
public E peekFirst() 
public E getFirst() // 获得第一个元素
public E getLast() // 获得最后一个元素
public E peekLast() 
public E pop() // 等同于removeFirst
public E pollFirst() // 等同于removeFirst
public E removeFirst() // 删除并获得第一个元素 -> private E unlinkFirst(Node<E> f)
public E pollLast() // 等同于removeLast
public E removeLast() // 删除并获得最后一个元素 -> private E unlinkLast(Node<E> l)
public boolean remove(Object o) // 遍历查询指定元素删除
public E pollLast() //

关键属性

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

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

构造器

LinkedList(); // 建立空的链接列表
LinkedList(Collection c); // 建立由c初始化的链接列表

查找

查询会去遍历这个链表，有一个优化的机制，通过二分查询，index决定是从头开查询还是从尾开始查询

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
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;
        }
    }

添加元素

• 对链表头尾进行操作

  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++;
    }
  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 add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(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++;
    }

• 调用addAll方法添加一组元素

  • 无论是addAll(Collection<? extends E> c)，还是LinkedList(Collection c) 构造器

  • 本质是调用public boolean addAll(int index, Collection<? extends E> c)

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

删除元素

• 对链表头尾进行操作

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

• 对链表中间部分进行操作

  • 判断需要删除元素是否为空，分开进行处理

  • 从头遍历到尾，直到找到第一个符合条件的指定元素，删除

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

    迭代器

    public ListIterator<E> listIterator(int index) {
       checkPositionIndex(index);
       return new ListItr(index);
    }
    private class ListItr implements ListIterator<E> {
       private Node<E> lastReturned;
       private Node<E> next;
       private int nextIndex;
       private int expectedModCount = modCount;
    ListItr(int index) {
           // assert isPositionIndex(index);
           next = (index == size) ? null : node(index);
           nextIndex = index;
       }
    }

    拷贝

• clone 是一个深拷贝

  public Object clone() {
        LinkedList<E> clone = superClone();
        // Put clone into "virgin" state
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;
        // Initialize clone with our elements
        for (Node<E> x = first; x != null; x = x.next)
            clone.add(x.item);
        return clone;
    }
  private LinkedList<E> superClone() {
        try {
            return (LinkedList<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }