1 引言

LinkedList 底层基于双向链表实现，插入、获取、删除，都可以从队头、队尾来实现，完全可以当做一个队列来用，offer()往队尾插入元素，poll()从队头删除元素。

优点：队头、队尾、队中插入数据，哪怕是插入大量的数据，也不会出现任何的大量元素的挪动和数组扩容。在中间插入元素性能没有队头和队尾那么好，需要遍历链表到指定的位置，然后完成元素的插入。

缺点：如果是要随机位置获取一个元素，get(int index)这个方法，需要遍历，如果数据很多，性能比较差的。

2 类继承关系

LinkedList不仅实现了List接口，还实现了Queue和Deque接口，所以它既能作为List使用，也能作为双端队列使用，当然也可以作为栈使用。

3 主要属性与内部类

// 元素个数
transient int size = 0;
// 链表首节点
transient Node<E> first;
// 链表尾节点
transient Node<E> last;

属性很简单，定义了元素个数size和链表的首尾节点。

Node 内部类：典型的双向链表结构。

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

4 主要方法

4.1 add

• add()：默认就是在队列的尾部插入一个元素，在那个双向链表的尾部插入一个元素

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

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

• add(index, element)：是在队列的中间插入一个元素，会判断是在前半段插入还是在后半段插入。

  public void add(int index, E element) {
      checkPositionIndex(index);
    	// 在尾部插入
      if (index == size)
          linkLast(element);
      else
        	// 指定索引位置插入
          linkBefore(element, node(index));
  }
  

  /**
   * Returns the (non-null) Node at the specified element 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;
      }
  }
  

  /**
   * Inserts element e before non-null Node 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++;
  }
  

• addFirst()：在队列的头部插入一个元素

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

• addLast()：跟add()方法是一样的，也是在尾部插入一个元素

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

• offer() == add()：就是在队列尾部入队，将一个元素插入队列尾部，同理还有offerFirst()，offerLast()

4.2 get

• poll()：从队列头部出队

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

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

• peek()：获取队列头部的元素，但是头部的元素不出队

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

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

• get(int index)

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

4.3 remove

• remove()：删除头结点

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

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

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

• remove(int index)

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

• removeLast()

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