数据结构链表（双向链表学习）

程序里有几个注释的地方还是需要特别注意的&＃xff0c;根据单链表自己的逻辑来写一遍双向链表&＃xff0c;可能有几个细节处理的不到位。

package DataStructures.LinkedList;public class DoubleLinkedListDemo {public static void main(String []args){System.out.println("双向链表的测试");//先创建节点HeroNode2 hero1 &＃61; new HeroNode2(1, "宋江", "及时雨");HeroNode2 hero2 &＃61; new HeroNode2(2, "卢俊义", "玉麒麟");HeroNode2 hero3 &＃61; new HeroNode2(3, "吴用", "智多星");HeroNode2 hero4 &＃61; new HeroNode2(4, "林冲", "豹子头");//创建一个双向链表DoubleLinkedList doubleLinkedList &＃61; new DoubleLinkedList();//添加节点doubleLinkedList.add(hero1);doubleLinkedList.add(hero2);doubleLinkedList.add(hero3);doubleLinkedList.add(hero4);doubleLinkedList.list();HeroNode2 newHeroNode &＃61; new HeroNode2(4,"公孙胜","入云龙");doubleLinkedList.updata(newHeroNode);doubleLinkedList.list();doubleLinkedList.delete(1);doubleLinkedList.list();}
}
class DoubleLinkedList{private HeroNode2 head &＃61; new HeroNode2(0,"","");public HeroNode2 getHead() {return head;}//删除一个节点//说明//对于双向链表&＃xff0c;直接找到这个节点&＃xff0c;进行自我删除public void delete(int no){if (head.next &＃61;&＃61; null){System.out.println("链表为空&＃xff0c;无法删除");}//这里要加next&＃xff0c;因为0是不能删除的HeroNode2 temp &＃61; head.next;boolean flag &＃61; false;//这里现在是用temp本身来判断while (temp !&＃61; null){if (temp.no &＃61;&＃61; no){flag &＃61; true;break;}temp &＃61; temp.next;}if (flag){temp.pre.next &＃61; temp.next;//注意&＃xff1a;&＃xff1a;这里会有问题&＃xff1f;&＃xff1f;&＃xff1f;//因为如果删除的节点是最后一个节点&＃xff0c;下面这句话加上了&＃xff0c;会出现空指针异常if (temp.next !&＃61; null) {temp.next.pre &＃61; temp.pre;}System.out.println("节点删除成功\n");}else {System.out.printf("没找到编号为 %d 的节点&＃xff01;删除失败\n",no);}}//修改一个节点的内容public void updata(HeroNode2 heroNode){if (head.next &＃61;&＃61; null){System.out.println("链表为空位&＃xff0c;无法修改");return;}//这里要用next&＃xff0c;因为更改的时候头结点不能找HeroNode2 temp &＃61; head.next;boolean flag &＃61; false;while(true){if (temp &＃61;&＃61; null){break;}if (temp.no &＃61;&＃61; heroNode.no){flag &＃61; true;break;}temp &＃61; temp.next;}if (flag){temp.name &＃61; heroNode.name;temp.nickname &＃61; heroNode.nickname;}else {System.out.printf("没找到 编号为 %d 的节点\n",heroNode.no);}}//添加节点public void add(HeroNode2 newHeroNode){HeroNode2 temp &＃61; head;while(true){if (temp.next &＃61;&＃61; null){break;}temp &＃61; temp.next;}//while退出后temp就是链表最后节点//形成双向链表temp.next &＃61; newHeroNode;newHeroNode.pre &＃61; temp;}//遍历输出public void list(){if (head.next &＃61;&＃61; null){System.out.println("链表为空");return;}//这里要加next要不然打印会把头结点打印出来HeroNode2 temp &＃61; head.next;while (temp !&＃61; null){System.out.println(temp);temp &＃61; temp.next;}}}class HeroNode2{public int no;public String name;public String nickname;public HeroNode2 next; //指向下一个节点public HeroNode2 pre; //指向前一个节点public HeroNode2(int no, String name, String nickname) {this.no &＃61; no;this.name &＃61; name;this.nickname &＃61; nickname;}&＃64;Overridepublic String toString() {return "HeroNode2{" &＃43;"no&＃61;" &＃43; no &＃43;", name&＃61;&＃39;" &＃43; name &＃43; &＃39;\&＃39;&＃39; &＃43;", nickname&＃61;&＃39;" &＃43; nickname &＃43; &＃39;\&＃39;&＃39; &＃43;&＃39;}&＃39;;}
}


加一个添加的时候根据no排序

//添加节点并根据no有序public void addByOrder(HeroNode2 newHeroNode){HeroNode2 temp &＃61; head;boolean flag &＃61; false;while (true){if (temp.next &＃61;&＃61; null){break;}if (temp.next.no > newHeroNode.no){break;}else if (temp.next.no &＃61;&＃61; newHeroNode.no){flag &＃61; true;break;}temp &＃61; temp.next;}if (flag){System.out.printf("编号 %d 已存在,不能添加\n",newHeroNode.no);}else {//这里注意不要写反了&＃xff0c;先写if这里&＃xff0c;再写剩下两个&＃xff0c;要不然就形成了一个环状&＃xff0c;这里找了好久bugif (temp.next !&＃61; null) {temp.next.pre &＃61; newHeroNode;newHeroNode.next &＃61; temp.next;}temp.next &＃61; newHeroNode;newHeroNode.pre &＃61; temp;}}


测试

doubleLinkedList.addByOrder(hero1);
doubleLinkedList.addByOrder(hero4);
doubleLinkedList.addByOrder(hero2);
doubleLinkedList.addByOrder(hero3);doubleLinkedList.list();


结果&＃xff1a;双向链表的测试
HeroNode2{no&＃61;1, name&＃61;&＃39;宋江&＃39;, nickname&＃61;&＃39;及时雨&＃39;}
HeroNode2{no&＃61;2, name&＃61;&＃39;卢俊义&＃39;, nickname&＃61;&＃39;玉麒麟&＃39;}
HeroNode2{no&＃61;3, name&＃61;&＃39;吴用&＃39;, nickname&＃61;&＃39;智多星&＃39;}
HeroNode2{no&＃61;4, name&＃61;&＃39;林冲&＃39;, nickname&＃61;&＃39;豹子头&＃39;}