双向链表的增删查改

上图是双向链表按照编号顺序添加节点的图 temp是头节点的辅助节点，开始temp = head， node是下一个要加入的节点 修改节点比较简单就没写 可以先看代码

public class DoubleLinkListDemo3 { public static void main(String[] args) { HHeroNode3 hHeroNode1 = new HHeroNode3(1); HHeroNode3 hHeroNode2 = new HHeroNode3(5); HHeroNode3 hHeroNode3 = new HHeroNode3(3); HHeroNode3 hHeroNode4 = new HHeroNode3(10); DoubleLinkList3 d = new DoubleLinkList3(); d.addByOrder(hHeroNode1); d.addByOrder(hHeroNode2); d.addByOrder(hHeroNode3); d.addByOrder(hHeroNode4); d.show(); System.out.println("删除数据后： "); d.del(10); d.show(); } } class DoubleLinkList3{ //创建头结点 private HHeroNode3 head = new HHeroNode3(0); //删除节点 public void del(int no){ if (head.getNext() == null){ System.out.println("链表为空！！！"); return; } HHeroNode3 temp = head.getNext(); boolean flag = false; while (true){ if (temp == null){ break; } if (temp.getNo() == no){ flag = true; break; } temp = temp.getNext(); } if (flag){ temp.getPre().setNext(temp.getNext()); if (temp.getNext() != null){ temp.getNext().setPre(temp.getPre()); } }else { System.out.println("链表中不存在这个数！！！"); } } //按照编号顺序添加到链表 public void addByOrder(HHeroNode3 node){ HHeroNode3 temp = head; boolean flag1 = false; boolean flag2 = false; while (true){ if (temp.getNext() == null){ break; } if (temp.getNext().getNo() == node.getNo()){ flag1 = true; break; }else if (temp.getNext().getNo() > node.getNo()){ flag2 = true; break; } temp = temp.getNext(); } if (flag1){ System.out.println("链表中已经存在此节点！！！"); }else if (flag2){ node.setNext(temp.getNext()); temp.getNext().setPre(node); node.setPre(temp); temp.setNext(node); }else { temp.setNext(node); node.setPre(temp); } } //添加节点到链表中 public void add(HHeroNode3 node){ HHeroNode3 temp = head; while (true){ if (temp.getNext() == null){ break; } temp = temp.getNext(); } temp.setNext(node); node.setPre(temp); } //展示链表 public void show(){ if (head.getNext() == null){ System.out.println("链表为空！！！"); return; } HHeroNode3 temp = head.getNext(); while (temp != null){ System.out.println(temp); temp = temp.getNext(); } } } class HHeroNode3{ private int no; private HHeroNode3 pre; private HHeroNode3 next; @Override public String toString() { return "HHeroNode3{" + "no=" + no + '}'; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public HHeroNode3 getPre() { return pre; } public void setPre(HHeroNode3 pre) { this.pre = pre; } public HHeroNode3 getNext() { return next; } public void setNext(HHeroNode3 next) { this.next = next; } public HHeroNode3(int no) { this.no = no; } }

刚开始学的时候 还写了另一个代码,注释比较多点，个人比较喜欢上面的代码

public class DoubleLinkListDemo { public static void main(String[] args) { HeroNode2 heroNode1 = new HeroNode2(5,"d","ddd"); HeroNode2 heroNode2 = new HeroNode2(10,"f","fff"); HeroNode2 heroNode3 = new HeroNode2(7,"g","ggg"); HeroNode2 heroNode4 = new HeroNode2(11,"h","hhh"); HeroNode2 heroNode5 = new HeroNode2(6,"j","jjj"); HeroNode2 heroNode6 = new HeroNode2(12,"jr","rrr"); DoubleLinkList d1 = new DoubleLinkList(); System.out.println("添加节点到双向链表-----"); // d1.add(heroNode1); // d1.add(heroNode2); // d1.add(heroNode3); // d1.add(heroNode4); // d1.add(heroNode5); // d1.list(); System.out.println("按照no的大小添加节点到双向链表-----"); d1.addByOrder(heroNode1); d1.addByOrder(heroNode5); d1.addByOrder(heroNode3); d1.addByOrder(heroNode4); d1.addByOrder(heroNode2); d1.addByOrder(heroNode6); System.out.println("遍历双向链表------"); d1.list(); // System.out.println("修改节点-----"); // HeroNode2 newHeroNode = new HeroNode2(4,"zz","zzz"); // d1.update(newHeroNode); // d1.list(); // System.out.println("删除节点-----"); // d1.del(2); // d1.list(); } } //创建一个双向链表的类 class DoubleLinkList{ //先初始化一个头结点，头结点不要动，不要存放具体的数据 private HeroNode2 head = new HeroNode2(0,"",""); //返回头结点 public HeroNode2 getHead() { return head; } //按照no排序进行添加 public void addByOrder(HeroNode2 heroNode){ //因head节点是不能动的，所以用一个临时变量来帮助找到添加的位置 HeroNode2 temp = head; boolean flag1 = false;//用于判断是不是链表的最后，默认是false boolean flag = false;//标志添加的编号是否存在，默认为false while (true){ //找到链表的最后节点 if (temp.next == null){ // 说明temp在链表的最后，然后直接退出指针并没有移动，当添加第二个节点时就可以判断新添加的节点与旧节点的大小 flag1 = true; break;//退出 } if (temp.next.no > heroNode.no){//位置找到了，就在temp的后面插入 break; }else if(temp.next.no == heroNode.no){//说明希望添加的heroNode的编号存在 flag = true;//说明编号存在 break; } //如果上面的条件都不满足时，则将指针向后边移 temp = temp.next; } //判断flag的值 if (flag){//不能添加，说明编号存在 System.out.printf("准备插入的英雄编号为%d 已经存在，不能添加了\n",heroNode.no); }else if (flag1){ //分情况考虑，这个是代表插入尾巴的插入方式 //在temp后面插入 heroNode.next = temp.next; temp.next = heroNode; heroNode.pre = temp; flag1 = false; }else {//这个是代表插入节点之间的方式 //插入到链表中 heroNode.next = temp.next; temp.next.pre = heroNode; temp.next = heroNode; heroNode.pre = temp; } } //添加节点到双向链表 public void add(HeroNode2 newHeadNode){ //因为head节点不能动，因此我们需要一个辅助变量来帮助遍历 HeroNode2 temp = head; //遍历链表，找到最后 while (true){ //找到链表的最后 if (temp .next == null){ break; } temp = temp.next; } temp.next = newHeadNode; newHeadNode.pre = temp; } /** * 从双向链表中删除一个节点 * 说明 * 1.对于双向链表，我们可以直接找到要删除的这个节点 * 2.找到后，自即删除即可 * @param no */ public void del(int no){ //判断当前链表是否为空 if (head.next == null){ System.out.println("链表是空,无法删除"); return; } HeroNode2 temp = head.next;//辅助变量(指针) boolean flag = false;//标志是否找到待删除节点 while (true){ if (temp == null){//已经到链表的最后 break; } if (temp.no == no){ //找到待删除节点的前一个节点的temp flag = true; break; } temp = temp.next; } if (flag){ //可以删除 双向链表 temp.pre.next = temp.next; //如果是最后一个节点，就不需要执行下面这句话，否则会出现空指针异常 if (temp.next.pre != null){ //w temp.next.pre = temp.pre; } }else { System.out.printf("要删除的%d节点不存在\n",no); } } //修改一个节点的内容，可以看到双向链表的节点内容修改和单链表的的内容修改是一样的 //只是节点类型改成HeroNode2 public void update(HeroNode2 node){ //判空 if (head.next == null){ System.out.println("链表时候空的!!!!"); return; } HeroNode2 temp = head.next; boolean flag = false; while (true){ if (temp == null){ break; } if (temp.no == node.no){ flag = true; break; } temp = temp.next; } if (flag){ temp.name = node.name; temp.nickname = node.nickname; }else { System.out.println("不存在这个节点"); } } //遍历双向链表的方法和单链表的方法 public void list(){ if (head.next == null){ System.out.println("这个链表是空链表----"); return; } HeroNode2 cur = head.next; while (cur != null){ System.out.println(cur); cur = cur.next; } } } //定义一个HeroNode2 每个HeroNode对象就是一个节点 class HeroNode2{ public int no; public String name; public String nickname; public HeroNode2 pre;//指向下一个节点，默认为null public HeroNode2 next; //指向下一个节点,默认为null //构造器 public HeroNode2(){} public HeroNode2(int hNo,String hName,String hNickname){ this.no = hNo; this.name = hName; this.nickname = hNickname; } //为了显示方便，重写toString @Override public String toString() { return "HeroNode2{" + "no=" + no + ", name='" + name + '\'' + ", nickname='" + nickname + '}'; } }