前言❤️❤️hello hello这里是洋不写bug~欢迎大家点赞关注收藏这篇博客是链表博客的最后一篇内容比较少就是模拟双链表的实现进一步的锻炼代码能力初学的铁汁建议先模拟实现单链表链表博客中有提到再来模拟实现双链表因为很多方法是在单链表的基础上改了一点这个专栏的数据结构是代码都是用Java来写的JavaSE专栏现在已经全部更新完成铁汁们复习基础知识时非常推荐使用可以试一下个人主页洋不写bug的博客所属专栏数据结构专栏复习Java基础知识Java学习之旅从入门到进阶铁汁们对于数据结构基础的各种核心知识不太常用的也有都可以在上面的数据结构专栏学习专栏正在持续更新中有问题可以写在评论区或者私信我哦~1双链表简介单链表就是节点中只存了 next 引用只能找到下一个节点。双链表中存储了 prev 引用和 next 引用也可以找到上一个节点这样在使用时自然是更方便的双链表的缺点就是空间利用率低在Java中链表的一个引用占8个字节双向链表的引用就占16个字节如果每个节点中保存数据的部分占用空间很小例如只保存了一个int类型的数字那链表的空间利用率就是很低的2双链表的模拟实现接下来就模拟实现个自己的双链表里面存入的数据类型固定为String先建个Node类表示节点相比单链表要多定义一个属性prevpublicclassNode{publicStringval;publicNodenextnull;publicNodeprevnull;publicNode(Stringval){this.valval;}}在MyDLinkedList类中搞一个尾节点方便后续进行尾插对于addFirst方法要判断下如果head为null也就是链表为空那就让head和tail指向null如果链表不为空那就先让newNode指向head把head的perv改为newNode再更新下headpublicclassMyDLinkedList{privateNodeheadnull;privateNodetailnull;publicvoidaddFirst(Stringval){NodenewNodenewNode(val);if(headnull){headnewNode;tailnewNode;}else{newNode.nexthead;head.prevnewNode;headnewNode;}}}接着再写个toString方法打印时使用publicStringtoString(){StringBuilderstringBuildernewStringBuilder();stringBuilder.append([);Nodecurhead;while(cur!null){stringBuilder.append(cur.val);if(cur.next!null){stringBuilder.append(,);}curcur.next;}stringBuilder.append(]);returnstringBuilder.toString();}每写完一个方法都建议在main方法中测试一下后面每个方法的测试代码博主就不粘了publicclassTest{publicstaticvoidmain(String[]args){MyDLinkedListmyDLinkedListnewMyDLinkedList();myDLinkedList.addFirst(aaa);myDLinkedList.addFirst(bbb);myDLinkedList.addFirst(ccc);myDLinkedList.addFirst(ddd);System.out.println(myDLinkedList);}}接着是尾插因为链表中存储了最后一个节点的引用就无需再去遍历找尾节点了publicvoidaddLast(Stringval){NodenewNodenewNode(val);if(headnull){headnewNode;tailnewNode;}else{tail.nextnewNode;newNode.prevtail;tailnewNode;}}size方法如下写法跟单链表相同publicintsize(){Nodecurhead;intsize0;while(cur!null){size;curcur.next;}returnsize;}中间位置插入方法add就是传入下标和元素值在中间位置插入元素条件判断的时候是可以等于size()的相当于尾插也可以等于0相当于头插下面这两种写法单从代码上来看第二种写法效率是比较高的因为第一种写法size()是可能执行两次的判断时和打印错误信息时而size()方法是遍历整个链表还是有一定开销的但是如果测试的话这两种写法的执行效率可能也差不多这是因为Java的编译器在编译代码的时候具有优化功能可能会对代码的顺序写法之类的进行调整以降低程序员之间的代码差距所以铁汁们用哪种写法根据自己的喜好来即可if(index0||indexsize()){thrownewIndexOutOfBoundsException(size:size(),index:index);}intsizesize();if(index0||indexsize){thrownewIndexOutOfBoundsException(size:size,index:index);}分析下中间位置插入的逻辑首先把新节点的prev指向前面的节点next指向后面的节点接着再调下前面节点的next和后面节点的prev即可对于首插和尾插直接调用前面的方法即可publicvoidadd(intindex,Stringval){intsizesize();if(index0||indexsize){thrownewIndexOutOfBoundsException(size:size,index:index);}if(index0){addFirst(val);return;}if(indexsize){addLast(val);return;}NodenewNodenewNode(val);Nodeprevhead;for(inti0;iindex-1;i){prevprev.next;}Nodenextprev.next;newNode.prevprev;newNode.nextnext;prev.nextnewNode;next.prevnewNode;}contains和indexOf方法都是遍历下链表即可publicbooleancontains(Stringval){if(headnull){returnfalse;}Nodecurhead;while(cur!null){if(cur.val.equals(val)){returntrue;}curcur.next;}returnfalse;}publicintindexOf(Stringval){intindex0;if(headnull){return-1;}Nodecurhead;while(cur!null){if(cur.val.equals(val)){returnindex;}index;curcur.next;}return-1;}removeFirst方法删除头部元素需要分为空链表只有一个节点的链表还有多个节点的链表publicvoidremoveFirst(){if(headnull){return;}if(head.nextnull){headnull;tailnull;return;}Nodecurhead.next;cur.prevnull;headhead.next;}removeLast方法和removeFirst的写法类似publicvoidremoveLast(){if(headnull){return;}if(head.nextnull){headnull;tailnull;return;}Nodecurtail.prev;cur.nextnull;tailcur;}指定位置删除remove方法里面传入index这里index就不能等于size()了因为链表的下标是从0到index - 1的需要找到要删除元素的上个位置和下个位置如果要删除的是头节点或者尾节点直接调用前面已经写过的removeFirst和RemoveLast方法即可排除这两种情况后prev和next就不可能是null我们就可以放心的去写代码publicvoidremove(intindex){intsizesize();if(index0||indexsize){thrownewIndexOutOfBoundsException(size:size,index:index);}if(index0){removeFirst();return;}if(indexsize-1){removeLast();return;}Nodeprevhead;for(inti0;iindex-1;i){prevprev.next;}Nodenextprev.next.next;prev.nextnext;next.prevprev;}reomve方法传入元素的版本就遍历一下链表找到toRemove节点接获取它的上个节点和下个节点分别修改下next和prev的指向即可publicvoidremove(Stringval){NodetoRemovehead;while(toRemove!null){if(toRemove.val.equals(val)){break;}toRemovetoRemove.next;}if(toRemovenull){return;}if(toRemovehead){removeFirst();return;}if(toRemovetail){removeLast();return;}NodeprevtoRemove.prev;NodenexttoRemove.next;prev.nextnext;next.prevprev;}结语双链表的模拟实现在日常开发中上不会用到这里模拟实现同样是锻炼我们的代码能力包括画图分析对于特殊情况和边界的处理在写代码时可以先考虑正常的情况先写出代码再结合正常情况的代码来分析加上处理特殊情况的逻辑remove方法的逻辑就是这样初学数据结构的铁汁如果能把这三篇博客中的代码都自己敲一遍你做链表题目的代码能力一定会有个很大的提升