简介LinkedList 底层是基于双向链表实现的内部有三个属性size用来存储元素个数first指向链表头节点last指向链表尾节点。public class LinkedListE extends AbstractSequentialListE implements ListE, DequeE, Cloneable, java.io.Serializable { // 元素个数 transient int size 0; // 头节点 transient NodeE first; // 尾节点 transient NodeE last; }头尾节点都是由 Node 节点组成Node 节点表示双向链表的一个元素内部结构如下private static class NodeE { // 存储元素数据 E item; // 后继节点指向下一个元素 NodeE next; // 前驱节点指向上一个元素 NodeE prev; // 构造函数 Node(NodeE prev, E element, NodeE next) { this.item element; this.next next; this.prev prev; } }类图架构«interface»CollectionEadd(E e) : booleanremove(Object o) : booleancontains(Object o) : booleansize() : intisEmpty() : boolean«interface»ListEget(int index) : Eadd(int index, E e) : voidremove(int index) : EindexOf(Object o) : int«interface»DequeEaddFirst(E e) : voidaddLast(E e) : voidremoveFirst() : EremoveLast() : EpeekFirst() : EpeekLast() : E«abstract»AbstractSequentialListELinkedListE-transient int size-transient NodeE first-transient NodeE last-static class NodeLinkedList()add(E e) : booleanadd(int index, E e) : voidget(int index) : Eremove(int index) : EaddFirst(E e) : voidaddLast(E e) : voidremoveFirst() : EremoveLast() : E-node(int index) : Node-linkLast(E e) : void-linkFirst(E e) : void-unlink(Node x) : ELinkedList 实现了List接口提供了集合操作的常用方法当然也包含随机访问的方法只不过没有像ArrayList那样实现RandomAccess接口LinkedList 提供的随机访问方法时间复杂度不是常量级别的。LinkedList 还实现了Deque接口Deque 是double ended queue的缩写读音是/dek/读错就尴尬了。Deque 是双端队列可以在头尾进行插入和删除操作兼具栈和队列的性质。Deque 提供了大量增删查方法目的是区分不同语义对于添加操作addFirst()在队列满时会抛出异常而offerFirst()则返回false对于删除和查询以poll/peek开头的方法在元素不存在时返回null而以remove/get/element开头的方法则会抛出异常。常用方法分类如下操作类型头部操作抛出异常头部操作返回特殊值尾部操作抛出异常尾部操作返回特殊值添加addFirst(e)、push(e)offerFirst(e)addLast(e)、add(e)offerLast(e)、offer(e)删除removeFirst()、remove()、pop()pollFirst()、poll()removeLast()pollLast()查询getFirst()、element()peekFirst()、peek()getLast()peekLast()核心工作原理add(e) 尾部添加addFirst(e) 头部添加add(index,e) 任意位置是否remove 删除removeFirstremoveLastremove(index)remove(Object)找到未找到get(index)getFirst/getLast初始化: firstnull, lastnull, size0添加元素?linkLast: 新节点prev指向原last\nlast更新为新节点\n原last.next指向新节点\nsize modCountlinkFirst: 新节点next指向原first\nfirst更新为新节点\n原first.prev指向新节点\nsize modCountindex size?node(index): 按index与size/2比较\n决定从头或尾遍历linkBefore: 在目标节点前插入新节点\n修改前后节点指针\nsize modCount按位置还是按值?unlinkFirst: 断开头节点引用\nitem和next置null\nsize-- modCountunlinkLast: 断开尾节点引用\nitem和prev置null\nsize-- modCountnode(index) 定位节点unlink: 断开前后节点引用\nitem/prev/next置null\nsize-- modCount从头/尾遍历查找equals返回false查询元素?node(index) 定位节点返回 node.item直接返回 first.item / last.item初始化LinkedList 只有一个构造方法——无参构造并不能像ArrayList那样指定初始容量。ListInteger list new LinkedList();构造方法的底层实现也是一个空方法没有做任何操作public LinkedList() { }这意味着 LinkedList 创建时不会预先分配任何节点所有节点都是在添加元素时才动态创建。 核心提示LinkedList 的无参构造是真正的零成本初始化——它不分配任何内存。这与 ArrayList 不同ArrayList 无参构造也只是赋值空数组引用同样零分配。但 LinkedList 每次add都要new Node()意味着每次添加都是一次独立的堆分配在大量元素场景下这会导致内存碎片化且每个节点的 GC 追踪开销更大。添加元素添加元素的方法根据位置区分共有三种在头部添加、在尾部添加、在任意位置添加。方法含义不返回值返回布尔值在头部添加addFirst(e)、push(e)offerFirst(e)在尾部添加addLast(e)add(e)、offer(e)、offerLast(e)在任意位置添加add(index, e)-先看一下使用最多的add(e)方法底层实现// 添加元素 public boolean add(E e) { // 在末尾添加元素 linkLast(e); return true; } // 在末尾添加元素 void linkLast(E e) { // 1. 获取尾节点 final NodeE l last; // 2. 初始化新节点 final NodeE newNode new Node(l, e, null); // 3. 追加到末尾 last newNode; if (l null) { first newNode; } else { l.next newNode; } size; modCount; }linkLast的核心逻辑保存原尾节点 → 创建新节点前驱指向原尾节点 → 更新last指针 → 如果链表为空则同时设置first→ 否则将原尾节点的next指向新节点。再看一个从头部添加元素的push()// 添加元素 public void push(E e) { // 在头部添加元素 addFirst(e); } // 在头部添加元素 public void addFirst(E e) { linkFirst(e); } // 在头部添加元素底层私有实现 private void linkFirst(E e) { // 1. 获取头节点 final NodeE f first; // 2. 初始化新节点 final NodeE newNode new Node(null, e, f); // 3. 追加到头部 first newNode; if (f null) { last newNode; } else { f.prev newNode; } size; modCount; }linkFirst与linkLast逻辑对称保存原头节点 → 创建新节点后继指向原头节点 → 更新first指针 → 如果链表为空则同时设置last→ 否则将原头节点的prev指向新节点。最后看在任意位置添加的add(index, e)底层实现// 在下标index位置添加元素 public void add(int index, E element) { // 检查下标是否越界 checkPositionIndex(index); // 如果index等于链表长度则添加到末尾 if (index size) { linkLast(element); } else { // 添加到指定位置前面先找到index位置的元素 linkBefore(element, node(index)); } } // 在当前元素前面添加新元素 void linkBefore(E e, NodeE succ) { final NodeE pred succ.prev; // 创建新节点并将新节点插入到当前节点之前 final NodeE newNode new Node(pred, e, succ); succ.prev newNode; if (pred null) { first newNode; } else { pred.next newNode; } size; modCount; }这里调用了checkPositionIndex进行越界检查允许index size因为可以在末尾追加// 检查位置下标是否越界 private void checkPositionIndex(int index) { if (!isPositionIndex(index)) { throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } } // 判断位置下标是否合法 private boolean isPositionIndex(int index) { return index 0 index size; }add(index, e)内部还依赖了node(index)方法来定位节点这个方法在查询部分详细分析。查询元素查询元素的方法按位置区分共有三种查询头节点、查询尾节点、查询任意位置元素。方法含义如果不存在则返回null如果不存在则抛异常查询头部peek()、peekFirst()getFirst()、element()查询尾部peekLast()getLast()查询任意位置-get(index)看一下从头查询的element()方法的底层实现// 查询元素 public E element() { return getFirst(); } // 获取第一个元素 public E getFirst() { final NodeE f first; if (f null) { throw new NoSuchElementException(); } return f.item; }再看一个查询尾节点的getLast()方法的底层实现// 获取最后一个元素 public E getLast() { final NodeE l last; if (l null) { throw new NoSuchElementException(); } return l.item; }头尾查询都是 O(1) 时间复杂度因为直接访问first和last指针。再看一个查询任意位置的方法get(index)的底层实现