双向链表与数据结构简介上一节我们分析了ArrayList的底层实现，了解到ArrayList的底层实现是基于数组的，所以它具有查找和修改快，但插入和删除慢的优点本章我们介绍的LinkedList的特点是List接口的另一种实现。它的底层是基于双向链表的，所以具有插入和删除快，查找和修改慢的特点。什么是链表？LinkList是双向链表（doublelinkedlist）；它是链表的一种，也是最常见的数据结构。它的内部数据是线性排列的，属于线性表结构。它的每个数据节点都有两个指针，分别指向直接后继者和直接前驱者。因此，从双向链表中的任意一个节点出发，都可以很容易地访问到它的前驱节点和后继节点，因此它是一个双向链表。,middle,tail)插入O(1)缺点：查询慢O(N)线程不安全，允许null，允许重复元素蓝色表示；可以随意插入和删除一个指向下一个节点的指针，一个指向前一个节点的指针（双向读）。所谓指针就是指向另一个节点的对象的引用（说白了就是定义了两个成员变量）。双向链表线程不安全。允许为null，允许重复元素查询O(n)插入删除O(1)1.2双向链表继承关系LinkedList是继承于AbstractSequentialList的双向链表。LinkedList实现了List接口，可以对其进行队列操作。LinkedList实现了Deque接口，LinkedList可以作为双端队列使用。LinkedList实现了Cloneable接口，它重写了函数clone()并且可以被克隆。LinkedList实现了java.io.Serializable接口，也就是说LinkedList支持序列化，可以通过序列化进行传输。1.3双向链表源码深入分析案例代码com.llist.LListpackagecom.llist;importjava.util.ArrayList;importjava.util.Collection;importjava.util.LinkedList;publicclassLList{publicstaticvoidmain(String[]args){LinkedListlinkedList=newLinkedList();linkedList.add("100");//尾部插入，相当于linkedList.addLast()linkedList.add("200");链表。添加（“300”）；//*******在中间插入linkedList..add(3,"700")************linkedList.add("400")linkedList.add("500");linkedList.add("600");System.out.println(链表);linkedList.add(3,"700");//中间插入System.out.println(linkedList);//*********修改*******************************************linkedList.set(3,"700000000");System.out.println(链表);//*********查询***************************************系统输出.println(linkedList.getFirst());//头部检查System.out.println(linkedList.getLast());//结束检查//for(ints=0;slinkedListRemove=newLinkedList();linkedListRemove.add("100");linkedListRemove.add("200");linkedListRemove.add("300");linkedListRemove.remove(1);//指定移除linkedListRemove.removeAll(linkedList);//同样调用上面的unlink方法；LinkedList.ListItr.remove}}1.3.1链表成员变量和内部类先定义几个名字，后面会用到transientintsize=0;//元素个数transientNodefirst;//Head节点引用（查询时获取）transientNodelast;//尾节点引用（查询时获取）privatestaticclassNode{//链表节点元素，封装真实数据，并添加前后指针Eitem;//元素，this是真正放入Nodenext的数据;//下一个节点，指针也是Node类型Nodeprev;//上一个节点//构造器，pre，value，post，很清楚Node(Nodeprev,Eelement,Nodenext){this.item=element;//newelementthis.next=next;//nextAnodethis.prev=prev;//上一个节点}}1.3.2双向链表构造函数无参构造函数：什么都不做publicLinkedList(){//无参构造函数}有参构造函数：传入的构造函数外部集合publicLinkedList(Collectionc){this();addAll(c);}秘密就藏在addAll中(重点，绘图显示)publicbooleanaddAll(intindex,Collectionc){checkPositionIndex(index);//边界判断Object[]a=c.toArray();//无论传什么类型，都会转成数组intnumNew=a.length;//需要新插入Numberif(numNew==0)returnfalse;//两个指针，分别代表你要插入的点前后两个节点我们称它们为前节点和后节点//比如你的index=2:[0001111(pred)(index)2222(succ)33333...]Nodepred,succ;if(index==size){//下一步就是定位这两个指针的位置succ=null;//如果指定索引等于尾部，显然没有postpred=last;//pre是最后一个元素last}else{succ=node(index);//否则post就是当前索引位置的节点。下面将详细描述该方法。Pred=succ.prev;//pred就是当前索引位置的prev，很容易理解}for(Objecto:a){//开始循环插入的元素@SuppressWarnings("unchecked")Ee=(E)o;NodenewNode=newNode<>(pred,e,null);//定义一个新节点，将当前元素包裹起来if(pred==null)//如果pred为空，注意什么时候为空？仅当插入表头或当前列表没有元素时first=newNode;//表示第一次插入元素，先指向当前元素，完成elsepred.next=newNode;//否则，将节点指向的后向指针前置到当前元素（已连接）pred=newNode;//让前面的指针向后移动，指向新创建的节点，为下一次循环做准备}//依次循环，向上连接，连接后pred是最后一个插入的元素//所有循环连接完成后，我们将处理新连接链接的后指针if(succ==null){//如果后缀为nul，说明我们一直在最后插入last=pred；//只要last指向最后插入的元素，也就是尾部}else{pred.next=succ;//否则最后插入的next指向原插入前的postsucc.prev=pred;//post-pred指针指向最后插入的元素，一对操作这两步缺一不可}//至此，被截断的后半段链也连接上了大小+=numNew;//最后别忘了元素个数增加modCount++;//操作计数器增加returntrue;}1.3.3链表插入（重点）1）双向链表尾部插入方法1、add(Ee)、2、addLast；调用方法相同(linkLast)publicbooleanadd(Ee){linkLast(e);//在链表末尾添加returntrue;}在链表末尾添加/***添加*/链表末尾voidlinkLast(Ee){finalNodel=last;//取出当前最后一个节点finalNodenewNode=newNode<>(l,e,null);//创建新节点，注意其前驱节点Forllast=newNode;//尾指针指向新节点if(l==null)//如果原尾节点为空，则表示链表为空，首节点也赋值为newNodefirst=newNode;elsel.next=newNode;//否则，将原尾节点的后向指针指向新节点，形成双向环size++;//countmodCount++;//count}结论：默认add是尾部插入方式，追加到尾部2）链表中部双向插入目标：在双向链表中部插入之前插入700到400add(intindex,E元素)//自定义插入linkedList.add(3,"700");源码如下publicvoidadd(intindex,Eelement){checkPositionIndex(index);//越界检查if(index==size)//如果index是指针的末尾，则可以自然调整和插入linkLast(element);elselinkBefore(element,node(index));//否则，找到index位置的节点，跳到它的前面}/***那它是怎么找到的呢？参见下面的方法（绘图显示）*/Nodenode(intindex){//这里是一个简洁的设计！非常灵活的应用我们的first和lastif(index<(size>>1)){//如果index小于链表长度的1/2（size向右移动1，则为除以2)Nodex=first;for(inti=0;ix=最后一个；for(inti=size-1;i>index;i--)//循环直到索引位置x=x.prev;返回x;//抓住它并返回，完成！}}//画图显示voidlinkBefore(Ee,Nodesucc){//找到后，也就是这里的succ，我们开始在它前面插入新的元素//assertsucc!=null;finalNodepred=succ.prev;//上一个节点finalNodenewNode=newNode<>(pred,e,succ);//新建一个双向节点succ.prev=newNode;//修改后节点的前指针if(pred==null)//如果前节点为空，则链表为空first=newNode;//则当前插入为头节点elsepred.next=newNode;//否则修改pre-post指针指向新节点，双向链表连接成功！size++;//数量加1modCount++;//修改次数加1}1.3.4双向链表的修改方法很简单！找到包裹值的节点，修改里面的属性。publicEset(intindex,Eelement){checkElementIndex(index);//边界检查Nodex=node(index);//通过链表索引查找nodeEoldVal=x.item;//获取原值x.item=element;//赋新值returnoldVal;//返回旧值}1.3.5双向链表的查询方式很简单！get(intindex)：根据下标获取元素；一般方法getFirst()：获取第一个元素；特殊方法，直接取指针是getLast()：获取最后一个元素；特殊方法，也是直接取指针publicEget(intindex){checkElementIndex(index);//越界校验returnnode(index).item;//在原数组中找到index对应的节点}System.out.println(linkedList.getFirst());//headcheckSystem.out.println(linkedList.getLast());//endcheck1.3.6双向链表删除方法remove(Ee)：删除指定元素;通用方法removeAll(Collectionc)移除指定集合的??元素；同样分两步调用unlink方法：1查找，2删除publicbooleanremove(Objecto){if(o==null){//如果要移除空元素for(Nodex=first;x!=null;x=x.next){//从拳头找if(x.item==null){//如果你找到它，杀死它unlink(x);//关键点！是unlink方法returntrue；}}}else{for(Nodex=first;x!=null;x=x.next){if(o.equals(x.item)){//如果不是去掉null，则方式是一样的，无非就是把==换成equals来判断unlink(x)；返回真；}}}返回假；}/***绘图显示：要移除的节点，如【100】【200】【300】*/Eunlink(Nodex){//assertx!=null;finalEelement=x.item;//元素finalNodenext=x.next;//下一个节点finalNodeprev=x.prev;//上一个节点if(prev==null){first=next;//前一个节点为空，表示当前要移除的节点为头节点，设置fist指针指向后面，我被移除后升级为头}else{prev.下一个=下一个；//否则前向后指针指针指向postx.prev=null;//当前节点的pre指针被截断！}if(next==null){last=prev;//post为空，说明当前要移除的节点为尾节点。我被移除后，我的前面变成了尾巴}else{next.prev=prev;//否则后指针指向前节点x.next=null;//当前节点的后向指针被截断！}//这里前后的指针都整理好了，什么该断，什么该接x.item=null;//将当前元素变为null，交给垃圾回收size--;//链表的大小减一modCount++;//修改次数加一返回元素；//删除元素}本文由传智教育博学谷-野外建筑师教研组发布，转载请注明出处！如果本文对您有帮助，请关注并点赞；有什么建议也可以留言或私信。您的支持是我坚持创作的动力
