数据结构:图文详解双向链表的各种操作(头插法,尾插法,任意位置插入,查询节点,删除节点,求链表的长度... ...)

简介: 数据结构:图文详解双向链表的各种操作(头插法,尾插法,任意位置插入,查询节点,删除节点,求链表的长度... ...)

前言:在上一篇文章中,我们认识了链表中的单链表,而本篇文章则是介绍线链表中的另一个结构双向链表,有兴趣的朋友们可以点击了解:图文详解单链表的各种操作



一.双向链表的概念

双向链表(Doubly Linked List)是一种数据结构,它与单向链表相似,但每个节点不仅包含指向下一个节点的指针,还包含指向上一个节点的指针。


双向链表的每个节点通常包含以下两个指针:


  • prev:指向上一个节点
  • next:指向下一个节点

通过这两个指针,可以在双向链表中沿着两个方向遍历。


相比于单向链表,双向链表能够更方便地进行插入和删除操作。因为每个节点包含指向前一个节点的指针,所以在删除或插入一个节点时,只需要修改该节点前后节点的指针即可。而在单向链表中,则需要在删除或插入节点时,找到该节点的前一个节点,以便进行指针修改,显得相对麻烦。


二.双向链表的数据结构

双向俩表有俩个指针,分别存放前驱节点的地址和后继节点的地址,如图所示



对于其中每一个节点,我们可以如下存储

    public class Node{
        public int data;
        public Node prev;
        public Node next;
        //构造方法,给每个节点赋值
        public Node(int data) {
            this.data = data;
        }
    }

 

而我们的链表则是需要将所有的节点封装起来,放进一个数据结构中,因此将刚才定义的节点类作为链表的内部类即可,而链表又需要实现各种各样的功能,我们可以将所有的链表的功能抽象出一个接口,然后通过链表去具体的实现那些功能

public class MyLinkList implements Ilst{
    //节点的数据结构
    public class Node{
        public int data;
        public Node prev;
        public Node next;
        //构造方法
        public Node(int data) {
            this.data = data;
        }
    }
    public Node head;//头节点
    public Node last;//尾节点
}


接口:

public interface Ilst {
    //头插法
    public void addFirst(int data);
    //尾插法
    public void addLast(int data);
    //任意位置插入
    public void addIndex(int index,int data);
    //查找是否包含关键字key是否在链表当中
    public boolean contains(int key);
    //删除第一次出现关键字为key的节点
    public void remove(int key);
    //删除所有值为key的节点
    public void removeAllKey(int key);
    //得到链表的长度
    public int size();
    //展示链表
    public void display();
    //清空链表
    public void clear();
}



三.双向链表的实现

节点的插入

节点的插入分为三种情况,一是在链表最前面进行插入也就是头插法,二是在链表末尾进行插入,也就是尾插法,三是在链表中间位置插入


头插法

如图所示有一个新的节点,我们需要将其插入头节点的位置



第一步:将目标节点的后继指针指向头节点位置的节点



第二步,将头节点的前驱指针指向目标节点



在使用代码具体实现的时候,需要对异常做出判断,假如头节点为空,也就是链表里面没有节点的时候,我们就直接让我们要新加的节点既是头节点,又是尾节点;在做出异常处理后,我们就可以按照刚才图示的过程进行头插了,但是需要注意的是,在完成头插后需要更新头节点的位置

    @Override//头插法
    public void addFirst(int data) {
        Node newNode = new Node(data);
        if (head == null){
            head = newNode;
            last = newNode;
        }else {
            newNode.next = head;
            head.prev = newNode;
            //更新头节点
            head = newNode;
        }
    }

 

尾插法

如图所示有一个新的节点,我们需要将其插入链表的末尾



第一步:将目标节点的前驱指针指向尾部节点



第二步:将尾部节点的后继指针指向目标节点



在使用代码具体实现的时候,需要对异常做出判断,假如头节点为空,也就是链表里面没有节点的时候,我们就直接让我们要新加的节点既是头节点,又是尾节点;在做出异常处理后,我们就可以按照刚才图示的过程进行尾插了,但是需要注意的是,在完成头插后需要更新尾部节点的位置

    @Override//尾插法
    public void addLast(int data) {
        Node newNode =  new Node(data);
        if (head == null){
            head = newNode;
            last = newNode;
        }else {
            newNode.prev = last;
            last.next = newNode;
            //更新尾部节点
            last = newNode;
        }
    }


任意位置插入

如图,假如想让新节点插入第三个节点的位置,该如何做呢?



第一步:先将目标节点的后继指针指向要插入节点的后一个节点


第二步:将目标节点的前驱指针指向插入节点


第三步:将插入节点的后继指针指向目标节点



第四步:将插入节点的后一个节点的前驱指针指向目标节点



对于节点的插入,最难的一点便是这4个步骤的顺序,顺序不是一成不变也不必死背,只需要记住一个原则——保证链表不断,在这个原则的基础上进行操作就不会出现问题了,也就是说在我们插入的时候,不要因为先去处理前面的节点导致找不到后面的节点就可以,因此我们在对链表进行插入操作的时候,一般都习惯先对后面的节点进行操作。


对于输入的位置我们要进行合法性的判断,如果在最前面就刚好使用头插法,如果是最后面就使用尾插法,之后遍历找到我们要插入的位置

    @Override//任意位置插入
    public void addIndex(int index, int data) {
        //对输入位置进行判断
        if (index < 0 || index > size()) {
            System.out.println("输入位置不合法");
            return;
        }
        if (index == 0) {
            //如果插入位置在最前面就使用头插
            addFirst(data);
            return;
        }
        if (index == size()) {//这里的size方法在后文中有定义
            //如果插入位置在最后面就使用尾插
            addLast(data);
            return;
        }
        //在中间插入
        Node newNode = new Node(data);
        //找到要插入的位置
        Node cur = head;
        while (index != 1) {
            cur = cur.next;
            index--;
        }
        //将新节点插入到cur之前
        newNode.next = cur;
        newNode.prev = cur.prev;
        cur.prev.next = newNode;
        cur.prev = newNode;
//        //将新节点插入到cur之后
//        newNode.next = cur.next;
//        newNode.prev = cur;
//        cur.next = newNode;
//        newNode.next.prev = newNode;
    }

 


节点的删除

对于节点的删除我们分为俩种,一种的将单个节点进行删除,一种是将所有与目标值相同的节点进行删除


删除链表中第一次出现的目标节点

如图,我们假定我们要删除链表中第三个节点



第一步:将删除节点的前驱节点的后继指针指向删除节点的后继节点



第二步:将删除节点的后继节点的前驱指针指向删除节点的前驱节点



对于上面俩个过程只是俩行代码就可以解决:

cur.next.prev = cur.prev;
cur.prev.next = cur.next;


删除的过程非常简单,但是要找到正确的位置并不是一件容易事,就算找到后也要进行合法性的判断,具体代码如下:

    @Override//删除第一次出现关键字为key的节点
    public void remove(int key) {
        Node cur = head;
        while (cur != null) {
            if(cur.data == key) {
                if(cur == head) {
                    head = head.next;
                    if(head != null) {
                        head.prev = null;
                    }else {
                        //只有一个节点 且是需要删除的节点
                        last = null;
                    }
                }else {
                    if(cur.next != null) {
                        //删除中间节点
                        cur.next.prev = cur.prev;
                        cur.prev.next = cur.next;
                    }else {
                        //删除尾巴节点
                        cur.prev.next = cur.next;
                        last = last.prev;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }

 


删除链表中所有与关键字相同的节点

对于和刚才唯一不同的点就是我们在删除一个点后不需要停止返回,继续遍历整个链表进行删除即可,这里就不再赘述

    @Override//删除所有值为key的节点
    public void removeAllKey(int key) {
        Node cur = head;
        while (cur != null) {
            if(cur.data == key) {
                if(cur == head) {
                    head = head.next;
                    if(head != null) {
                        head.prev = null;
                    }else {
                        //只有一个节点 且是需要删除的节点
                        last = null;
                    }
                }else {
                    if(cur.next != null) {
                        //删除中间节点
                        cur.next.prev = cur.prev;
                        cur.prev.next = cur.next;
                    }else {
                        //删除尾巴节点
                        cur.prev.next = cur.next;
                        last = last.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }



节点的查找

对于节点的查找,只需要挨个遍历判断就可以

    @Override//查找是否包含关键字key是否在链表当中
    public boolean contains(int key) {
        Node cur = head;
        while (cur != null){
            if (cur.data == key){
                return true;
            }else {
                cur = cur.next;
            }
        }
        return false;
    }

 

链表的清空

清空链表需要对每个节点进行清空,因此我们遍历整个链表然后进行赋值为空就可以,但是有一点需要注意,我们在删除每一个节点的后继指针之前得先做临时的记录,不然我们删除了一个节点的后继指针后就无法通过它访问后一个节点了

    @Override//清空链表
    public void clear() {
        Node cur = head;
        while (cur != null){
            Node tempNode = cur.next;//记录当前节点的下一个节点的地址
            cur.prev = null;
            cur.next = null;
            cur = tempNode;
        }
        this.head = null;
        this.last = null;
    }

 

链表的长度

求链表的长度只需要使用计数器遍历累加就可以

    @Override//得到单链表的长度
    public int size() {
        int count = 0;
        Node cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

 

四.模拟实现链表的完整代码

package MyLinkList;
public class MyLinkList implements Ilst {
    public class Node {
        public int data;
        public Node prev;
        public Node next;
        //构造方法
        public Node(int data) {
            this.data = data;
        }
    }
    public Node head;
    public Node last;
    @Override//头插法
    public void addFirst(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            last = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            //更新头节点
            head = newNode;
        }
    }
    @Override//尾插法
    public void addLast(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            last = newNode;
        } else {
            newNode.prev = last;
            last.next = newNode;
            //更新尾部节点
            last = newNode;
        }
    }
    @Override//任意位置插入
    public void addIndex(int index, int data) {
        //对输入位置进行判断
        if (index < 0 || index > size()) {
            System.out.println("输入位置不合法");
            return;
        }
        if (index == 0) {
            //如果插入位置在最前面就使用头插
            addFirst(data);
            return;
        }
        if (index == size()) {
            //如果插入位置在最后面就使用尾插
            addLast(data);
            return;
        }
        //在中间插入
        Node newNode = new Node(data);
        //找到要插入的位置
        Node cur = head;
        while (index != 1) {
            cur = cur.next;
            index--;
        }
        //将新节点插入到cur之前
        newNode.next = cur;
        newNode.prev = cur.prev;
        cur.prev.next = newNode;
        cur.prev = newNode;
//        //将新节点插入到cur之后
//        newNode.next = cur.next;
//        newNode.prev = cur;
//        cur.next = newNode;
//        newNode.next.prev = newNode;
    }
    @Override//查找是否包含关键字key是否在链表当中
    public boolean contains(int key) {
        Node cur = head;
        while (cur != null){
            if (cur.data == key){
                return true;
            }else {
                cur = cur.next;
            }
        }
        return false;
    }
    @Override//删除第一次出现关键字为key的节点
    public void remove(int key) {
        Node cur = head;
        while (cur != null) {
            if(cur.data == key) {
                if(cur == head) {
                    head = head.next;
                    if(head != null) {
                        head.prev = null;
                    }else {
                        //只有一个节点 且是需要删除的节点
                        last = null;
                    }
                }else {
                    if(cur.next != null) {
                        //删除中间节点
                        cur.next.prev = cur.prev;
                        cur.prev.next = cur.next;
                    }else {
                        //删除尾巴节点
                        cur.prev.next = cur.next;
                        last = last.prev;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }
    @Override//删除所有值为key的节点
    public void removeAllKey(int key) {
        Node cur = head;
        while (cur != null) {
            if(cur.data == key) {
                if(cur == head) {
                    head = head.next;
                    if(head != null) {
                        head.prev = null;
                    }else {
                        //只有一个节点 且是需要删除的节点
                        last = null;
                    }
                }else {
                    if(cur.next != null) {
                        //删除中间节点
                        cur.next.prev = cur.prev;
                        cur.prev.next = cur.next;
                    }else {
                        //删除尾巴节点
                        cur.prev.next = cur.next;
                        last = last.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }
    @Override//得到单链表的长度
    public int size() {
        int count = 0;
        Node cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    @Override//展示链表
    public void display() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    @Override//清空链表
    public void clear() {
        Node cur = head;
        while (cur != null){
            Node tempNode = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = tempNode;
        }
        this.head = null;
        this.last = null;
    }
}



 本次的分享就到此为止了,希望我的分享能给您带来帮助,也欢迎大家三连支持,你们的点赞就是博主更新最大的动力!如有不同意见,欢迎评论区积极讨论交流,让我们一起学习进步!有相关问题也可以私信博主,评论区和私信都会认真查看的,我们下次再见


目录
相关文章
|
3月前
|
Java
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
|
2月前
|
存储 缓存 索引
从底层数据结构和CPU缓存两方面剖析LinkedList的查询效率为什么比ArrayList低
本文详细对比了ArrayList和LinkedList的查询效率,从底层数据结构和CPU缓存两个方面进行分析。ArrayList基于动态数组,支持随机访问,查询时间复杂度为O(1),且CPU缓存对其友好;而LinkedList基于双向链表,需要逐个节点遍历,查询时间复杂度为O(n),且CPU缓存对其帮助不大。文章还探讨了CPU缓存对数组增删操作的影响,指出缓存主要作用于读取而非修改。通过这些分析,加深了对这两种数据结构的理解。
47 2
|
2月前
|
分布式计算 Hadoop Unix
Hadoop-28 ZooKeeper集群 ZNode简介概念和测试 数据结构与监听机制 持久性节点 持久顺序节点 事务ID Watcher机制
Hadoop-28 ZooKeeper集群 ZNode简介概念和测试 数据结构与监听机制 持久性节点 持久顺序节点 事务ID Watcher机制
52 1
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现
|
2月前
|
存储 缓存
数据结构3——双向链表
数据结构3——双向链表
133 1
|
2月前
|
存储
探索数据结构:便捷的双向链表
探索数据结构:便捷的双向链表
|
4月前
|
JSON NoSQL MongoDB
MongoDB Schema设计实战指南:优化数据结构,提升查询性能与数据一致性
【8月更文挑战第24天】MongoDB是一款领先的NoSQL数据库,其灵活的文档模型突破了传统关系型数据库的限制。它允许自定义数据结构,适应多样化的数据需求。设计MongoDB的Schema时需考虑数据访问模式、一致性需求及性能因素。设计原则强调简洁性、查询优化与合理使用索引。例如,在构建博客系统时,可以通过精心设计文章和用户的集合结构来提高查询效率并确保数据一致性。正确设计能够充分发挥MongoDB的优势,实现高效的数据管理。
91 3
|
4月前
|
安全 C# 数据安全/隐私保护
WPF安全加固全攻略:从数据绑定到网络通信,多维度防范让你的应用固若金汤,抵御各类攻击
【8月更文挑战第31天】安全性是WPF应用程序开发中不可或缺的一部分。本文从技术角度探讨了WPF应用面临的多种安全威胁及防护措施。通过严格验证绑定数据、限制资源加载来源、实施基于角色的权限管理和使用加密技术保障网络通信安全,可有效提升应用安全性,增强用户信任。例如,使用HTML编码防止XSS攻击、检查资源签名确保其可信度、定义安全策略限制文件访问权限,以及采用HTTPS和加密算法保护数据传输。这些措施有助于全面保障WPF应用的安全性。
65 0
|
4月前
|
存储 测试技术
【初阶数据结构篇】双向链表的实现(赋源码)
因为头结点的存在,plist指针始终指向头结点,不会改变。
37 0
|
4月前
|
算法
【数据结构与算法】共享双向链表
【数据结构与算法】共享双向链表
28 0