LinkedList是什么？ 在上一章节中我们讲到了数组集合 ArrayList ，这节我们接着讲集合中的另一个成员 LinkedList ，就像它的名字说的一样，这是一个链表，在C语言中我们知道，链表是我们通过结构体实现的，那么在 Java 中我们应该怎样实现呢？
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; }}复制代码
这就是 LinkedList 用来保存元素的节点，Node类是 LinkedList 中的静态内部类，每一个 Node 对象代表一个元素，它具有三个属性，分别是用来存储元素的 item 对象，用来存储它上一个节点的 prev 对象，用来存储它下一个节点的 next 对象，那么我们就知道了 LinkedList 的内部是一个双链表。现在我们只需要知道 LinkedList 是怎样操作这些节点就行了。
首先我们来看看它的构造器：
构造器： /** * Constructs an empty list. */ public LinkedList() { }
/** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */public LinkedList(Collection c) { this(); addAll(c);}复制代码 LinkedList 不像 ArrayList 那样在初始化的时候传入集合容量，因为它的容量是可变的，与不可变的数组不同。在第二个构造器中我们看到当传入一个集合对象的时候会调用 addAll() 方法，那么我们接着看看 addAll() 的源码：
/** * Appends all of the elements in the specified collection to the end of * this list, in the order that they are returned by the specified * collection's iterator. The behavior of this operation is undefined if * the specified collection is modified while the operation is in * progress. (Note that this will occur if the specified collection is * this list, and it's nonempty.) * * @param c collection containing elements to be added to this list * @return {@code true} if this list changed as a result of the call * @throws NullPointerException if the specified collection is null */public boolean addAll(Collection c) { return addAll(size, c);}/** * Inserts all of the elements in the specified collection into this * list, starting at the specified position. Shifts the element * currently at that position (if any) and any subsequent elements to * the right (increases their indices). The new elements will appear * in the list in the order that they are returned by the * specified collection's iterator. * * @param index index at which to insert the first element * from the specified collection * @param c collection containing elements to be added to this list * @return {@code true} if this list changed as a result of the call * @throws IndexOutOfBoundsException {@inheritDoc} * @throws NullPointerException if the specified collection is null */public boolean addAll(int index, Collection c) { checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; Node 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 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;}复制代码 我们从源码中看到：在 addAll() 方法中和 ArrayList 一样，首先调用传入集合的 toArray() 方法将集合中的元素转到数组中便于遍历，然后回先判断一下插入的位置是否在链表尾部（如果刚开始链表为空的话，那么也就等于是在链表尾部插入），然后根据两种情况进行不同的操作。最后将 size 值更新。
成员属性： transient int size = 0;
/** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */transient Nodefirst;/** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */transient Node last;复制代码
我们再来看看 LinkedList 中的成员属性：size 值表示链表中的实际元素个数，跟 ArrayList的 size 值一样。
first 对象代表的是整个链表的头节点，last 对象代表的是整个链表的尾节点。
方法add()： /** * Links e as last element. / void linkLast(E e) { final Node l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } /* * Appends the specified element to the end of this list. * *
This method is equivalent to {@link #addLast}. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link Collection#add}) */ public boolean add(E e) { linkLast(e); return true; }
再调用 add() 方法的时候，其实就是在调用 linkLast() 方法，定义两个节点常量分别对应链表的的尾节点和新插入的节点，然后将新节点插入尾部，判断链表是否为空，若为空则将链表的手节点和尾节点都指向新加入的节点，否则将原来尾节点与新节点相连。
在 LinkedList 中还有一个方法和 add() 方法相同：
方法 offer()、offerFirst()、offerLast(): /** * Adds the specified element as the tail (last element) of this list. * * @param e the element to add * @return {@code true} (as specified by {@link Queue#offer}) * @since 1.5 */ public boolean offer(E e) { return add(e); }
// Deque operations/** * Inserts the specified element at the front of this list. * * @param e the element to insert * @return {@code true} (as specified by {@link Deque#offerFirst}) * @since 1.6 */public boolean offerFirst(E e) { addFirst(e); return true;}/** * Inserts the specified element at the end of this list. * * @param e the element to insert * @return {@code true} (as specified by {@link Deque#offerLast}) * @since 1.6 */public boolean offerLast(E e) { addLast(e); return true;}复制代码 我们在 offer() 方法中就可以看到，它内部就是调用了 add() 方法，那为什么有了 add() 方法还要一个和它功能相同的 offer() 方法呢？这是因为这两个方法继承自不同的接口：add() 方法继承自 Collection 接口，而 offer() 方法继承自 Deque 接口，Collection 是集合接口，而 Deque 接口代表双向队列，LinkedList 在继承了这两个接口后必须重写这两个接口中的方法，所以就写的一样咯。offerFirst() 方法表示在链表首部加入一个节点元素，而offerLast() 方法就和 add() 方法一样，在尾部添加节点元素，我们看看这两个方法的执行流程：
/** * Inserts the specified element at the beginning of this list. * * @param e the element to add */public void addFirst(E e) { linkFirst(e);}/** * Appends the specified element to the end of this list. * * This method is equivalent to {@link #add}. * * @param e the element to add */public void addLast(E e) { linkLast(e);}/** * Links e as first element. */private void linkFirst(E e) { final Node
f = first; final Node newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++;}/** * Links e as last element. */void linkLast(E e) { final Node l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++;}复制代码 它们最终调用的还是 linkFirst() 和 linkLast() 方法。
方法 remove(int index)、remove(Object o)： LinkedList提供两种删除指定节点的方式：
（1）按节点下标删除：
/** * Removes the element at the specified position in this list. Shifts any * subsequent elements to the left (subtracts one from their indices). * Returns the element that was removed from the list. * * @param index the index of the element to be removed * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */public E remove(int index) { checkElementIndex(index); return unlink(node(index));}private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}/** * Tells if the argument is the index of an existing element. */private boolean isElementIndex(int index) { return index >= 0 && index < size;}/** * Returns the (non-null) Node at the specified element index. */Node node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; }}/** * Unlinks non-null node x. */E unlink(Node x) { // assert x != null; final E element = x.item; final Node next = x.next; final Node 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;}复制代码 可以看到调用 remove(int index) 方法时会先用 checkElementIndex() 和 isElementIndex() 方法检查给定下标的合法性，如果给定的下标 小于0 或 超出链表的长度 checkElementIndex() 方法就会抛出一 IndexOutOfBoundsException(outOfBoundsMsg(index)) 异常（下标越界异常）。如果下标合法的话则继续调用 node(int index) 方法，方法中会首先判断给定的下标在链表的前半段还是后半段（index << 1 等于 index/2），若在前半段：从链表头部遍历；若在后半段：从链表尾部向前遍历（可能这就是为什么用双链表的原因吧），遍历到给定下表的节点后返回此节点给 unlink(Node x) 方法删除节点：分删除头节点和其他节点两种情况，在这里就不做赘述了。
（2）按节点值删除：
/** * Removes the first occurrence of the specified element from this list, * if it is present. If this list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * {@code i} such that * (o==null ? get(i)==null : o.equals(get(i))) * (if such an element exists). Returns {@code true} if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return {@code true} if this list contained the specified element */ public boolean remove(Object o) { if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }复制代码 按节点值删除因为 null 值的特性，所以需要先判断给定的节点值是否是 null 值，若是则遍历链表找到第一个值为 null 的节点删除，若不是，则用equals() 对比节点值和给定值。此中删除方法只删除第一个匹配到的节点。
方法 clear(): /** * Removes all of the elements from this list. * The list will be empty after this call returns. */ public void clear() { // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even if there is a reachable Iterator for (Node x = first; x != null; ) { Node next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; }
此方法负责清空链表所有节点，从头部遍历链表节点，一个一个清空 Node 对象，代码中 x.item = null;x.next = null;x.prev = null都是负责 help to gc的。