模拟双向链表

简介: 模拟双向链表

前言



双向链表在单链表的基础上做了一些改进,所以本篇博客对于那些相似的地方,不再赘述,但不同的地方一定会讲到,读者有迷惑的地方,或者有兴趣,可以去看看我上周写的单链表博客。


一、双向、不带头、非循环链表的结构



模拟五个节点,每个节点有三个域:


第一个是数据域,存放的是元素

第二个是前驱指针域,存放的是当前节点的前一个节点的地址

第三个是后继指针域,存放的是当前节点的下一个节点的地址


3ed2fe9f42fc4488b9edaa9c408be57f.png


二、代码实现



1. 第一个 java 文件放的是两个类
一个类实现节点 Node,另一个类实现链表 Double_LinkedList


class Node{
    public int val;
    public Node prev;
    public Node next;
    public Node(int newval){
        this.val = newval;
    }
}
public class Double_LinkedList {
    public Node head;
    public Node last;
    //初始化链表  ✓
    public void initialList() {
        Node node1 = new Node(12);
        Node node2 = new Node(23);
        Node node3 = new Node(34);
        Node node4 = new Node(45);
        Node node5 = new Node(56);
        this.head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node2.prev = node1;
        node3.prev = node2;
        node4.prev = node3;
        node5.prev = node4;
        this.last = node5;
    }
    //打印链表中每个节点对应的 val  ✓
    public void print() {
        Node cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    //得到单链表的长度  ✓
    public int size() {
        int count = 0;
        Node cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    //头插法  ✓
    public void addFirst(int data) {
        Node newnode = new Node(data);
        if (this.head == null) {
            this.head = newnode;
            this.last = newnode;
            return;
        }
        newnode.next = this.head;
        this.head.prev = newnode;
        this.head = newnode;
    }
    //尾插法  ✓
    public void addLast(int data) {
        Node newnode = new Node(data);
        if (this.head == null) {
            this.head = newnode;
            this.last = newnode;
            return;
        }
        newnode.prev = this.last;
        this.last.next = newnode;
        this.last = newnode;
    }
    //findPos函数是为下面的 insertData 函数所添加,目的就是为了找到指针cur的位置  ✓
    public Node findPos(int pos) {
        Node cur = this.head;
        for (int i = 0; i < pos - 1; i++) {
            cur = cur.next;
        }
        return cur;
    }
    //任意位置插入,第一个数据节点为0号下标  ✓
    public void insertData(int pos, int data) {
        if (pos < 0 || pos > size()) {
            System.out.println("插入的位置不合法!");
        } else if (pos == 0) {
            addFirst(data);
        } else if (pos == size()) {
            addLast(data);
        } else {
            Node cur = findPos(pos);
            Node newnode = new Node(data);
            newnode.next = cur.next;
            newnode.prev = cur;
            cur.next = newnode;
            //注意,这里必须最后改变 cur.next 的指向
            //否则,原先的链表就会发生截断,也就是说找不到原先的那个 cur.next
        }
    }
    //查找是否包含关键字key是否在单链表当中  ✓
    public boolean contains(int key) {
        Node cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点  ✓
    public void remove(int key) {
        //头删
        if (this.head.val == key) {
            //考虑到链表中只有一个节点的情况
            if (this.head.next == null) {
                this.head = null;
                this.last = null;
                return;
            }
            this.head.next.prev = null;
            this.head = this.head.next;
            return;
        }
        //尾删
        if (this.last.val == key) {
            this.last.prev.next = null;
            this.last = this.last.prev;
            return;
        }
        //考虑其他情况
        //用flag记录当前链表中是否有这个 key 值
        Node cur = this.head;
        int flag = 0;
        while (cur != null) {
            if (cur.val == key) {
                flag = 1;
                break;
            }
            cur = cur.next;
        }
        if (flag == 0) {
            System.out.println("你所要删除的 key 在链表中找不到对应的节点值");
            return;
        }
        //中间删
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
    }
    //删除所有值为key的节点  ✓
    //只遍历了链表一次
    public void removeAllKey(int key) {
        Node cur = this.head;
        int flag = 0;
        while (cur != null) {
            if (cur.val == key) {
                //头删
                if (this.head.val == key) {
                    //考虑到链表中只有一个节点的情况
                    if (this.head.next == null) {
                        this.head = null;
                        this.last = null;
                        flag = 1;
                        return;
                    }
                    flag = 1;
                    this.head.next.prev = null;
                    this.head = this.head.next;
                } else if (cur.next != null) {
                    //中间删
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                    flag = 1;
                } else {
                    //尾删
                    this.last.prev.next = null;
                    this.last = this.last.prev;
                    flag = 1;
                }
            }
            cur = cur.next;
        }
        if (flag == 0) {
            System.out.println("你所要删除的key在链表中找不到对应的节点值val");
        }
    }
    //清空链表
    public void clear() {
        if(head == null){
            System.out.println("链表本身就为空,无法清空链表!");
        }else{
            Node cur = this.head;
            Node cur2 = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = cur2;
            this.head = null;
            this.last = null;
        }
    }
}


2. 第二个 java 文件放的是一个类 Test
目的是使用主函数来测试双向链表的一系列功能


public class Test {
    public static void main(String[] args) {
        Double_LinkedList test = new Double_LinkedList();
        test.initialList();
        test.print();
    }
}


三、框架分析



0. 对框架进行说明


(1)我所创建的框架是拆解了代码的方法(函数),把类中的每一个方法都拿出来仔细分析。


(2)我画图的地方可能有些不规范,比如地址的表示形式,比如箭头指向等等,我旨在表达逻辑,所以请读者自行理解,也请大佬多多指点。


1. 创建一个类 Node,表示节点


双向链表比单向链表多了一个前驱指针


class Node{
    public int val;
    public Node prev;
    public Node next;
    public Node(int newval){
        this.val = newval;
    }
}


2. 模拟链表内部结构


这里的思想和单链表相似,这里不再说明。


3. 初始化一个链表


public class Double_LinkedList {
    public Node head;
    public Node last;
    //初始化链表  ✓
    public void initialList() {
        Node node1 = new Node(12);
        Node node2 = new Node(23);
        Node node3 = new Node(34);
        Node node4 = new Node(45);
        Node node5 = new Node(56);
        this.head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node2.prev = node1;
        node3.prev = node2;
        node4.prev = node3;
        node5.prev = node4;
        this.last = node5;
    }
}


这里相较于单链表,多了一个 last 指针,它指向尾节点,在用代码实现的时候,要考虑进去,有些书上可能没有给出 last 这一指针,其实是一样的,只是给出 last 指针,会更好记录尾节点的前后情况。


4. 打印每个节点对应的 val


    //打印链表中每个节点对应的 val  ✓
    public void print() {
        Node cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }


5. 得到链表的长度


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


6. 头插法


    //头插法  ✓
    public void addFirst(int data) {
        Node newnode = new Node(data);
        if (this.head == null) {
            this.head = newnode;
            this.last = newnode;
            return;
        }
        newnode.next = this.head;
        this.head.prev = newnode;
        this.head = newnode;
    }


头插法的关键在于改变头指针 head 的地址,既然是双向链表,那么我们不仅要关心后继 next,同时也要考虑前驱 prev. 而此时,当链表为空的时候,头指针 head 和 尾指针 last 也要进行相关操作。


160a19974d634b91a410b179686cdece.png


7. 尾插法


    //尾插法  ✓
    public void addLast(int data) {
        Node newnode = new Node(data);
        if (this.head == null) {
            this.head = newnode;
            this.last = newnode;
            return;
        }
        newnode.prev = this.last;
        this.last.next = newnode;
        this.last = newnode;
    }


尾插法和头插法思想相同,不再赘述。但我们可以思考一个问题:当我们没有 last 指针的时候,我们该怎么找到最后一个节点呢?我们能做的只能是遍历链表了,这增加了时间复杂度。然而,有 last 指针,情况就大不相同了!


8. 在任一位置插入节点


    //findPos函数是为下面的 insertData 函数所添加,目的就是为了找到指针cur的位置  ✓
    public Node findPos(int pos) {
        Node cur = this.head;
        for (int i = 0; i < pos - 1; i++) {
            cur = cur.next;
        }
        return cur;
    }
    //任意位置插入,第一个数据节点为0号下标  ✓
    public void insertData(int pos, int data) {
        if (pos < 0 || pos > size()) {
            System.out.println("插入的位置不合法!");
        } else if (pos == 0) {
            addFirst(data);
        } else if (pos == size()) {
            addLast(data);
        } else {
            Node cur = findPos(pos);
            Node newnode = new Node(data);
            newnode.next = cur.next;
            newnode.prev = cur;
            cur.next = newnode;
            //注意,这里必须最后改变 cur.next 的指向
            //否则,原先的链表就会发生“截断”,也就是说找不到原先的那个 cur.next
        }
    }


这里和单链表的插入思想相同,这里不再赘述,唯一注意的地方就是下面三行代码的顺序,我们必须记住的是:当使用代码实现我们想要的结果时,地址不能被覆盖。


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


9. 查找关键字key是否在单链表当中


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


10. 删除第一次出现关键字为 key 的节点


    //删除第一次出现关键字为key的节点  ✓
    public void remove(int key) {
        //头删
        if (this.head.val == key) {
            //考虑到链表中只有一个节点的情况
            if (this.head.next == null) {
                this.head = null;
                this.last = null;
                return;
            }
            this.head.next.prev = null;
            this.head = this.head.next;
            return;
        }
        //尾删
        if (this.last.val == key) {
            this.last.prev.next = null;
            this.last = this.last.prev;
            return;
        }
        //考虑其他情况
        //用flag记录当前链表中是否有这个 key 值
        Node cur = this.head;
        int flag = 0;
        while (cur != null) {
            if (cur.val == key) {
                flag = 1;
                break;
            }
            cur = cur.next;
        }
        if (flag == 0) {
            System.out.println("你所要删除的 key 在链表中找不到对应的节点值");
            return;
        }
        //中间删
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
    }


这里代码实现可能写的有点啰嗦,本来想优化一下的,但是我发现这样的可读性更高,所以我决定就这样保留下来了,希望等我以后回过头看,会更清晰地理解。

//情况(1)头删


d13dd6f7e9264b61ae5274309803aee4.png


//情况(2)整个链表只有一个节点


8065b5835b504cf2a00a31fd7b48c904.png


//情况(3)中间删


179b99cc23ea48b39689ac23ff9aeeb0.png


//情况(4)尾删


3702b77c643d45fbba2501a1d91bfe18.png



11. 删除所有出现 key 的节点


    //删除所有值为key的节点  ✓
    public void removeAllKey(int key) {
        Node cur = this.head;
        int flag = 0;
        while (cur != null) {
            if (cur.val == key) {
                //头删
                if (this.head.val == key) {
                    //考虑到链表中只有一个节点的情况
                    if (this.head.next == null) {
                        this.head = null;
                        this.last = null;
                        flag = 1;
                        return;
                    }
                    flag = 1;
                    this.head.next.prev = null;
                    this.head = this.head.next;
                } else if (cur.next != null) {
                    //中间删
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                    flag = 1;
                } else {
                    //尾删
                    this.last.prev.next = null;
                    this.last = this.last.prev;
                    flag = 1;
                }
            }
            cur = cur.next;
        }
        if (flag == 0) {
            System.out.println("你所要删除的 key 在链表中找不到对应的节点值");
        }
    }


这里的代码与上一层的代码基本一致,只是去掉了 return。而我们真正要思考的是:双向链表与单链表实现此功能的区别在哪里,虽然两者思路一样,但是双向链表遍历链表的时候要容易想的多,因为这里给出了前驱 prev 指针,这使得串联节点的时候,就不怎么需要绕弯子了。


12. 清空链表


    //清空链表
    public void clear() {
        if(head == null){
            System.out.println("链表本身就为空,无法清空链表!");
        }else{
            Node cur = this.head;
            Node cur2 = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = cur2;
            this.head = null;
            this.last = null;
        }
    }


思路一:


可以遍历整个链表,把每个节点的指针域置成 null,这里要注意:要拿一个 cur2 指针来始终记录某个节点的后一个位置,这很关键。


思路二:


当然也可以直接写成如下代码,至于其余的,Java 的机制可以自动回收内存。


this.head = null;
  this.last = null;


四、测试程序



1. 初始化链表


public class Test {
    public static void main(String[] args) {
        Double_LinkedList test = new Double_LinkedList();
        test.initialList();
        test.print();
    }
}


输出结果:


32d378d6055f41ffba5ef4494dea2d5e.png


2. 插入功能


public class Test {
    public static void main(String[] args) {
        Double_LinkedList test = new Double_LinkedList();
        test.addFirst(1);
        test.addFirst(3);
        test.addFirst(5);
        test.addFirst(7);
        test.print();
        test.addLast(2);
        test.addLast(4);
        test.addLast(6);
        test.addLast(8);
        test.print();
        test.insertData(8,77);
        test.print();
        test.insertData(0,99);
        test.print();
        test.insertData(2,88);
        test.print();
    }
}


输出结果:


68ccd938029d4ad5a472a662b9bde2eb.png


3. 删除单节点


public class Test {
    public static void main(String[] args) {
        Double_LinkedList test = new Double_LinkedList();
        test.addLast(1);
        test.addLast(3);
        test.addLast(5);
        test.addLast(7);
        test.addLast(9);
        test.print();
        test.remove(9);
        test.print();
        test.remove(1);
        test.print();
        test.remove(5);
        test.print();
        test.remove(10);
    }
}


输出结果:


13518ccc324e432cb74a95ac7d40fb52.png


4. 删除指定的重复节点


public class Test {
    public static void main(String[] args) {
        Double_LinkedList test = new Double_LinkedList();
        test.addLast(2);
        test.addLast(3);
        test.addLast(5);
        test.addLast(2);
        test.addLast(2);
        test.addLast(9);
        test.addLast(2);
        test.print();
        test.removeAllKey(2);
        test.print();
    }
}



输出结果:


ca98189aa15e465fba5b9c45684320bf.png


5. 清空链表


public class Test {
    public static void main(String[] args) {
        Double_LinkedList test = new Double_LinkedList();
        test.addLast(2);
        test.addLast(3);
        test.addLast(5);
        test.addLast(2);
        test.addLast(2);
        test.addLast(9);
        test.addLast(2);
        test.clear();
        test.print();
    }
}


输出结果:


5f51bb9687a64255bfaa7909b6eb8eac.png


总结



  1. 经过大约 10 天左右的时间,我才把链表完整学完,对于链表的原理,光用眼看是不够的,必须得用代码实现,自己画画图,思路就很清晰了。记得上周实现单链表的时候,跟着老师的节奏,花了两天的时间才做出来,而今天早上花了半天时间,就自己把双向链表做出来了,而且只有很少一部分看了老师的代码。


  1. 这期间刷了牛客网和力扣的一些题目,才发现数据结构和算法是离不开的,有些题目的解法确实很难想到,希望自己能够继续努力,持续不断地积累。


473ebb05cabd4cc5b24a9cf4b395b0e1.jpg


Over. 谢谢观看哟~

目录
相关文章
|
存储 机器学习/深度学习 算法
模拟实现单链表、双链表、栈、队列——数组模拟
我们在数据结构中都学到过单链表、双链表、栈和队列,当我们实现的时候时使用结构体指针实现的。定义一个结构体,结构体中存储指针变量和存放数值的变量。当然,C++的STL库中已经有实现好的栈和队列,我们可以直接用。但是在做算法题时,有时候我们会发现超出时间限制。原因是我们用STL库中的栈和队列容器时,效率相对来说较慢。我们这时就引出用数组模拟实现栈和队列。用数组模拟实现的使用起来效率更高、更方便。当然,我们也会讲到用数组模拟实现单链表和双链表。
69 0
|
算法 C语言
【数据结构】顺序队列模拟实现
文章目录 一、队列的定义: 二、链式结构队列的模拟实现 1.结构图; 2.队列的结构体 3.初始化 4.销毁队列 5.入队(尾插) 6.出队(头删)
|
3月前
|
索引
02_设计链表
02_设计链表
|
6月前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
41 0
|
7月前
数据结构 模拟实现Queue队列(双链表模拟)
数据结构 模拟实现Queue队列(双链表模拟)
54 1
|
7月前
|
存储
数据结构 模拟实现LinkedList双向不循环链表
数据结构 模拟实现LinkedList双向不循环链表
72 1
|
7月前
|
存储
数据结构 模拟实现LinkedList单向不循环链表
数据结构 模拟实现LinkedList单向不循环链表
49 0
|
7月前
|
存储 缓存 算法
【数据结构-链表 八】【链表模拟】模拟设计LRU缓存结构
【数据结构-链表 八】【链表模拟】模拟设计LRU缓存结构
70 0
|
7月前
|
存储 测试技术
单链表的模拟实现
单链表的模拟实现
52 0
|
存储
【数据结构】模拟实现无头单向非循环链表
【数据结构】模拟实现无头单向非循环链表