搜索
首页Javajava教程Java数据结构之双向链表的实现方式

双向链表(Doubly linked list)

什么是双向链表?

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

双向链表与单向链表的主要区别: 

查找方向 : 单向链表的查找方向只能是一个方向,而双向链表可以向前或者向后查找。
删除: 单向链表的删除需要借助辅助指针,先找到要删除节点的前驱,然后进行删除。
           temp.next = temp.next.next;(temp为辅助指针)
           双向链表可以进行自我删除。 

双向链表与单向链表的优劣: 

优点:双链表结构比单链表结构更有优越性。

缺点:从存储结构来看,双向链表比单向链表多了一个指针,需要一个额外的、线性的内存使用量。(在32位操作系统中一个指针为4个字节,64位操作系统中一个指针为8个字节)。

双向链表的逻辑结构图解:

Java数据结构之双向链表如何实现

双向链表的具体操作: 

添加:
图解:

Java数据结构之双向链表如何实现

代码:

//添加一个节点到最后
    public void add(DoubleNode newNode) {
        DoubleNode temp = head;
        while (true) {
            if (temp.next == null) {
                // 当temp.next 为空时,证明temp为最后一个元素。
                temp.next = newNode; //temp节点的下一位指向新节点
                newNode.pre = temp;//新节点的前一位指向temp
                //这两步构成双向链表
                break;
            }else if (temp.next.ID == newNode.ID) {
                //ID相同证明 已经存在该学生。
                System.out.printf("要插入学号为%d的学生已经存在。\n", newNode.ID);
                break;
            }
            temp = temp.next;
        }
    }
 
    //按学号顺序添加节点
    public void Sortadd(DoubleNode newNode) {
        DoubleNode temp = head;
        while (true) {
            if (temp.next == null) {
                //说明要添加的节点序号在当前链表中最大,因此直接添加在末尾。
                temp.next = newNode;//temp节点的下一位指向新节点
                newNode.pre = temp;//新节点的前一位指向temp
                //这两步构成双向链表
                break;
            } else if (temp.next.ID > newNode.ID) {
                //当前节点的下一位节点的编号大于 要添加的新节点,则证明新节点要添加在temp节点之后
                newNode.next = temp.next;//要添加节点的下一位 指向temp当前节点的下一位
                temp.next.pre = newNode;//temp当前节点的下一位的前一位 指向 新节点构成双向链表
                temp.next = newNode; // 再让当前节点的下一位指向 新节点
                newNode.pre = temp;//新节点的前一位 指向 当前节点temp
                //这样连接完成后就将  新节点插入 到 原本链表的temp节点与temp.next节点之间
                break;
            }else if (temp.next.ID == newNode.ID) {
                //ID相同证明 已经存在该学生。
                System.out.printf("要插入学号为%d的学生已经存在。\n", newNode.ID);
                break;
            }
            temp = temp.next;
        }
    }

删除 :
图解:

Java数据结构之双向链表如何实现

代码:

 //删除一个节点。
    //自我删除
    public void DoubleDelete(int id) {
        if (head.next == null) {
            System.out.println("链表为空!");
            return;
        }
        DoubleNode temp = head.next;
        while (true) {
            if (temp == null) {
                System.out.printf("要删除的%d节点不存在\n", id);
                break;
            } else if (temp.ID == id) {
                //找到要删除节点
                // 此时temp 就代表将要被删除节点
                //temp.pre.next 指 当前要被删除节点 的前一位 的后一位
                // temp.next  指 当前要被删除节点的后一位
                temp.pre.next = temp.next;
                // (当前要被删除节点 的前一位 的后一位)指向 (当前要被删除节点的后一位)
                //这样就完成了 temp节点的删除操作
 
                // 如果是最后一个节点,就不需要执行下面这句话,否则出现空指针
                if (temp.next != null) {
                    temp.next.pre = temp.pre;
                }
                break;
            }
            temp = temp.next;
        }
    }

修改:
侃侃:它实际上与单链表的删除是一样。

代码:

//修改链表节点
    public void DoubleUpdate(DoubleNode newNode) {
        if (head.next == null) {
            System.out.println("链表为空!");
            return;
        }
        DoubleNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            } else if (temp.ID == newNode.ID) {
                //找到要修改的节点
                temp.name = newNode.name;
                temp.mark = newNode.mark;
                return;
            }
            temp = temp.next;
        }
        System.out.printf("要修改的%d节点不存在\n", newNode.ID);
    }

双向链表实例:

用双向链表创建一个学生信息管理系统,完成对学生信息的添加,删除,修改操作。

package Linkedlist;
 
//双向链表。
public class DoubleLinkedListDemo {
    public static void main(String agrs[]) {
        DoubleNode stu1 = new DoubleNode(6, "张三", 99);
        DoubleNode stu2 = new DoubleNode(2, "李四", 99);
        DoubleNode stu3 = new DoubleNode(3, "王五", 99);
        DoubleNode stu4 = new DoubleNode(5, "王二", 99);
        DoubleNode stu5 = new DoubleNode(4, "小红", 99);
        DoubleNode stu6 = new DoubleNode(1, "小明", 99);
        DoubleNode stu7 = new DoubleNode(1, "小明", 99);
 
        DoubleLinkedlist doubleLinkedlist = new DoubleLinkedlist();
 
       /* doubleLinkedlist.add(stu1);
        doubleLinkedlist.add(stu2);
        doubleLinkedlist.add(stu3);
        doubleLinkedlist.add(stu4);
        doubleLinkedlist.add(stu5);
        doubleLinkedlist.add(stu6);
        doubleLinkedlist.add(stu7);*/
 
        doubleLinkedlist.Sortadd(stu1);
        doubleLinkedlist.Sortadd(stu2);
        doubleLinkedlist.Sortadd(stu3);
        doubleLinkedlist.Sortadd(stu4);
        doubleLinkedlist.Sortadd(stu5);
        doubleLinkedlist.Sortadd(stu6);
        doubleLinkedlist.add(stu7);
 
        System.out.println("原链表展示!");
        doubleLinkedlist.ShowList();
        System.out.println();
 
        doubleLinkedlist.DoubleDelete(6);
        doubleLinkedlist.DoubleDelete(15);
        System.out.println("删除后链表展示!");
        doubleLinkedlist.ShowList();
        System.out.println();
 
 
        DoubleNode stu8 = new DoubleNode(1, "李思成", 100);
        DoubleNode stu9 = new DoubleNode(20, "李成", 100);
        doubleLinkedlist.DoubleUpdate(stu8);
        doubleLinkedlist.DoubleUpdate(stu9);
        System.out.println("修改后链表展示!");
        doubleLinkedlist.ShowList();
        System.out.println();
    }
}
 
class DoubleLinkedlist {
    private DoubleNode head = new DoubleNode(0, "", 0);
 
    public DoubleNode getHead() {
        return head;
    }
 
    //添加一个节点到最后
    public void add(DoubleNode newNode) {
        DoubleNode temp = head;
        while (true) {
            if (temp.next == null) {
                // 当temp.next 为空时,证明temp为最后一个元素。
                temp.next = newNode; //temp节点的下一位指向新节点
                newNode.pre = temp;//新节点的前一位指向temp
                //这两步构成双向链表
                break;
            }else if (temp.next.ID == newNode.ID) {
                //ID相同证明 已经存在该学生。
                System.out.printf("要插入学号为%d的学生已经存在。\n", newNode.ID);
                break;
            }
            temp = temp.next;
        }
    }
 
    //按学号顺序添加节点
    public void Sortadd(DoubleNode newNode) {
        DoubleNode temp = head;
        while (true) {
            if (temp.next == null) {
                //说明要添加的节点序号在当前链表中最大,因此直接添加在末尾。
                temp.next = newNode;//temp节点的下一位指向新节点
                newNode.pre = temp;//新节点的前一位指向temp
                //这两步构成双向链表
                break;
            } else if (temp.next.ID > newNode.ID) {
                //当前节点的下一位节点的编号大于 要添加的新节点,则证明新节点要添加在temp节点之后
                newNode.next = temp.next;//要添加节点的下一位 指向temp当前节点的下一位
                temp.next.pre = newNode;//temp当前节点的下一位的前一位 指向 新节点构成双向链表
                temp.next = newNode; // 再让当前节点的下一位指向 新节点
                newNode.pre = temp;//新节点的前一位 指向 当前节点temp
                //这样连接完成后就将  新节点插入 到 原本链表的temp节点与temp.next节点之间
                break;
            }else if (temp.next.ID == newNode.ID) {
                //ID相同证明 已经存在该学生。
                System.out.printf("要插入学号为%d的学生已经存在。\n", newNode.ID);
                break;
            }
            temp = temp.next;
        }
    }
 
    //删除一个节点。
    //自我删除
    public void DoubleDelete(int id) {
        if (head.next == null) {
            System.out.println("链表为空!");
            return;
        }
        DoubleNode temp = head.next;
        while (true) {
            if (temp == null) {
                System.out.printf("要删除的%d节点不存在\n", id);
                break;
            } else if (temp.ID == id) {
                //找到要删除节点
                // 此时temp 就代表将要被删除节点
                //temp.pre.next 指 当前要被删除节点 的前一位 的后一位
                // temp.next  指 当前要被删除节点的后一位
                temp.pre.next = temp.next;
                // (当前要被删除节点 的前一位 的后一位)指向 (当前要被删除节点的后一位)
                //这样就完成了 temp节点的删除操作
 
                // 如果是最后一个节点,就不需要执行下面这句话,否则出现空指针
                if (temp.next != null) {
                    temp.next.pre = temp.pre;
                }
                break;
            }
            temp = temp.next;
        }
    }
 
    //修改链表节点
    public void DoubleUpdate(DoubleNode newNode) {
        if (head.next == null) {
            System.out.println("链表为空!");
            return;
        }
        DoubleNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            } else if (temp.ID == newNode.ID) {
                //找到要修改的节点
                temp.name = newNode.name;
                temp.mark = newNode.mark;
                return;
            }
            temp = temp.next;
        }
        System.out.printf("要修改的%d节点不存在\n", newNode.ID);
    }
 
    public void ShowList() {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 因为头节点,不能动,因此我们需要一个辅助变量来遍历
        DoubleNode temp = head.next;
        while (true) {
            // 判断是否到链表最后
            if (temp == null) {
                break;
            }
            System.out.println(temp);// 输出节点的信息
            temp = temp.next;
        }
    }
}
 
class DoubleNode {
    public int ID; // 编号。
    public String name;
    public int mark;
    public DoubleNode next;
    public DoubleNode pre; // 前一个(Previous)
 
    public DoubleNode(int ID, String name, int mark) {
        this.ID = ID;
        this.name = name;
        this.mark = mark;
    }
 
    @Override
    public String toString() {
        return "DoubleNode{" + "ID=" + ID + ", name='" + name + '\'' + "mark=" + mark + '}';
    }
}

以上是Java数据结构之双向链表的实现方式的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文转载于:亿速云。如有侵权,请联系admin@php.cn删除
带你搞懂Java结构化数据处理开源库SPL带你搞懂Java结构化数据处理开源库SPLMay 24, 2022 pm 01:34 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于结构化数据处理开源库SPL的相关问题,下面就一起来看一下java下理想的结构化数据处理类库,希望对大家有帮助。

Java集合框架之PriorityQueue优先级队列Java集合框架之PriorityQueue优先级队列Jun 09, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于PriorityQueue优先级队列的相关知识,Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,下面一起来看一下,希望对大家有帮助。

完全掌握Java锁(图文解析)完全掌握Java锁(图文解析)Jun 14, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于java锁的相关问题,包括了独占锁、悲观锁、乐观锁、共享锁等等内容,下面一起来看一下,希望对大家有帮助。

一起聊聊Java多线程之线程安全问题一起聊聊Java多线程之线程安全问题Apr 21, 2022 pm 06:17 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于多线程的相关问题,包括了线程安装、线程加锁与线程不安全的原因、线程安全的标准类等等内容,希望对大家有帮助。

详细解析Java的this和super关键字详细解析Java的this和super关键字Apr 30, 2022 am 09:00 AM

本篇文章给大家带来了关于Java的相关知识,其中主要介绍了关于关键字中this和super的相关问题,以及他们的一些区别,下面一起来看一下,希望对大家有帮助。

Java基础归纳之枚举Java基础归纳之枚举May 26, 2022 am 11:50 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于枚举的相关问题,包括了枚举的基本操作、集合类对枚举的支持等等内容,下面一起来看一下,希望对大家有帮助。

java中封装是什么java中封装是什么May 16, 2019 pm 06:08 PM

封装是一种信息隐藏技术,是指一种将抽象性函式接口的实现细节部分包装、隐藏起来的方法;封装可以被认为是一个保护屏障,防止指定类的代码和数据被外部类定义的代码随机访问。封装可以通过关键字private,protected和public实现。

归纳整理JAVA装饰器模式(实例详解)归纳整理JAVA装饰器模式(实例详解)May 05, 2022 pm 06:48 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于设计模式的相关问题,主要将装饰器模式的相关内容,指在不改变现有对象结构的情况下,动态地给该对象增加一些职责的模式,希望对大家有帮助。

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.能量晶体解释及其做什么(黄色晶体)
2 周前By尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
1 个月前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

EditPlus 中文破解版

EditPlus 中文破解版

体积小,语法高亮,不支持代码提示功能

SublimeText3 英文版

SublimeText3 英文版

推荐:为Win版本,支持代码提示!

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

功能强大的PHP集成开发环境