概述
本文是基于jdk8_271源码进行分析的。
LinkedList底层是基于链表实现。链表没有长度限制，内存地址不需要固定长度，也不需要是连续的地址来进行存储，只需要通过引用来关联前后元素即可完成整个链表的连续。所以链表的优点就是添加删除元素比较快，只需要移动指针，并且不需要判断扩容。缺点就是因为没有索引，所以在查询和遍历元素时候比较慢。
使用场景：在增删操作使用较多，查询遍历操作使用较少情况下比较适合去使用；例如：拿来当栈使用。
数据结构
继承实现关系
1 public class LinkedList<E> 2 extends AbstractSequentialList<E> 3 implements List<E>, Deque<E>, Cloneable, java.io.Serializable
- AbstractSequentialList ：本质上面与继承 AbstractList 没有什么区别，AbstractSequentialList 完善了 AbstractList 中没有实现的方法。
- List：实现List接口。
- Deque：实现Deque队列接口，拥有作为双端队列（队列和栈）的功能。
- Cloneable：重写clone()方法，通过创建新的LinkedList 对象，遍历拷贝数据进行对象拷贝。
- Serializable：重写read/writeObject() 方法实现序列化。
静态内部类
为什么Node这个类是静态的？答案是：这跟内存泄露有关，Node类是在LinkedList类中的，也就是一个内部类，若不使用static修饰，那么Node就是一个普通的内部类，在java中，一个普通内部类在实例化之后，默认会持有外部类的引用，这就有可能造成内存泄露（内部类与外部类生命周期不一致时）。但使用static修饰过的内部类（称为静态内部类），就不会有这种问题。
非静态内部类会自动生成一个构造器依赖于外部类：也是内部类可以访问外部类的实例变量的原因。
静态内部类不会生成，访问不了外部类的实例变量，只能访问类变量。
1 private static class Node<E> { 2 E item; 3 Node<E> next; // 后继节点 4 Node<E> prev; // 前置节点 5 6 Node(Node<E> prev, E element, Node<E> next) { 7 this.item = element; 8 this.next = next; 9 this.prev = prev; 10 } 11 }
基本属性
1 // 元素数量 2 transient int size = 0; 3 // 头结点 4 transient Node<E> first; 5 // 尾节点 6 transient Node<E> last;
构造方法
1 public LinkedList() { 2 } 3 4 public LinkedList(Collection<? extends E> c) { 5 this(); 6 addAll(c); 7 }
主要方法解析
获取元素
peek()：队列的查，获取队头元素。
1 public E get(int index) { // 根据索引获取 2 checkElementIndex(index); 3 return node(index).item; 4 } 5 Node<E> node(int index) { 6 // assert isElementIndex(index); 7 // 利用二分法查找；小于中间数从头结点开始找，否则从尾节点开始找 8 if (index < (size >> 1)) { 9 Node<E> x = first; 10 for (int i = 0; i < index; i++) 11 x = x.next; 12 return x; 13 } else { 14 Node<E> x = last; 15 for (int i = size - 1; i > index; i--) 16 x = x.prev; 17 return x; 18 } 19 } 20 // 获取队头元素 ，但是不删除队列的头元素（双端队列Deque中的方法） 21 public E getFirst() { 22 final Node<E> f = first; 23 if (f == null) 24 throw new NoSuchElementException(); 25 return f.item; 26 } 27 // 获取队尾元素，但是不删除队列的尾元素（实现双端队列Deque中的方法） 28 public E getLast() { 29 final Node<E> l = last; 30 if (l == null) 31 throw new NoSuchElementException(); 32 return l.item; 33 } 34 35 // 队列的查。获取队头元素。 36 public E peek() { 37 final Node<E> f = first; 38 return (f == null) ? null : f.item; 39 }
添加元素
offer()：队列的增，添加队尾元素，底层实现是调用add()->linkLast()。
push()：栈的增，把元素压入栈中，添加对头元素，底层实现是调用addFirst()->linkFirst()。
1 // 添加元素，默认在链表尾部添加 2 public boolean add(E e) { 3 linkLast(e); 4 return true; 5 } 6 // 指定索引添加元素 7 public void add(int index, E element) { 8 checkPositionIndex(index); // 检验下标是否越界 9 10 if (index == size) // 如果要插入的索引等于现有元素长度，说明是要在尾部插入元素 11 linkLast(element); 12 else // 否则，获取该索引节点，在该节点之前插入元素 13 linkBefore(element, node(index)); 14 } 15 16 public boolean addAll(Collection<? extends E> c) { 17 return addAll(size, c); 18 } 19 public boolean addAll(int index, Collection<? extends E> c) { 20 checkPositionIndex(index); // 检验下标是否越界 21 22 Object[] a = c.toArray(); 23 int numNew = a.length; 24 if (numNew == 0) 25 return false; 26 27 // pred:前置节点，在该节点之后插入元素。succ：该索引位节点。 28 Node<E> pred, succ; 29 if (index == size) { 30 succ = null; 31 pred = last; 32 } else { 33 succ = node(index); 34 pred = succ.prev; 35 } 36 // 将数组设置为链表 37 for (Object o : a) { 38 @SuppressWarnings("unchecked") E e = (E) o; 39 Node<E> newNode = new Node<>(pred, e, null); // 新建一个节点，指向前置节点 40 if (pred == null) // 如果前置节点为空，说明该链表为空。将头节点指向当前节点 41 first = newNode; 42 else // 前置节点的后继节点指向当前节点 43 pred.next = newNode; 44 pred = newNode; // 将当前节点设置为前置节点，供后面需要插入的节点使用 45 } 46 47 if (succ == null) { 48 last = pred; 49 } else { 50 pred.next = succ; 51 succ.prev = pred; 52 } 53 54 size += numNew; 55 modCount++; 56 return true; 57 } 58 59 // 添加元素到头结点（实现双端队列Deque中的方法） 60 public void addFirst(E e) { 61 linkFirst(e); 62 } 63 private void linkFirst(E e) { 64 final Node<E> f = first; // 原头节点 65 final Node<E> newNode = new Node<>(null, e, f); // 新建一个节点，要添加的元素 66 first = newNode; // 将头结点指向该新建的节点 67 if (f == null) // 如果原头结点为空，说明原链表为空。这是添加的第一个元素，将尾结点也指向该新建的节点 68 last = newNode; 69 else // 如果原头结点不为空，则将原头结点的前置节点指向该新建的节点 70 f.prev = newNode; 71 size++; // 元素数量+1 72 modCount++; // 修改次数+1 73 } 74 // 添加元素到尾结点（实现双端队列Deque中的方法） 75 public void addLast(E e) { 76 linkLast(e); 77 } 78 void linkLast(E e) { 79 final Node<E> l = last; // 原尾结点 80 final Node<E> newNode = new Node<>(l, e, null); // 新建一个节点，要添加的元素 81 last = newNode; // 将尾结点指向该新建的节点 82 if (l == null) // 如果尾头结点为空，说明原链表为空。这是添加的第一个元素，将头结点也指向该新建的节点 83 first = newNode; 84 else // 如果原尾结点不为空，则将原尾结点的后继节点指向该新建的节点 85 l.next = newNode; 86 size++; // 元素数量+1 87 modCount++; // 修改次数+1 88 } 89 90 // 队列的添加方法 91 public boolean offer(E e) { 92 return add(e); 93 } 94 95 // 栈的添加方法 96 public void push(E e) { 97 addFirst(e); 98 }
删除元素
poll()：队列的删，获取对头元素并且对头元素删除。
pop()：栈的删，返回的是栈顶元素并将栈顶元素删除。
1 public boolean remove(Object o) { 2 if (o == null) { 3 for (Node<E> x = first; x != null; x = x.next) { 4 if (x.item == null) { 5 unlink(x); 6 return true; 7 } 8 } 9 } else { 10 for (Node<E> x = first; x != null; x = x.next) { 11 if (o.equals(x.item)) { 12 unlink(x); 13 return true; 14 } 15 } 16 } 17 return false; 18 } 19 public E remove(int index) { 20 checkElementIndex(index); 21 return unlink(node(index)); 22 } 23 // 将该节点前置节点的下一个节点指向该节点后继节点，将该节点后继节点的上一个节点指向该节点前置节点。并将该节点置为空 24 E unlink(Node<E> x) { 25 // assert x != null; 26 final E element = x.item; 27 final Node<E> next = x.next; 28 final Node<E> prev = x.prev; 29 30 if (prev == null) { 31 first = next; 32 } else { 33 prev.next = next; 34 x.prev = null; 35 } 36 37 if (next == null) { 38 last = prev; 39 } else { 40 next.prev = prev; 41 x.next = null; 42 } 43 44 x.item = null; 45 size--; 46 modCount++; 47 return element; 48 } 49 // 将头结点的下一个节点设置为新的头结点，并将原头节点置为空 50 private E unlinkFirst(Node<E> f) { 51 // assert f == first && f != null; 52 final E element = f.item; 53 final Node<E> next = f.next; 54 f.item = null; 55 f.next = null; // help GC 56 first = next; 57 if (next == null) 58 last = null; 59 else 60 next.prev = null; 61 size--; 62 modCount++; 63 return element; 64 } 65 66 // 将尾结点的上一个节点设置为新的尾结点，并将原尾节点置为空 67 private E unlinkLast(Node<E> l) { 68 // assert l == last && l != null; 69 final E element = l.item; 70 final Node<E> prev = l.prev; 71 l.item = null; 72 l.prev = null; // help GC 73 last = prev; 74 if (prev == null) 75 first = null; 76 else 77 prev.next = null; 78 size--; 79 modCount++; 80 return element; 81 } 82 83 public E remove() { 84 return removeFirst(); 85 } 86 87 // 队列的删除方法 88 public E poll() { 89 final Node<E> f = first; 90 return (f == null) ? null : unlinkFirst(f); 91 } 92 // 栈的删除方法 93 public E pop() { 94 return removeFirst(); 95 }
附录
LinkedList源码详细注释Github地址：https://github.com/y2ex/jdk-source/blob/jdk1.8.0_271/src/main/java/java/util/LinkedList.java
jdk1.8源码Github地址：https://github.com/y2ex/jdk-source/tree/jdk1.8.0_271