双向链表

特点

  • 每个数据结点中都有两个指针，分别指向直接后继和直接前驱

  • 从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点

    代码实现

    ```java /**

    • @author laoduan

    • @create 2020-04-09-21:29 */ public class DoubleLinkedListDemo { public static void main(String[] args) {

      1. System.out.println("-------------------双向链表测试-----------------------\n\n");
  1.     HeroNode2 hero1 = new HeroNode2(1, "贾克斯", "武器大师");
  2.     HeroNode2 hero2 = new HeroNode2(2, "李青", "盲僧");
  3.     HeroNode2 hero3 = new HeroNode2(3, "凯瑟琳", "皮城女警");
  4.     HeroNode2 hero4 = new HeroNode2(4, "提莫", "迅捷斥候");
  7.     DoubleLinkedList doubleLinkedList = new DoubleLinkedList();

// doubleLinkedList.add(hero1); // doubleLinkedList.add(hero2); // doubleLinkedList.add(hero3); // doubleLinkedList.add(hero4); // System.out.println(“—————————-显示双向链表——————————\n”); // doubleLinkedList.list();

  1.     System.out.println("--------------------顺序添加-----------------\n\n");
  3.     doubleLinkedList.orderadd(hero2);
  4.     doubleLinkedList.orderadd(hero1);
  5.     doubleLinkedList.orderadd(hero4);
  6.     doubleLinkedList.orderadd(hero3);
  7.     doubleLinkedList.list();

// //修改 // HeroNode2 newHeroNode = new HeroNode2(2,”豹女”,”狂野女猎手”); // doubleLinkedList.update(newHeroNode); // System.out.println(“——————————-“); // doubleLinkedList.list(); // // //删除 // System.out.println(“————————-删除双向链表\n\n”); // doubleLinkedList.dele(3); // doubleLinkedList.list();

  1. }

}

class DoubleLinkedList{ private HeroNode2 head = new HeroNode2(0,””,””); public HeroNode2 getHead() { return head; } //显示 public void list(){ if(head.next==null){ System.out.println(“链表为空”); return; } //头结点不能动，创建一个temp HeroNode2 temp=head.next; while (true){ if(temp==null){ break; } System.out.println(temp); //将temp后移 temp=temp.next; } }

  1. //添加
  2. public void add(HeroNode2 heroNode){
  3.     HeroNode2 temp = head;
  4.     //遍历链表，找到最后
  5.     while (true){
  6.         if(temp.next==null){
  7.             break;
  8.         }
  9.         temp=temp.next;
  10.     }
  11.     //形成一个双向链表
  12.     temp.next=heroNode;
  13.     heroNode.pre=temp;
  14. }
  15. //按编号顺序添加
  16. public void orderadd(HeroNode2 heroNode){
  19.     HeroNode2 temp = head;
  20.     if(temp==null){
  21.         return;
  22.     }
  23.     while (true){
  24.         if (temp.next==null){
  25.             break;
  26.         }
  27.         if(temp.next.no>heroNode.no){
  28.             break;
  29.         }
  30.         temp=temp.next;
  31.     }
  32.     heroNode.next=temp.next;
  33.     heroNode.pre=temp;
  34.     temp.next=heroNode;
  35. }
  37. //修改一个结点,和单向链表基本一样，只是节点类型是heronode2
  38. public void update(HeroNode2 heroNode){
  39.     if (head.next==null){
  40.         System.out.println("链表为空");
  41.         return;
  42.     }
  43.     HeroNode2 temp = head;
  44.     boolean flag = false;
  45.     while (true){
  46.         if(temp.next.no==heroNode.no){
  47.             flag=true;
  48.             break;
  49.         }if(temp.next==null){
  50.             System.out.println("链表中没有你要找的结点");
  51.             break;
  52.         }
  53.         temp=temp.next;
  54.     }
  55.     if(flag){
  56.         temp.next.nickname=heroNode.nickname;
  57.         temp.next.name=heroNode.name;
  58.     }
  59. }
  61. //删除
  62. public void dele(int no){
  64.     //判断当前链表是否为空
  65.     if(head.next==null){
  66.         System.out.println("链表为空,无法删除");
  67.         return;
  68.     }
  69.     HeroNode2 temp = head.next;
  70.     boolean flag= false;
  72.     while (true){
  73.         if(temp==null){
  74.             System.out.println("链表中没有你要删的结点");
  75.             break;
  76.         }if(temp.no==no){
  77.             flag=true;
  78.             break;
  79.         }
  80.         temp=temp.next;
  81.     }
  82.     if(flag){
  83.         temp.pre.next=temp.next;
  84.         //如果是最后一个结点，就不需要执行下面一句话，否则空指针异常
  85.         if(temp.next!=null){
  86.             temp.next.pre=temp.pre;
  88.         }
  89.     }
  90.     else {
  91.         System.out.printf("要删除的%d结点不在",no);
  92.     }
  93. }

}

class HeroNode2{ public int no; public String name; public String nickname; public HeroNode2 next;//默认为null public HeroNode2 pre;

  1. //构造器
  2. public HeroNode2(int hNo,String hName,String hNickname){
  3.     this.no=hNo;
  4.     this.name=hName;
  5.     this.nickname=hNickname;
  6. }
  8. //重写toString
  9. @Override
  10. public String toString() {
  11.     return "HeroNode{" +
  12.             "no=" + no +
  13.             ", name='" + name + '\'' +
  14.             ", nickname='" + nickname + '\'' +
  15.             '}';
  16. }

} ```