概览

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

总结：

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

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

  1. public void push(E e) // 等同于 addFirst
  2. public boolean offerFirst(E e) // 等同于 addFirst
  3. public void addFirst(E e) // 在列头加元素 == private void linkFirst(E e)
  4. public boolean offerLast(E e) // 等同于 addLast
  5. public void addLast(E e) // 在列尾加元素 == void linkLast(E e)
  6. public boolean add(E e) // 在列尾加元素 == void linkLast(E e)
  7. public void add(int index, E element) // linkLast(element) or linkBefore(element, node(index))
  8. public boolean addAll(Collection<? extends E> c)
  10. public E peekFirst() 
  11. public E getFirst() // 获得第一个元素
  12. public E getLast() // 获得最后一个元素
  13. public E peekLast() 
  15. public E pop() // 等同于removeFirst
  16. public E pollFirst() // 等同于removeFirst
  17. public E removeFirst() // 删除并获得第一个元素 -> private E unlinkFirst(Node<E> f)
  18. public E pollLast() // 等同于removeLast
  19. public E removeLast() // 删除并获得最后一个元素 -> private E unlinkLast(Node<E> l)
  20. public boolean remove(Object o) // 遍历查询指定元素删除
  21. public E pollLast() //

关键属性

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

构造器

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

查找

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

  1. public E get(int index) {
  2.         checkElementIndex(index);
  3.         return node(index).item;
  4.     }
  5. Node<E> node(int index) {
  6.         // assert isElementIndex(index);
  8.         if (index < (size >> 1)) {
  9.             Node<E> x = first;
  10.             for (int i = 0; i < index; i++)
  11.                 x = x.next;
  12.             return x;
  13.         } else {
  14.             Node<E> x = last;
  15.             for (int i = size - 1; i > index; i--)
  16.                 x = x.prev;
  17.             return x;
  18.         }
  19.     }

添加元素

  • 对链表头尾进行操作

    1. void linkLast(E e) {
    2.       final Node<E> l = last;
    3.       final Node<E> newNode = new Node<>(l, e, null);
    4.       last = newNode;
    5.       if (l == null)
    6.           first = newNode;
    7.       else
    8.           l.next = newNode;
    9.       size++;
    10.       modCount++;
    11.   }
    12. private void linkFirst(E e) {
    13.       final Node<E> f = first;
    14.       final Node<E> newNode = new Node<>(null, e, f);
    15.       first = newNode;
    16.       if (f == null)
    17.           last = newNode;
    18.       else
    19.           f.prev = newNode;
    20.       size++;
    21.       modCount++;
    22.   }

  • 对链表中间部分添加元素

    1.   public void add(int index, E element) {
    2.       checkPositionIndex(index);
    4.       if (index == size)
    5.           linkLast(element);
    6.       else
    7.           linkBefore(element, node(index));
    8.   }
    9. void linkBefore(E e, Node<E> succ) {
    10.       // assert succ != null;
    11.       final Node<E> pred = succ.prev;
    12.       final Node<E> newNode = new Node<>(pred, e, succ);
    13.       succ.prev = newNode;
    14.       if (pred == null)
    15.           first = newNode;
    16.       else
    17.           pred.next = newNode;
    18.       size++;
    19.       modCount++;
    20.   }

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

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

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

      1. public boolean addAll(int index, Collection<? extends E> c) {
      2.    checkPositionIndex(index);
      4.    Object[] a = c.toArray();
      5.    int numNew = a.length;
      6.    if (numNew == 0)
      7.        return false;
      9.    Node<E> pred, succ;
      10.    if (index == size) {
      11.        succ = null;
      12.        pred = last;
      13.    } else {
      14.        succ = node(index);
      15.        pred = succ.prev;
      16.    }
      18.    for (Object o : a) {
      19.        @SuppressWarnings("unchecked") E e = (E) o;
      20.        Node<E> newNode = new Node<>(pred, e, null);
      21.        if (pred == null)
      22.            first = newNode;
      23.        else
      24.            pred.next = newNode;
      25.        pred = newNode;
      26.    }
      28.    if (succ == null) {
      29.        last = pred;
      30.    } else {
      31.        pred.next = succ;
      32.        succ.prev = pred;
      33.    }
      35.    size += numNew;
      36.    modCount++;
      37.    return true;
      38. }

删除元素

  • 对链表头尾进行操作

    1. private E unlinkFirst(Node<E> f) {
    2.       // assert f == first && f != null;
    3.       final E element = f.item;
    4.       final Node<E> next = f.next;
    5.       f.item = null;
    6.       f.next = null; // help GC
    7.       first = next;
    8.       if (next == null)
    9.           last = null;
    10.       else
    11.           next.prev = null;
    12.       size--;
    13.       modCount++;
    14.       return element;
    15.   }
    16. private E unlinkLast(Node<E> l) {
    17.       // assert l == last && l != null;
    18.       final E element = l.item;
    19.       final Node<E> prev = l.prev;
    20.       l.item = null;
    21.       l.prev = null; // help GC
    22.       last = prev;
    23.       if (prev == null)
    24.           first = null;
    25.       else
    26.           prev.next = null;
    27.       size--;
    28.       modCount++;
    29.       return element;
    30.   }

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

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

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

      1. public boolean remove(Object o) {
      2.    if (o == null) {
      3.        for (Node<E> x = first; x != null; x = x.next) {
      4.            if (x.item == null) {
      5.                unlink(x);
      6.                return true;
      7.            }
      8.        }
      9.    } else {
      10.        for (Node<E> x = first; x != null; x = x.next) {
      11.            if (o.equals(x.item)) {
      12.                unlink(x);
      13.                return true;
      14.            }
      15.        }
      16.    }
      17.    return false;
      18. }
      19. E unlink(Node<E> x) {
      20.    // assert x != null;
      21.    final E element = x.item;
      22.    final Node<E> next = x.next;
      23.    final Node<E> prev = x.prev;
      25.    if (prev == null) {
      26.        first = next;
      27.    } else {
      28.        prev.next = next;
      29.        x.prev = null;
      30.    }
      32.    if (next == null) {
      33.        last = prev;
      34.    } else {
      35.        next.prev = prev;
      36.        x.next = null;
      37.    }
      39.    x.item = null;
      40.    size--;
      41.    modCount++;
      42.    return element;
      43. }

      迭代器

      1. public ListIterator<E> listIterator(int index) {
      2.    checkPositionIndex(index);
      3.    return new ListItr(index);
      4. }
      5. private class ListItr implements ListIterator<E> {
      6.    private Node<E> lastReturned;
      7.    private Node<E> next;
      8.    private int nextIndex;
      9.    private int expectedModCount = modCount;
      10. ListItr(int index) {
      11.        // assert isPositionIndex(index);
      12.        next = (index == size) ? null : node(index);
      13.        nextIndex = index;
      14.    }
      15. }

      拷贝

  • clone 是一个深拷贝

    1. public Object clone() {
    2.       LinkedList<E> clone = superClone();
    4.       // Put clone into "virgin" state
    5.       clone.first = clone.last = null;
    6.       clone.size = 0;
    7.       clone.modCount = 0;
    9.       // Initialize clone with our elements
    10.       for (Node<E> x = first; x != null; x = x.next)
    11.           clone.add(x.item);
    13.       return clone;
    14.   }
    15. private LinkedList<E> superClone() {
    16.       try {
    17.           return (LinkedList<E>) super.clone();
    18.       } catch (CloneNotSupportedException e) {
    19.           throw new InternalError(e);
    20.       }
    21.   }