JAVA 实现双向链表根据节点大小按顺序新增、修改、删除操作

单向链表查找的方向只能是一个方向，而双向链表可以向前或者向后查找。

结合

JAVA 实现带头结点的链表根据节点大小按顺序新增、修改、删除节点

单向链表的操作。在单向链表的基础上进行双向链表的增删改就比较简单了。

根据上图，分析双向链表的新增，修改、删除操作思路：

1) 遍历方和单链表一样，可以向前查找，也可以向后查找。本文使用向后查找的方式遍历双向链表。

2) 添加 (按照节点的大小顺序插入到双向链表中)

(1) 先通过遍历，找到双向链表中比新节点大的节点。如果找到链表中已存在要添加的新节点，则提示不能添加

(2)反之，则新节点的下个节点即为当前节点的下个节点 newHeroNode.next = temp.next;

(3)当前节点的下个节点为新节点 temp.next = doubleNode;新节点的前一节点为当前节点：doubleNode.previous = temp;

3) 修改思路和原单向链表的修改思路一样.找到双向链表中相同编号的节点，并直接修改

4) 删除节点

(1) 首先要设置一个temp节点，使用while循环遍历双向链表，查找到要删除的节点。

(2) 找到要删除的节点后，设置被删除节点的前一个节点的next 为被删除节点的next。

(3) 如果被删除节点的next不为空，则被删除节点的下个节点的previous为被删除节点的前一个节点temp.next.previous = temp.previous。

代码实现

1、先创建一个DoubleNode对象，即链表中的节点对象

class DoubleNode{
    public int no;
    public String name;
    public String nickName;
    public DoubleNode next;
    public DoubleNode previous;


    public DoubleNode(int no,String name,String nickName){
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "DoubleNode{" + "no=" + no + ", name='" + name  + "', nickName='" + nickName+"'}";
    }
}

2、创建DoubleLinkedList类，并定义全局头节点对象

 DoubleNode head = new DoubleNode(0,"","");

3、添加节点，按节点的编号顺序添加到双向链表

 //按节点的编号顺序添加
    public void addByOrder(DoubleNode doubleNode){
        //head节点不能动，所要需要一个临时节点 temp
        DoubleNode temp = head;
        boolean flag = false;
        //遍历链表，找到要添加的节点应插入的位置，如果节点的next为null，就代表找到了最后的节点
        while (true) {
            if(temp.next == null){
                break;
            }
            if(temp.no == doubleNode.no){
                flag = true;
                break;
            }else if(temp.next.no > doubleNode.no){
                break;
            }
            //当遍历的当前节点next不为Null时，则继续遍历，需要将临时节点后移
            temp = temp.next;
        }

        if(flag){
            System.out.printf("链表中已存在该编号%d节点，不能添加\n",doubleNode.no);
        }else{
            doubleNode.next = temp.next;
            if(temp.next !=null){
                temp.next.previous = doubleNode;
            }
            temp.next = doubleNode;
            doubleNode.previous = temp;
        }
    }

4、修改指定节点

public void update(DoubleNode doubleNode){
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        DoubleNode temp = head;
        boolean flag = false;
        while (true){
            if(temp.next == null && temp.no == doubleNode.no){
                flag = true;
                break;
            }
            if(temp.next != null && temp.no == doubleNode.no){
                flag = true;
                break;
            }
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }

        if(flag==true){
            temp.name = doubleNode.name;
            temp.nickName = doubleNode.nickName;
        }else{
            System.out.printf("链表中不存在编号为%d的节点，无法修改\n",doubleNode.no);
        }
    }

5、删除指定节点

 
    //删除指定编号的节点
    public void delete(int no){
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        DoubleNode temp = head;
        boolean flag = false;// 标志是否找到待删除节点的
        while (true){
            if((temp.next == null) && (temp.no == no)){
                flag = true;
                break;
            }
            if((temp.next != null) && temp.no == no){
                flag = true;
                break;
            }
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }

        if(flag){
            //被删除节点的前一个节点的next 为 被删除节点的next
            temp.previous.next = temp.next;
            if(temp.next !=null){
                //如果被删除节点的next不为空，则 被删除节点的下个节点的previous为被删除节点的前一个节点
                temp.next.previous = temp.previous;
            }
        }else{
            System.out.printf("链表中不存在编号为%d的节点，无法删除\n",no);
        }
    }

6、遍历双向链表

public void list(){
        //判断链表是否为空，如果为空则返回
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        //head节点不能动，所要需要一个临时节点 temp
        DoubleNode temp = head.next;
        while (true){
            //判断当前遍历的节点是否为空，为空则代表到了链表的最后
            if(temp == null){
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //将temp后移，继续遍历
            temp = temp.next;
        }
    }

7、创建测试类

public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        DoubleNode h1 = new DoubleNode(1,"AAA","A");
        DoubleNode h2 = new DoubleNode(2,"BBB","B");
        DoubleNode h3 = new DoubleNode(3,"CCC","C");
        DoubleNode h4 = new DoubleNode(4,"DDD","D");

        doubleLinkedList.addByOrder(h1);
        doubleLinkedList.addByOrder(h3);
        doubleLinkedList.addByOrder(h4);
        doubleLinkedList.addByOrder(h2);
        System.out.println("修改前的双链表打印--------------------");
        doubleLinkedList.list();

        DoubleNode h5 = new DoubleNode(5,"EEEE","E");
        doubleLinkedList.update(h5);
        System.out.println("修改后的双链表打印--------------------");
        doubleLinkedList.list();

        doubleLinkedList.delete(1);
        System.out.println("删除节点后的双链表打印--------------------");
        doubleLinkedList.list();
    }
}

输出结果：

修改前的双链表打印——————–

DoubleNode{no=1, name=’AAA’, nickName=’A’}

DoubleNode{no=2, name=’BBB’, nickName=’B’}

DoubleNode{no=3, name=’CCC’, nickName=’C’}

DoubleNode{no=4, name=’DDD’, nickName=’D’}

修改后的双链表打印——————–

DoubleNode{no=1, name=’AAA’, nickName=’A’}

DoubleNode{no=2, name=’BBB’, nickName=’B’}

DoubleNode{no=3, name=’CCC’, nickName=’C’}

DoubleNode{no=4, name=’EEEE’, nickName=’E’}

删除节点后的双链表打印——————–

DoubleNode{no=2, name=’BBB’, nickName=’B’}

DoubleNode{no=3, name=’CCC’, nickName=’C’}

DoubleNode{no=4, name=’EEEE’, nickName=’E’}

原文链接：https://blog.csdn.net/Sundy_sc/article/details/108011647

你可能也喜欢