简介LinkedList和ArrayList数据结构完全不同，ArrayList底层是数组结构，而LinkedList底层是链表结构，可以进行高效的插入和移除运算，它基于是一个双向链表结构。从图中也可以看出LinkedList的整体结构图，LinkedList有很多Node，有first和last两个变量，用来存放头尾节点的信息；而且它不是循环双向链表，因为它前后都是null，这是我们需要注意的。继承体系publicclassLinkedListextendsAbstractSequentialListimplementsList,Deque,Cloneable,java.io.Serializable{...}通过继承体系我们可以看出LinkedList不仅实现了List接口，同时实现了Queue和Deque接口，所以它不仅可以作为List使用，还可以作为双端队列使用，当然也可以作为栈使用。源码分析主要属性//元素个数transientintsize=0;//链表第一个节点transientNodefirst;//链表最后一个节点transientNodelast;NodenodeprivatestaticclassNode{//valueE项;//后继者指向下一个引用Nodenext;//前驱指向前一个引用Nodeprev;Node(Nodeprev,Eelement,Nodenext){this.item=element;这个.下一个=下一个；this.prev=prev;}}构造方法publicLinkedList(){}publicLinkedList(Collectionc){this();//设置集合C中的所有元素都插入到链表中addAll(c);}添加元素为双端队列，添加元素主要有两种，一种是在尾部添加元素队列，另一种是在队列的头部添加元素。这两种形式主要是通过LinkedList中的以下两个方法实现的。//从队列开头添加元素privatevoidlinkFirst(Ee){//第一个节点finalNodef=first;//创建一个新节点，新节点的下一个是第一个节点finalNodenewNode=newNode<>(null,e,f);//让新节点成为新的第一个节点first=newNode;//判断是否是第一个加入的元素//如果是，则设置last为新节点//否则将原first节点的prev指针设置为新节点if(f==null)last=newNode;elsef.prev=newNode;//元素个数加1size++;//修改次数加1，表示这是一个支持fail-fast的集合modCount++;}//从队尾添加元素voidlinkLast(Ee){//队尾节点finalNodel=最后一个；//创建一个新节点，新节点的prev为结束节点finalNodenewNode=newNode<>(l,e,null);//使新节点成为新的结束节点last=newNode;//判断是否是第一个加入的元素//如果是，则把first也设为新节点//否则，将原尾节点的next指针设为新节点if(l==null)first=newNode;elsel.next=newNode;//元素个数加1size++;//增加修改次数1modCount++;}publicvoidaddFirst(Ee){linkFirst(e);}publicvoidaddLast(Ee){linkLast(e);}//作为无界队列，添加元素总会成功publicbooleanofferFirst(Ee){addFirst(e);returntrue;}publicbooleanofferLast(Ee){addLast(e);returntrue;}上面看成一个双端队列，其添加的元素分为第一个和最后一个添加的元素，作为一个List，就是支持在中间添加元素，主要通过下面的方法//在节点前添加一个元素succvoidlinkBefore(Ee,Nodesucc){//succ为待添加节点的后继节点//查找待添加节点的前驱节点finalNodepred=成功。上一个；//在其前驱节点和后继节点之间创建一个新节点finalNodenewNode=newNode<>(pred,e,succ);//修改后继节点的前指针指向新节点succ.prev=newNode;//判断上一个节点是否为空//如果为空，则表示是第一个加入的元素，修改第一个指针//否则，修改上一个节点的next为新节点if(pred==空）首先=新节点；否则pred.next=newNode;//修改元素个数size++;//修改次数加1modCount++;}//找到索引位置的节点Nodenode(intindex){//因为是双链表//所以根据索引是否在前半部分还是后半部分，决定从前面遍历还是从后面遍历//这样索引就可以遍历后半部分一半的元素if(index<(size>>1)){//如果在前半段//遍历Nodex=first;for(inti=0;ix=last;for(inti=size-1;i>index;i--)x=x.prev;返回x;}}//在指定索引位置添加一个元素publicvoidadd(intindex,Eelement){//判断是否越界checkPositionIndex(index);//如果index是队列尾节点之后的位置//直接在尾节点之后添加新节点//否则调用linkBefore()方法在中间添加节点if(index==size)linkLast(元素）;elselinkBefore(element,node(index));}在中间添加元素方法也很简单。典型双链表中间添加元素的三种方式大致如下图所示：在队列首尾添加元素效率很高，时间复杂度为O(1)。在中间添加元素是比较低效的。首先找到插入位置的节点，然后修改前后节点的指针。时间复杂度为O(n)。作为双端队列，删除元素有两种方式，一种是删除队头元素，另一种是删除队尾元素。作为List，也是支持删除中间元素的，所以删除元素的方法有3种，分别如下。//删除第一个节点privateEunlinkFirst(Nodef){//第一个节点的元素值finalEelement=f.item;//第一个节点的下一个指针finalNodenext=f.next;//添加第一个节点的内容辅助GCf.item=null;f.next=null;//helpGC//取第一个节点的next作为新的第一个节点first=next;//如果只有一个元素，则删除它，也将last设置为null//否则，将next的前向指针设置为nullif(next==null)last=null;否则next.prev=null;//将元素数量减少1size--;//修改次数加1modCount++;//返回删除的元素returnelement;}//删除尾节点privateEunlinkLast(Nodel){//尾节点的元素值finalEelement=l.item;//Tail节点的前端指针finalNodeprev=l.prev;//清除tail节点的内容以辅助GCl.item=null;l.prev=null;//帮助GC//使前端节点成为新节点尾节点last=prev;//如果只有一个元素，则删除它并设置first为空//否则，将前一个节点的next设置为空if(prev==null)first=null;否则prev.next=null;//元素个数减1size--;//修改次数加1modCount++;//返回删除的元素returnelement;}//删除指定节点xEunlink(Nodex){//x的元素值finalEelement=x.item;//x的前节点finalNodenext=x.next;//x的post节点finalNodeprev=x.prev;//如果前节点为空//表示它是第一个节点，让first指向x的后节点//否则，将前节点的next修改为x的后节点if(prev==null){first=next;}else{prev.next=next;x.prev=null;}//如果post节点为空//表示是尾节点，让last指向x的前一个节点//否则修改post节点的prev为xif(next==null){last=上一个；}else{next.prev=prev;x.next=null;}//清除x的元素值以辅助GCx.item=null;//元素个数减1size--;//修改次数加1modCount++;//返回删除的元素returnelement;}//移除时，如果没有元素，则抛出异常publicEremoveFirst(){finalNodef=first;如果(f==null)抛出新的NoSuchElementException()；returnunlinkFirst(f);}//如果在删除过程中没有元素，则抛出异常publicEremoveLast(){finalNodel=last;如果（l==null）抛出新的NoSuchElementException（）；returnunlinkLast(l);}//轮询时如果没有元素则返回nullpublicEpollFirst(){finalNodef=first;返回（f==null）？null:unlinkFirst(f);}//如果在轮询期间没有元素，则返回nullpublicEpollLast(){finalNodel=last;返回（l==null）？null:unlinkLast(l);}//删除中间节点publicEremove(intindex){//检查是否越界checkElementIndex(index);//删除指定索引位置的节点returnunlink(node(index));}三种删除元素的方法是双链表删除元素的典型方法。度数为O(1)。删除中间的元素是比较低效的。首先找到删除位置的节点，然后修改前后指针。时间复杂度为O(n)。我们在栈之前说过LinkedList是一个双端队列。还记得双端队列可以当栈用吗？packageorg.example.test;importjava.util.LinkedList;/***使用LinkedList模拟栈*栈的特点：先进后出*/publicclassTest12{privateLinkedListlinkList=newLinkedList<字符串>();//推送publicvoidpush(Stringstr){linkList.addFirst(str);}//poppublicStringpop(){returnlinkList.removeFirst();}//查看publicStringpeek(){returnlinkList.peek();}//判断是否为空publicbooleanisEmpty(){returnlinkList.isEmpty();}}classTest13{publicstaticvoidmain(String[]args){//测试堆栈Test12test12=newTest12();test12.push("我是第一个进入的");test12.push("我是第二个进入的");test12.push("我是第三个进入");test12.push("我是第4个");test12.push("我是第5个");//取出while(!test12.isEmpty()){Stringpop=test12.pop();系统.out.println（弹出）；}//打印结果/*我是第5个，我是第4个，我是第3个，我是第2个，我是第1个*/}}栈的特点是后进先出（LastInFirstOut），所以作为栈来使用非常简单。添加和删??除元素只操作队列的第一个节点。(1)LinkedList是双链表实现的List，所以不存在容量不足的问题，所以没有办法扩容。(2)LinkedList也是双端队列，具有队列、双端队列、栈的特点。(3)LinkedList在队列首尾添加和删除元素的效率很高，时间复杂度为O(1)。(4)LinkedList在中间增删元素效率比较低，时间复杂度为O(n)。(5)LinkedList不支持随机访问，因此访问队列头尾以外的元素效率低下。(6)LinkedList在功能上等同于ArrayList+ArrayDeque。(7)LinkedList不是线程安全的。(8)LinkedList可以存储空值。经典面试题说说ArrayList和LinkedList的区别。本质区别来自于两者的底层实现：ArrayList底层是数组，LinkedList底层是双向链表。数组具有O(1)的查询效率，可以直接通过下标定位元素；链表在查询元素时只能通过遍历来查询，效率不如数组。数组中元素的增删改查效率比较低，通常伴随着复制数组的操作；链表中元素的增删改查效率很高，只需要调整相应位置的指针即可。以上是数组和链表之间的流行比较。在日常使用中，两者都能在各自的适用场景中发挥很好的作用。我们经常使用ArrayList而不是数组，因为它封装了很多简单易用的API，并且在内部实现了自动扩容机制。由于其内部维护了一个当前容量指针大小，直接向ArrayList添加元素的时间复杂度为O(1)，使用起来非常方便。LinkedList经常被用作Queue队列的实现类。由于底层是一个双向链表，可以方便的提供先进先出的操作。可以分为两部分：一是数组和链表底层实现的区别，二是ArrayList和LinkedList的实现细节。
