链表进阶2:双向链表的构建[TOC](链表进阶2:双向链表的构建) 这一版我没有引入尾部tail,后面会更新单向链表与双向链表引入尾部节点tail的章节;1.创建链表节点;2.头插法2.尾插3.中间位置插入4.头删5.尾删6.按下标删除7.按值删除8.判断元素是否存在循环遍历即可9.返回存在元素的下标循环遍历即可10.toString方法这一版我没有引入尾部tail,后面会更新单向链表与双向链表引入尾部节点tail的章节;1.创建链表节点;这个链表节点与先前的单向链表相比,多了一个prev指向前一个节点;classListNode{publicintval;publicListNodenext;publicListNodeprev;publicListNode(intval){this.valval;this.nextnull;this.prevnull;}}2.头插法1)首先要有头节点,判断是否为null,如果是,头节点指向新的节点;2)新节点指向head,head的前一个节点prev指向新节点;3)新节点变为头节点;publicListNodeheadnull;publicvoidaddFirst(intval){ListNodenewnodenewListNode(val);if(headnull){headnewnode;return;}newnode.nexthead;head.prevnewnode;headnewnode;}2.尾插1)创建一个尾部节点,头节点;2)当头节点为空时,全部指向新节点;3)不为空,尾部插入,还要更新tail尾部publicvoidaddLast(intval){LinkedNodenewnodenewLinkedNode(val);if(headnull){headnewnode;return;}LinkedNodecurhead;while(cur.next!null){curcur.next;}cur.nextnewnode;newnode.prevcur;}3.中间位置插入1)首先判断下标,我们需要写链表的尺寸大小;2)下标为0或者最后调用前面的头插与尾插;3) 找出要插入的位置,开始插入privateintsize(){if(headnull){return0;}intsize0;for(LinkedNodecurhead;cur!null;curcur.next){size;}returnsize;}publicvoidadd(intindex,intval){LinkedNodenewnodenewLinkedNode(val);intsizesize();if(index0||indexsize){thrownewIndexOutOfBoundsException(下标越界);}if(index0){addFirst(val);return;}if(indexsize){addLast(val);return;}LinkedNodecurhead;for(inti0;iindex-1;i){curcur.next;}newnode.nextcur.next;cur.next.prevnewnode;cur.nextnewnode;newnode.prevcur;}4.头删1)判断是不是头节点head为空或者只有一个节点;2)更新head3)注意head的prev指向一定要为nullpublicvoidremoveFirst(){if(headnull){return;}if(head.nextnull){headnull;return;}headhead.next;head.prevnull;}5.尾删1)先判断是不是为空,或者只有一个节点2)找到最后要删除的节点的上一个,让他指向空;3)删除节点的prev也要指向空;publicvoidremoveLast(){if(headnull){return;}if(head.nextnull){headnull;return;}LinkedNodetailhead;while(tail.next!null){tailtail.next;}LinkedNodeprevtail.prev;prev.nextnull;tail.prevnull;}6.按下标删除1)首先还是要判断下标;2)下标为0,为尾部特殊处理3)循环遍历找到要删除的元素;publicvoidremove(intindex){intsizesize();if(index0||indexsize){thrownewIndexOutOfBoundsException(下标越界);}if(index0){removeFirst();return;}if(indexsize-1){removeLast();return;}LinkedNodetoDeletehead;for(inti0;iindex;i){toDeletetoDelete.next;}LinkedNodeprevtoDelete.prev;prev.nexttoDelete.next;toDelete.next.prevprev;toDelete.nextnull;toDelete.prevnull;}7.按值删除1).通过循环遍历,找出要删除的值的节点,直接退出break;2).判断循环结束是否找到,没找到直接返回;3).最后考虑删除节点是否为尾部节点;publicvoidremoveByvalue(intval){if(headnull){return;}if(head.valval){removeFirst();return;}LinkedNodecurhead;for(;cur!null;curcur.next){if(cur.valval){break;}}if(curnull){return;}LinkedNodeprevcur.prev;LinkedNodenextcur.next;prev.nextcur.next;if(next!null){next.prevprev;}cur.nextnull;cur.prevnull;}8.判断元素是否存在循环遍历即可publicbooleancontains(intval){if(headnull){returnfalse;}for(LinkedNodecurhead;cur!null;curcur.next){if(cur.valval){returntrue;}}returnfalse;}9.返回存在元素的下标循环遍历即可publicintindexOf(intval){inti0;for(LinkedNodecurhead;cur!null;curcur.next,i){if(cur.valval){returni;}}return-1;}10.toString方法publicStringtoString(){if(headnull){returnnull;}StringBuilderstrnewStringBuilder();for(LinkedNodecurhead;cur!null;curcur.next){str.append(cur.val);if(cur.next!null){str.append(, );}}LinkedNodetailhead;while(tail.next!null){tailtail.next;}str.append(||);for(LinkedNodecurtail;cur!null;curcur.prev){str.append(cur.val);if(cur.prev!null){str.append(, );}}returnstr.toString();}publicclassTestToString{privatestaticintpass0,fail0;privatestaticvoidcheck(Stringname,Stringexpected,Stringactual){if(expectednull?actualnull:expected.equals(actual)){pass;System.out.println([PASS] name - \actual\);}else{fail;System.out.println([FAIL] name);System.out.println( expected: \expected\);System.out.println( actual : \actual\);}}publicstaticvoidmain(String[]args){MyDLinkedListemptynewMyDLinkedList();check(空链表,,empty.toString());MyDLinkedListonenewMyDLinkedList();one.addFirst(1);check(单节点 [1],1||1,one.toString());MyDLinkedListmultinewMyDLinkedList();multi.addLast(1);multi.addLast(2);multi.addLast(3);check(多节点 [1,2,3],1, 2, 3||3, 2, 1,multi.toString());MyDLinkedListafterHeadnewMyDLinkedList();afterHead.addLast(1);afterHead.addLast(2);afterHead.addLast(3);afterHead.removeFirst();check(头删后 [2,3],2, 3||3, 2,afterHead.toString());MyDLinkedListafterTailnewMyDLinkedList();afterTail.addLast(1);afterTail.addLast(2);afterTail.addLast(3);afterTail.removeLast();check(尾删后 [1,2],1, 2||2, 1,afterTail.toString());System.out.println(\n通过 pass失败 fail);}}