LinkedList 底层采用 双链表 的形式存储数据，对比 ArrayList，其插入和删除更高效，其存储的 数据是有序、可以重复的，但不支持随机访问，LinkedList 是非线程安全的 。因为是双链表存储，因此不需要扩容操作。如果通过如下的方法实现多线程环境下的 LinkedList： Collections.synchronizedList(new ArrayList()); Collections.synchronizedList(new LinkedList());
另外，LinkedList 实现了 Deque 接口，因此具有双端队列的某些特性。

1、LinkedList 的存储结构
其存储结构如下：

LikedList 的 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; } }
2、LinkedList 源码分析
2.1 构造方法 // 构造函数 public LinkedList() { } // 从集合初始化 public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
2.2 add 添加元素 // 添加元素 public boolean add(E e) { linkLast(e); return true; } // 添加到最末尾 public void addLast(E e) { linkLast(e); } // 尾插 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++; } // 添加第一个元素 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++; }
如果是指定位置插入，注意：并不能通过 index 直接随机访问，index 只是相对于 first 的相对位置： // 指定位置插入 public void add(int index, E element) { // index 是否在 [0,size] 之间 checkPositionIndex(index); // 等于 size,直接插入在最后 if (index == size) linkLast(element); else // node(index) 通过这个方法找到 index 对应的 node // 然后插入在中间 linkBefore(element, node(index)); } // 在某个节点前插入 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++; }
插入集合的元素 // 从指定位置开始插入集合的元素 public boolean addAll(int index, Collection<? extends E> c) { // index 是否在 [0,size] 之间 checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; Node<E> 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<E> 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; }
2.3 根据位置 index 获取数据的方法
指定 index 位置获取数据的方法。 // 根据 index 返回元素，这不是随机访问，是通过遍历链表的方式 public E get(int index) { // index 是否合法 checkElementIndex(index); // 找到 index 对应的 node，并返回 node.item 的值 return node(index).item; } // 根据 index 找到对应位置的 node 的方法 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; } }
获取节点 first/last 的方法， 不会移除节点 ： get 方式如果 firs = null 会抛出异常 。 // 返回第一个元素 public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } // 返回最后的元素 public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }
如果是 peek 方法，first == null 不会抛出异常 : // 第一个 first public E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item; } // last 最后一个 public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; }
获取节点 first/last 的方法，会移除节点： // 第一个元素异常和返回第一个元素的 item public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } // 最后的元素异常和返回最后元素的 item public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); } // 返回 fist 的 item，并移除 public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }
根据 node 对象获取对应的 index 的方法，首次出现的 index，从头部开始往后找，没有找到返回 -1. // 根据 元素找到 index 的方法 public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }
根据 node 对象获取对应的 index 的方法，最后出现的 index，从尾部开始往前找，没有找到返回 -1. // 某个元素最后出现的 index，从尾部开始找 public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node<E> x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; }
2.4 是否包含某个元素 // 是否包含某个元素，也就是 index >= 0 public boolean contains(Object o) { return indexOf(o) >= 0; }
2.5 删除元素
remove 方式删除头尾节点，如果为 null 会抛出异常： // 移除第一个元素 public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } // 移除末尾的元素 public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); }
poll 方法移除头尾节点，如果为 null 不会抛出异常 // 第一个元素异常和返回第一个元素的 item public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } // 最后的元素异常和返回最后元素的 item public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); }
remove 移除指定的元素 // 移除某个元素，会遍历链表 public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } // 移除某个元素 E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> 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; }
删除指定 index 位置的节点 // 根据 index 移除某个 node 的方法 public E remove(int index) { checkElementIndex(index); // 弄得是否合法 return unlink(node(index)); }