搜索
首页Javajava教程Java如何实现双向链表

Java如何实现双向链表

Jun 02, 2023 pm 02:55 PM
java

1、双向链表

1.1 双向链表的每个节点组成包含节点数据,上一个节点(pre),下一个节点(next)

1.2 双向链表节点结构

class Node {
//节点数据data
        int data;
        Node pre;
        Node next;

        public Node(int data) {
            this.data = data;
        }
        public Node() {
            super();
        }
        

    }

2、双向链表的增删改查(crud)

2.1 双向链表的增删改查

public class DoubleLinkedList {
    private Node first;
    private Node current;

    private static class Node {

        int data;
        Node pre;
        Node next;

        public Node(int data) {
            super();
            this.data = data;
        }

        public Node() {
            super();
        }
        

    }

    public DoubleLinkedList() {
        super();
    }

    /**
     * 双向链表增加
     */
    public void add(int val) {
        // 如果是头结点
        if (first == null) {
            Node node = new Node(val);
            first = node;
            first.pre = null;
            first.next = null;
            current = first;
        } else {
            Node node = new Node(val);
            current.next = node;
            node.pre = current;
            current = node;
        }
    }

    /**
     * 双向链表的删除 删除所有值为val的元素
     */
    public void del(int val) {
        if (first == null) {
            System.out.println("双向链表为空,无法进行删除操作!");
        } else {
            
            Node node = first;
            while(true) {
                // 首节点的删除可能
                if (node.data == val) {
                    //如果只有一个节点
                    if(node.next==null) {
                        node=null;
                        first=null;
                        System.out.println("删除所有的"+val+"成功");
                        return;
                    }else {
                        node = node.next;
                        node.pre.next=null;
                        node.pre=null;
                        first=node;
                        //删除后重新循环判断首节点是否值相等
                        continue;
                    }
                
                    
                } else {
                    
                    while (node.next != null) {
                        if (node.data == val) {
                            node.pre.next = node.next;
                            node.next.pre = node.pre;
                            Node tempNode = node.pre;
                            node.pre=null;
                            node.next=null;
                            node = tempNode;
                        }
                        node = node.next;
                    }
                    // 末节点删除可能
                    if (node.data == val) {
                        node.pre.next=null;
                        node.pre=null;

                    }
                    System.out.println("删除所有的"+val+"成功");
                    //末节点判断完成后,结束循环
                    return;
                }
            }
        }

    }
    /**
     * 遍历双向链表操作
     */
    public void traverse() {
        if(first==null) {
            System.out.println("双向链表为空");
        }else {
            Node node = first;
            //循环遍历到倒数第二个节点截止
            while(node.next!=null) {
                System.out.print(node.data+" ");
                node=node.next;
            }
            //遍历最后一个节点
            System.out.print(node.data);
        }
    }
    /**
     * 双向链表插入操作,在所有值为value的后面插入一个数insert
     */
    public void insert(int value,int insert) {
        
        if(first==null) {
            System.out.println("双向链表为空,无法插入");
        }else {
            Node node = first;
            //循环遍历到倒数第二个节点截止
            while(node.next!=null) {
                if(node.data==value) {
                    Node insertNode = new Node(insert);
                    node.next.pre = insertNode;
                    insertNode.next = node.next;
                    node.next = insertNode;
                    insertNode.pre = node;
                }
                node=node.next;
            }
            //最后一个节点后插入
            if(node.data == value) {
                Node insertNode = new Node(insert);
                node.next = insertNode;
                insertNode.pre = node;
            }
            System.out.println();
            System.out.println("插入操作完成");
            
        }
    }
    /**
     * 双向链表修改数据,将所有值为val的修改为revised
     */
    public void revise(int val,int revised) {
        if(first==null) {
            System.out.println("双向链表为空,无法修改");
        }else {
            Node node = first;
            while (node.next!=null) {
                if(node.data == val) {
                    node.data = revised;
                }
                node=node.next;
            }
            if(node.data == val) {}
            node.data = revised;
        }
        System.out.println("修改操作完成");
    }
    /**
     * 查找双向链表中是否包含val值
     * @param val
     */
    public void contain(int val) {
        if(first==null) {
            System.out.println("链表为空,无法查找");
        }else {
            Node node = first;
            while(node!=null) {
                if(node.data==val) {
                    System.out.println("该链表中包含"+val+"的值");
                    return;
                }else {
                    node=node.next;
                }
            }
            System.out.println("该链表不包含"+val);
        }
    }

}

2.2 测试类(main入口函数)

public class Main {
    public static void main(String[] args) {
        DoubleLinkedList list = new DoubleLinkedList();

        list.add(1);
        list.add(1);
        list.add(2);
        list.insert(1, 3);
        list.add(2);
        list.add(3);
        list.traverse();
        System.out.println();
        list.del(1);
    
        list.traverse();
        list.add(4);
        System.out.println();
        list.traverse();
        System.out.println();
        list.contain(4);
        
        list.contain(3);
        list.contain(0);

    }
}

3、一些缺点待修改

1)、循环结束是到倒数第二个节点截止的,要考虑多种不同的情况,头节点删除,尾结点删除等,导致删除函数复杂了很多
2)、在contain函数中有修改到循环到最后一个节点
3)、后续对删除函数修改有空再操作(待完成)

以上是Java如何实现双向链表的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文转载于:亿速云。如有侵权,请联系admin@php.cn删除
如何将Maven或Gradle用于高级Java项目管理,构建自动化和依赖性解决方案?如何将Maven或Gradle用于高级Java项目管理,构建自动化和依赖性解决方案?Mar 17, 2025 pm 05:46 PM

本文讨论了使用Maven和Gradle进行Java项目管理,构建自动化和依赖性解决方案,以比较其方法和优化策略。

如何使用适当的版本控制和依赖项管理创建和使用自定义Java库(JAR文件)?如何使用适当的版本控制和依赖项管理创建和使用自定义Java库(JAR文件)?Mar 17, 2025 pm 05:45 PM

本文使用Maven和Gradle之类的工具讨论了具有适当的版本控制和依赖关系管理的自定义Java库(JAR文件)的创建和使用。

如何使用咖啡因或Guava Cache等库在Java应用程序中实现多层缓存?如何使用咖啡因或Guava Cache等库在Java应用程序中实现多层缓存?Mar 17, 2025 pm 05:44 PM

本文讨论了使用咖啡因和Guava缓存在Java中实施多层缓存以提高应用程序性能。它涵盖设置,集成和绩效优势,以及配置和驱逐政策管理最佳PRA

如何将JPA(Java持久性API)用于具有高级功能(例如缓存和懒惰加载)的对象相关映射?如何将JPA(Java持久性API)用于具有高级功能(例如缓存和懒惰加载)的对象相关映射?Mar 17, 2025 pm 05:43 PM

本文讨论了使用JPA进行对象相关映射,并具有高级功能,例如缓存和懒惰加载。它涵盖了设置,实体映射和优化性能的最佳实践,同时突出潜在的陷阱。[159个字符]

Java的类负载机制如何起作用,包括不同的类载荷及其委托模型?Java的类负载机制如何起作用,包括不同的类载荷及其委托模型?Mar 17, 2025 pm 05:35 PM

Java的类上载涉及使用带有引导,扩展程序和应用程序类负载器的分层系统加载,链接和初始化类。父代授权模型确保首先加载核心类别,从而影响自定义类LOA

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
4 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
4 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
4 周前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解锁Myrise中的所有内容
1 个月前By尊渡假赌尊渡假赌尊渡假赌

热工具

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

安全考试浏览器

安全考试浏览器

Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

螳螂BT

螳螂BT

Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。

WebStorm Mac版

WebStorm Mac版

好用的JavaScript开发工具