注：本系列文章使用的jdk版本为java8LinkedList类图如下：LinkedList底层由双向链表实现。链表就像火车。每辆车都包含一辆车和一个到下一辆车的连接点。双向链表的每个节点不仅有一个指向下一个节点的指针，还有一个指向前一个节点的指针。LinkedList源码中有一个Node静态类，源码如下：privatestaticclassNode{Eitem;Nodenext;Nodeprev;Node(Nodeprev,Eelement,Nodenext){this.item=element;this.next=next;this.prev=prev;}}一个Node节点包含三部分，即item：数据next：指向下一个节点的指针prev：指向上一个节点的指针LinkedList的主要变量如下：//集合中的元素个数transientintsize=0;/***第一个节点的指针。*不变量：(first==null&&last==null)||*(first.prev==null&&first.item!=null)*/transientNodefirst;/***指向结束节点的指针。*不变量:(first==null&&last==null)||*(last.next==null&&last.item!=null)*/transientNodelast;1、添加元素LinkedList支持在任意节点位置添加元素。它不仅提供了集合中常用的add()方法，还提供了addFirst()和addLast()。add()方法默认调用addLast()方法。即默认是在链表的末尾插入元素。add()方法源码：publicbooleanadd(Ee){linkLast(e);returntrue;}1.1最后插入元素linkLast()源码如下：voidlinkLast(Ee){finalNodel=last;finalNodenewNode=newNode<>(l,e,null);last=newNode;if(l==null)first=newNode;elsel.next=newNode;size++;modCount++;}让我们画一张图来演示如何在链表末尾插入元素：if源码中if语句对应的链表中没有元素。如果没有元素，则新添加的节点是链表中的唯一元素。它既是第一个节点又是最后一个节点。前一个元素的指针和后一个元素的指针都为空。这里注意头节点不是首节点，头节点只是标识链表的地址。如果源码中else语句对应的链表中有元素。首先将新加入的元素作为Last节点，然后将原Last节点的next指向新节点。elsel.next=新节点；有图胜于序，画了图就明白了。1.2头部插入元素linkFirst()源码如下：privatevoidlinkFirst(Ee){finalNodef=first;finalNodenewNode=newNode<>(null,e,f);first=newNode;if(f==null)last=newNode;elsef.prev=newNode;size++;modCount++;}我们按照上图来解读源码，先把第一个节点赋给中间变量f，把新节点newNode赋给第一个节点。如果链表没有元素，则Last节点和First节点都是新插入的节点newNode，否则，原First节点的头指针指向新节点。2.删除元素LinkedList提供的删除方式是基于索引和元素的删除。此外，它还提供了删除第一个元素和最后一个元素的方法。这里只分析根据索引删除的方法。publicEremove(intindex){checkElementIndex(index);returnunlink(node(index));}checkElementIndex(index)方法用于判断传递过来的索引值是否合法，如果不合法，一个数组out-of-将抛出边界异常。关注unlink(node(index))方法如何删除元素。node(index)方法源码：node(index)方法是根据index获取index位置的节点Nodenode(intindex){//assertisElementIndex(index);//如果指定下标>1)){Nodex=first;for(inti=0;ix=last;for(inti=size-1;i>index;i--)x=x.prev;returnx;}}unlink(Nodex)源码如下：Eunlink(Nodex){//assertx!=null;finalEelement=x.item;finalNodenext=x.next;finalNodeprev=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++;returnelement;}画图分析删除的原理：假设删除了第一个元素：那么它的prev==NULL，我们需要添加它的下一个元素（第二个在图）用作第一个元素。假设删除了最后一个元素，那么它的next==null，我们需要用它的前一个元素（图中第二个）作为最后一个元素。如果是中间的任意一个元素，则需要将其前一个元素的next指针指向其下一个元素，同时将其下一个元素的prev指针指向其前一个元素。3.总结LinkedList的底层是由一个双向链表实现的。因为它是由链表实现的，所以它不仅存储数据，还存储指针，所以内存开销比ArrayList大。删除一个元素不需要移动其他元素，只需要改变指针的指向，所以删除效率更高，而且没有实现RandomAccess接口，所以使用迭代器遍历比for循环更高效。LinkedList也支持插入重复值和空值，同样是线程不安全的。本文转载自微信公众号“Java之旅”，可通过以下二维码关注。转载本文请联系Java之旅公众号。
