注意：本文基于JDK1.8进行记录。

1 简介

允许任何符合规则的元素插入，包括null和重复元素。

底层是链表结构，使用链表代替索引，查找效率低，增删效率高。

线程不安全。

2 方法说明

2.1 构造方法

1 // 空参构造器。
2 public LinkedList();
3 // 传入了一个集合的构造器。
4 public LinkedList(Collection<? extends E> c);

2.2 常用方法

 1 // 获取个数。
 2 public int size();
 3 // 判断是否包含指定数据。
 4 public boolean contains(Object o);
 5 // 计算指定数据首次出现的下标。
 6 public int indexOf(Object o);
 7 // 计算指定数据最后出现的下标。
 8 public int lastIndexOf(Object o);
 9 // 获取指定下标的元素。
10 public E get(int index);
11 // 获取首节点元素，节点不存在会抛异常。
12 public E getFirst();
13 // 获取尾节点元素，节点不存在会抛异常。
14 public E getLast();
15 // 设置指定下标的指定元素，并返回旧元素。
16 public E set(int index, E element);
17 // 添加指定元素作为尾节点，并返回是否成功。
18 public boolean add(E e);
19 // 在指定位置添加指定元素。
20 public void add(int index, E element);
21 // 添加指定元素作为首节点。
22 public void addFirst(E e);
23 // 添加指定元素作为尾节点。
24 public void addLast(E e);
25 // 删除同指定元素相同的第一个元素，并返回是否成功。
26 public boolean remove(Object o);
27 // 删除指定位置的元素，并返回删除的元素。
28 public E remove(int index);
29 // 删除首节点元素，并返回删除的元素，节点不存在会抛异常。
30 public E removeFirst();
31 // 删除尾节点元素，并返回删除的元素，节点不存在会抛异常。
32 public E removeLast();

2.3 队列方法

 1 // 获取首节点元素，节点不存在会抛异常。
 2 public E element();
 3 // 获取首节点元素，节点不存在会返回null。
 4 public E peek();
 5 // 获取首节点元素，节点不存在会返回null。
 6 public E peekFirst();
 7 // 获取尾节点元素，节点不存在会返回null。
 8 public E peekLast();
 9 // 添加指定元素作为尾节点。
10 public boolean offer(E e);
11 // 添加指定元素作为首节点。
12 public boolean offerFirst(E e);
13 // 添加指定元素作为尾节点。
14 public boolean offerLast(E e);
15 // 删除首节点元素，并返回删除的元素，节点不存在会返回null。
16 public E poll();
17 // 删除首节点元素，并返回删除的元素，节点不存在会返回null。
18 public E pollFirst();
19 // 删除尾节点元素，并返回删除的元素，节点不存在会返回null。
20 public E pollLast();

2.4 栈方法

1 // 添加指定元素作为首节点。
2 public void push(E e);
3 // 删除首节点元素，并返回删除的元素，节点不存在会抛异常。
4 public E pop();

3 源码分析

3.1 属性

1 // 元素个数。
2 transient int size = 0;
3 // 头节点。
4 transient Node<E> first;
5 // 尾节点。
6 transient Node<E> last;

3.2 构造方法

1 // 空参构造器。
2 public LinkedList() {
3 }
4 // 传入了一个集合的构造器。
5 public LinkedList(Collection<? extends E> c) {
6     this();
7     addAll(c);
8 }

3.3 常用方法

  1 // 获取个数。
  2 public int size() {
  3     return size;
  4 }
  5 // 判断是否包含指定数据。
  6 public boolean contains(Object o) {
  7     return indexOf(o) != -1;
  8 }
  9 // 计算指定数据首次出现的下标。
 10 public int indexOf(Object o) {
 11     int index = 0;
 12     // 如果指定数据为null。
 13     if (o == null) {
 14         for (Node<E> x = first; x != null; x = x.next) {
 15             if (x.item == null)
 16                 return index;
 17             index++;
 18         }
 19     // 如果指定数据不为null。
 20     } else {
 21         for (Node<E> x = first; x != null; x = x.next) {
 22             if (o.equals(x.item))
 23                 return index;
 24             index++;
 25         }
 26     }
 27     return -1;
 28 }
 29 // 计算指定数据最后出现的下标。
 30 public int lastIndexOf(Object o) {
 31     int index = size;
 32     // 如果指定数据为null。
 33     if (o == null) {
 34         for (Node<E> x = last; x != null; x = x.prev) {
 35             index--;
 36             if (x.item == null)
 37                 return index;
 38         }
 39     // 如果指定数据不为null。
 40     } else {
 41         for (Node<E> x = last; x != null; x = x.prev) {
 42             index--;
 43             if (o.equals(x.item))
 44                 return index;
 45         }
 46     }
 47     return -1;
 48 }
 49 // 获取指定下标的元素。
 50 public E get(int index) {
 51     // 检查指定下标是否越界。
 52     checkElementIndex(index);
 53     // 遍历链表并获取指定下标对应的元素。
 54     return node(index).item;
 55 }
 56 // 获取首节点元素，节点不存在会抛异常。
 57 public E getFirst() {
 58     final Node<E> f = first;
 59     if (f == null)
 60         throw new NoSuchElementException();
 61     return f.item;
 62 }
 63 // 获取尾节点元素，节点不存在会抛异常。
 64 public E getLast() {
 65     final Node<E> l = last;
 66     if (l == null)
 67         throw new NoSuchElementException();
 68     return l.item;
 69 }
 70 // 设置指定下标的指定元素，并返回旧元素。
 71 public E set(int index, E element) {
 72     // 检查指定下标是否越界。
 73     checkElementIndex(index);
 74     // 遍历链表并获取指定下标对应的元素。
 75     Node<E> x = node(index);
 76     // 获取旧元素。
 77     E oldVal = x.item;
 78     // 替换元素。
 79     x.item = element;
 80     // 返回旧元素。
 81     return oldVal;
 82 }
 83 // 添加指定元素作为尾节点，并返回是否成功。
 84 public boolean add(E e) {
 85     linkLast(e);
 86     return true;
 87 }
 88 // 在指定位置添加指定元素。
 89 public void add(int index, E element) {
 90     // 检查指定下标是否越界。
 91     checkPositionIndex(index);
 92     // 如果指定位置为末尾，则直接末尾插入。
 93     if (index == size)
 94         linkLast(element);
 95     // 如果指定位置不为末尾，则插入到该位置所在的元素前面。
 96     else
 97         linkBefore(element, node(index));
 98 }
 99 // 添加指定元素作为首节点。
100 public void addFirst(E e) {
101     linkFirst(e);
102 }
103 // 添加指定元素作为尾节点。
104 public void addLast(E e) {
105     linkLast(e);
106 }
107 // 删除同指定元素相同的第一个元素，并返回是否成功。
108 public boolean remove(Object o) {
109     if (o == null) {
110         for (Node<E> x = first; x != null; x = x.next) {
111             if (x.item == null) {
112                 unlink(x);
113                 return true;
114             }
115         }
116     } else {
117         for (Node<E> x = first; x != null; x = x.next) {
118             if (o.equals(x.item)) {
119                 unlink(x);
120                 return true;
121             }
122         }
123     }
124     return false;
125 }
126 // 删除指定位置的元素，并返回删除的元素。
127 public E remove(int index) {
128     // 检查指定下标是否越界。
129     checkElementIndex(index);
130     // 找到指定位置的元素并删除。
131     return unlink(node(index));
132 }
133 // 删除首节点元素，并返回删除的元素，节点不存在会抛异常。
134 public E removeFirst() {
135     final Node<E> f = first;
136     if (f == null)
137         throw new NoSuchElementException();
138     return unlinkFirst(f);
139 }
140 // 删除尾节点元素，并返回删除的元素，节点不存在会抛异常。
141 public E removeLast() {
142     final Node<E> l = last;
143     if (l == null)
144         throw new NoSuchElementException();
145     return unlinkLast(l);
146 }

3.4 队列方法

 1 // 获取首节点元素，节点不存在会抛异常。
 2 public E element() {
 3     return getFirst();
 4 }
 5 // 获取首节点元素，节点不存在会返回null。
 6 public E peek() {
 7     final Node<E> f = first;
 8     return (f == null) ? null : f.item;
 9 }
10 // 获取首节点元素，节点不存在会返回null。
11 public E peekFirst() {
12     final Node<E> f = first;
13     return (f == null) ? null : f.item;
14 }
15 // 获取尾节点元素，节点不存在会返回null。
16 public E peekLast() {
17     final Node<E> l = last;
18     return (l == null) ? null : l.item;
19 }
20 // 添加指定元素作为尾节点。
21 public boolean offer(E e) {
22     return add(e);
23 }
24 // 添加指定元素作为首节点。
25 public boolean offerFirst(E e) {
26     addFirst(e);
27     return true;
28 }
29 // 添加指定元素作为尾节点。
30 public boolean offerLast(E e) {
31     addLast(e);
32     return true;
33 }
34 // 删除首节点元素，并返回删除的元素，节点不存在会返回null。
35 public E poll() {
36     final Node<E> f = first;
37     return (f == null) ? null : unlinkFirst(f);
38 }
39 // 删除首节点元素，并返回删除的元素，节点不存在会返回null。
40 public E pollFirst() {
41     final Node<E> f = first;
42     return (f == null) ? null : unlinkFirst(f);
43 }
44 // 删除尾节点元素，并返回删除的元素，节点不存在会返回null。
45 public E pollLast() {
46     final Node<E> l = last;
47     return (l == null) ? null : unlinkLast(l);
48 }

3.5 栈方法

1 // 入栈，添加指定元素作为首节点。
2 public void push(E e) {
3     addFirst(e);
4 }
5 // 出栈，删除首节点元素，并返回删除的元素，节点不存在会抛异常。
6 public E pop() {
7     return removeFirst();
8 }