概述是一种可以在任何位置进行高效地插入和移除操作的有序序列它是基于双向链表实现的。是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。实现 List 接口能对它进行队列操作。实现 Deque 接口(带可)即能将LinkedList当作双端队列使用。实现了Cloneable接口即覆盖了函数clone()能克隆。实现java.io.Serializable接口这意味着LinkedList支持序列化能通过序列化去传输。是非同步线程不安全的。数据结构如上图所示LinkedList底层使用的双向链表结构有一个头结点和一个尾结点双向链表意味着我们可以从头开始正向遍历或者是从尾开始逆向遍历并且可以针对头部和尾部进行相应的操作。特性1异步也就是非线程安全2双向链表。由于实现了list和Deque接口能够当作队列来使用。链表查询效率不高但是插入和删除这种操作性能好。3是顺序存取结构源码分析类的属性​// 实际元素个数链表长度transient int size 0; // 头结点transient NodeE first; // 尾结点transient NodeE last;LinkedList的属性非常简单一个头结点、一个尾结点、一个表示链表中实际元素个数的变量。构造方法两个构造方法(两个构造方法都是规范规定需要写的1空参构造函数** * Constructs an empty list. */public LinkedList() { }2有参构造函数//将集合c中的各个元素构建成LinkedList链表。public LinkedList(Collection? extends E c) { // 调用无参构造函数 this(); // 添加集合中所有的元素 addAll(c); }说明会调用无参构造函数并且会把集合中所有的元素添加到LinkedList中。内部类Node//根据前面介绍双向链表就知道这个代表什么了linkedList的奥秘就在这里。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; } }说明内部类Node就是实际的结点用于存放实际元素的地方。核心方法1 add()方法私有方法LinkedList 内部有几个关键的私有方法它们实现了链表的插入、删除等操作。比如在表头插入private void linkFirst(E e) { final NodeE f first; //先保存当前头节点 //创建一个新节点节点值为e前驱节点为空后继节点为当前头节点 final NodeE newNode new Node(null, e, f); first newNode; //让first指向新节点 if (f null) //如果链表原来为空把last指向这个唯一的节点 last newNode; else · //否则原来的头节点的前驱指向新的头节点 f.prev newNode; size; modCount; } 其实就是双向链表的插入操作调整指针的指向时间复杂度为 O(1) 学过数据结构的应该很容易看懂。其它还有几个类似的方法//尾部插入void linkLast(E e) { final NodeE l last; final NodeE newNode new Node(l, e, null); last newNode; if (l null) //如果链表原来为空让first指向这个唯一的节点 first newNode; else l.next newNode; size; modCount; }//中间插入void linkBefore(E e, NodeE succ) { // assert succ ! null; 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; }//删除头节点private E unlinkFirst(NodeE f) { // assert f first f ! null; final E element f.item; final NodeE next f.next; //先保存下一个节点 f.item null; f.next null; // help GC first next; //让first指向下一个节点 if (next null) //如果下一个节点为空说明链表原来只有一个节点现在成空链表了要把last指向null last null; else //否则下一个节点的前驱节点要置为null next.prev null; size--; modCount; return element; }//删除尾节点 private E unlinkLast(NodeE l) { // assert l last l ! null; final E element l.item; final NodeE prev l.prev; //保存前一个节点 l.item null; l.prev null; // help GC last prev; //last指向前一个节点 if (prev null) //与头节点删除一样判断是否为空 first null; else prev.next null; size--; modCount; return element; }//从链表中间删除节点 E unlink(NodeE x) { // assert x ! null; final E element x.item; final NodeE next x.next; //保存前驱节点 final NodeE prev x.prev; //保存后继节点 if (prev null) { //前驱为空说明删除的是头节点first要指向下一个节点 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; }1add(E)说明add函数用于向LinkedList中添加一个元素并且添加到链表尾部。具体添加到尾部的逻辑是由linkLast函数完成的。public boolean add(E e) { // 添加到末尾 linkLast(e); return true; }LinkLast()//尾部插入/** * Links e as last element. */void linkLast(E e) { final NodeE l last; //临时节点l(L的小写)保存last也就是l指向了最后一个节点 final NodeE newNode new Node(l, e, null);//将e封装为节点并且e.prev指向了最后一个节点 last newNode;//newNode成为了最后一个节点所以last指向了它 if (l null) //判断是不是一开始链表中就什么都没有如果没有则newNode就成为了第一个节点first和last都要指向它 first newNode; else //正常的在最后一个节点后追加那么原先的最后一个节点的next就要指向现在真正的最后一个节点原先的最后一个节点就变成了倒数第二个节点 l.next newNode; size;//添加一个节点size自增 modCount; }举例ListInteger lists new LinkedListInteger();lists.add(e1);lists.add(e2);一开始first和last都为null此时链表什么都没有当第一次调用该方法后first和last均指向了第一个新加的节点E1第二次调用该方法加入新节点E2。首先将last引用赋值给l接着new了一个新节点E2并且E2的prve指向l接着将新节点E2赋值为last接着判断lnull? 所以走的else语句将l的next引用指向新节点E2最后size1modCount1退出该方法局部变量l销毁公开的方法几乎都是调用上面几个方法实现的例如 add 方法public boolean add(E e) { linkLast(e); return true; }public boolean add(E e) { linkLast(e); return true; }public void add(int index, E element) { checkPositionIndex(index); if (index size) linkLast(element); else linkBefore(element, node(index)); }add(int index, E element)的逻辑稍显复杂可以分成两部1.先根据index找到要插入的位置2.修改引用完成插入操作。//add(int index, E element)public void add(int index, E element) { checkPositionIndex(index);//index 0 index size; if (index size)//插入位置是末尾包括列表为空的情况 add(element); else{ NodeE succ node(index);//1.先根据index找到要插入的位置 //2.修改引用完成插入操作。 final NodeE pred succ.prev; final NodeE newNode new Node(pred, e, succ); succ.prev newNode; if (pred null)//插入位置为0 first newNode; else pred.next newNode; size; } }上面代码中的node(int index)函数有一点小小的trick因为链表双向的可以从开始往后找也可以从结尾往前找具体朝那个方向找取决于条件index (size 1)也即是index是靠近前端还是后端。2).remove()方法也有两个版本一个是删除跟指定元素相等的第一个元素remove(Object o)另一个是删除指定下标处的元素remove(int index)。remove(int index) public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }remove(Object o)//首先通过看上面的注释我们可以知道如果我们要移除的值在链表中存在多个一样的值那么我们会移除index最小的那个也就是最先找到的那个值如果不存在这个值那么什么也不做public boolean remove(Object o) { //这里可以看到linkedList也能存储null if (o null) { //循环遍历链表直到找到null值然后使用unlink移除该值。下面的这个else中也一样 for (NodeE x first; x ! null; x x.next) { if (x.item null) { unlink(x); return true; } } } else { for (NodeE x first; x ! null; x x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }第一个 remove(int index) 方法同样要调用 node(index) 寻找节点。而第二个方法 remove(Object o) 是删除指定元素这个方法要依次遍历节点进行元素的比较最坏情况下要比较到最后一个元素比调用 node 方法更慢时间复杂度为 O(n) 。另外从这个方法可以看出 LinkedList 的元素可以是 null 。3).get(index)get(index)查询元素的方法//这里没有什么重点还是在node(index)中public E get(int index) { checkElementIndex(index); return node(index).item; }node(index)/** * Returns the (non-null) Node at the specified element index. *///这里查询使用的是先从中间分一半查找 NodeE node(int index) { // assert isElementIndex(index);//:*2的几次方 “”:/2的几次方例如size1size*2的1次方//这个if中就是查询前半部分 if (index (size 1)) {//indexsize/2 NodeE x first; for (int i 0; i index; i) x x.next; return x; } else {//前半部分没找到所以找后半部分 NodeE x last; for (int i size - 1; i index; i--) x x.prev; return x; } }4).set(int index, E element)方法将指定下标处的元素修改成指定值也是先通过node(int index)找到对应下表元素的引用然后修改Node中item的值。public E set(int index, E element) { checkElementIndex(index); Node E x node(index); E oldVal x.item; x.item element; //替换新值 return oldVal; }5).indexOf(Object o)//这个很简单就是通过实体元素来查找到该元素在链表中的位置。跟remove中的代码类似只是返回类型不一样。public int indexOf(Object o) { int index 0; if (o null) { for (NodeE x first; x ! null; x x.next) { if (x.item null) return index; index; } } else { for (NodeE x first; x ! null; x x.next) { if (o.equals(x.item)) return index; index; } } return -1; }总结1linkedList本质上是一个双向链表通过一个Node内部类实现的这种链表结构。2能存储null值3跟arrayList相比较就真正的知道了LinkedList在删除和增加等操作上性能好而ArrayList在查询的性能上好4从源码中看它不存在容量不足的情况5linkedList不光能够向前迭代还能像后迭代并且在迭代的过程中可以修改值、添加值、还能移除值。6linkedList不光能当链表还能当队列使用这个就是因为实现了Deque接口。