LinkedList

extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

• 容器实体

  /**
   * Pointer to first node.
   * Invariant: (first == null && last == null) ||
   *            (first.prev == null && first.item != null)
   */

  transient Node<E> first;

  /**
   * Pointer to last node.
   * Invariant: (first == null && last == null) ||
   *            (last.next == null && last.item != null)
   */
  transient Node<E> last;

用途

基于 Deque

• 队列 (FIFO)

LinkedList<String> queue = new LinkedList<>();
queue.offer("A");       // 将元素添加到队列末尾
queue.offer("B");
String head = queue.poll();  // 从队列头部移除并返回元素，此处返回"A"
String peek = queue.peek();  // 查看队列头部元素而不移除它，此处返回"B"

• 堆栈(LIFO)

LinkedList<String> stack = new LinkedList<>();
stack.push("A");       // 将元素推到堆栈上
stack.push("B");
String top = stack.pop();   // 从堆栈顶部移除并返回元素，此处返回"B"