Java双链表

小灰灰 2021-11-16 09:30 361阅读 0赞

## 一、概述 ##

![1007094-20190729154426250-1175775918.png][]

## 二、英雄类　 ##

1 class HeroNode {
     2     //值域
     3     public int id;
     4     public String name;
     5     public String nickName;
     6     //指针域
     7     public HeroNode next;
     8     public HeroNode prev;
     9 
    10     HeroNode(int id, String name, String nickName) {
    11         this.id = id;
    12         this.name = name;
    13         this.nickName = nickName;
    14     }
    15 }

## 三、主方法 ##

1     private  HeroNode head = null;
     2     private  HeroNode last = null;
     3     @Test
     4     public void test() {
     5        /* insertNodeBefore(new HeroNode(1, "松江", "及时雨"));
     6         insertNodeBefore(new HeroNode(2, "武松", "行者"));
     7         insertNodeBefore(new HeroNode(3, "林冲", "豹子头"));*/
     8         insertNodeAfter(new HeroNode(1, "松江", "及时雨"));
     9         insertNodeAfter(new HeroNode(2, "武松", "行者"));
    10         insertNodeAfter(new HeroNode(3, "林冲", "豹子头"));
    11 
    12         deleteNode(2);
    13         deleteNode(1);
    14         deleteNode(3);
    15         printLinkedLast();
    16     }

## 四、操作 ##

双链表操作跟单链表相差无几，所以只写了插入和打印操作

**　1、最前插入节点**

1 //插入新节点
     2     public void insertNode(HeroNode head, HeroNode newNode) {
     3         if (head == null) {
     4             System.out.println("头结点不能为空");
     5             return;
     6         }
     7         HeroNode hn = head;
     8         //循环到最后一个节点，它的next=null，即hn.next==null
     9         while (hn.next != null) {
    10             hn = hn.next;
    11         }
    12         //将hn.next指向新节点
    13         hn.next = newNode;
    14         //新节点的prev指向hn，即新节点的前一个节点
    15         newNode.prev = hn;
    16     }

**　　2、最后插入节点**

1     //插入新节点(插入最前面)
     2     public void insertNodeBefore(HeroNode newNode) {
     3         //如果插入的是第一个元素
     4         if(head==null){
     5             head = newNode;
     6             head.prev=null;
     7             head.next=null;
     8             last = head;
     9         }else {
    10             newNode.prev = null;
    11             newNode.next = head;
    12             head.prev = newNode;
    13             head = newNode;
    14         }
    15     }

**　3、打印双向链表(根据head向后遍历打印)**

1     //打印双向链表(根据head打印)
     2     public void printLinkedHead() {
     3         if (head == null) {
     4             System.out.println("链表为空");
     5             return;
     6         }
     7         HeroNode tmp = head;
     8         while (tmp!= null) {
     9             System.out.println(show(tmp));
    10             tmp = tmp.next;
    11         }
    12     }

**4、打印双向链表(根据last向前遍历打印)**

1 //打印双向链表(根据head打印)
     2     public void printLinkedLast() {
     3         if (last == null) {
     4             System.out.println("链表为空");
     5             return;
     6         }
     7         HeroNode tmp = last;
     8         while (tmp!= null) {
     9             System.out.println(show(tmp));
    10             tmp = tmp.prev;
    11         }
    12     }

**　　5、删除节点**

1     public  void deleteNode(int id){
     2         if (last == null) {
     3             System.out.println("链表为空");
     4             return;
     5         }
     6         HeroNode tmp = last;
     7         while (tmp!= null) {
     8             if(tmp.id==id){
     9                 //只有一个节点，
    10                 if(last.id==id && head.id==id){
    11                     head = null;
    12                     last = null;
    13                 }
    14                 //有两个节点，删除后一个
    15                 else if(last.id == id && head.id!=id){
    16                     head.next=null;
    17                     last = head;
    18                 }
    19                 //有两个节点，删除前一个
    20                 else if(head.id==id && last.id!=id){
    21                     last.prev = null;
    22                     head = last;
    23                 }
    24                 //有两个以上节点
    25                 else{
    26                     //当前节点的前一个节点的下一个节点，指向当前节点的下一个节点
    27                     tmp.prev.next=tmp.next;
    28                     //当前节点的下一个节点的前一个节点，指向当前节点的前一个节点
    29                     tmp.next.prev=tmp.prev;
    30                 }
    31                 return;
    32             }
    33             tmp = tmp.prev;
    34         }
    35     }

** **

5、打印的辅助方法

1 public String show(HeroNode h) {
     2         return "{" +
     3                 "本节点id=" + convertNode(h) + '\'' +
     4                 "id=" + h.id +
     5                 ", name='" + h.name + '\'' +
     6                 ", nickName='" + h.nickName + '\'' +
     7                 ", prev=" + convertNode(h.prev) + '\'' +
     8                 ", next=" + convertNode(h.next) + '\'' +
     9                 '}' + "\n";
    10     }
    11 
    12     //格式化HeroNode，直接输出地址值
    13     public String convertNode(HeroNode h) {
    14         return h == null ? null : h.toString().substring(h.toString().lastIndexOf('@'));
    15     }

## 五、结果展示 ##

![1007094-20190729155100135-745671024.png][]

[1007094-20190729154426250-1175775918.png]: /images/20211116/9aba87ae2aa54bdf92f7a42ccc645fd9.png
[1007094-20190729155100135-745671024.png]: /images/20211116/fef7ae9575534501b650200bc581a68a.png