• 【21天学习挑战赛】双向链表的数据操作

    ​
    ​

    活动地址：CSDN21天学习挑战赛

    怕什么真理无穷，进一步有一份的欢喜。

    目录

    【21天学习挑战赛】双向链表的数据操作

    ✌我为什么参与挑战赛

    1，机缘

    读到研一了，暑假器件打开私信发现这个挑战赛就鼓起勇气参加了。

    2，期待的收获

    A, 本人在华南理工大学攻读专硕，目前研究方向是图像恢复，从事深度学习相关工作，目标是从事Java后端开发。
    B, 期待您的反馈，如果有什么不对的地方，欢迎指正！
    C, 期待认识志同道合的领域同行或技术交流。
    如果感觉博主的文章还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦

    🍉什么是双向链表？

    双向链表的定义是，一个节点有两个方向，分别储存当前节点的前驱节点，和后续节点；
    双向链表属于链式存储结构，属于数据结构的一种。
    在这里插入图片描述

    💬数据操作的定义

    对数据实施的步骤，每种数据结构都有一组对应的运算，最常用的运算有查询，插入，删除，更新和排序。数据操作最终需要在对应的数据结构上进行算法的实现。

    ✨双向链表的优劣

    优势

    便于数据的修改，在对元素进行插入或者删除操作时仅需修改对应节点的引用，不必移动节点。

    劣势

    存储空间利用率较低，每次添加节点时都需要2个指向，额外增加了内存空间消耗。

    🍵双向链表的数据操作的步骤

    1、定义节点

    每个节点由前驱节点、后驱节点和数据构成

    ✍️ 算法实现

    class Node {
    public Integer num = null;\\数据
    public Node previous = null;\\前驱节点
    public Node next = null;\\后驱节点

    public Node(int num) {
        this.num = num;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    2、插入数据

    大致分为三种方式，步骤如下:

    1. 表头插入节点
      • 将新节点的前驱节点指向null
      • 新节点的后续节点指向表头
      • 将表头的前驱节点指向新节点
    2. 表尾插入节点
      • 表尾的后续节点指向新节点
      • 新节点的前驱节点指向表尾
      • 新节点的后续节点指向null
    3. 指定位置插入节点
      • 假设在AB直接插入新节点C
      • A 节点的后续节点指向 C
      • C 节点 的前驱节点指向 A
      • C 节点的后续节点指向 B
      • B 节点的前驱节点指向 C

    ✍️ 算法实现

    class DouLinkedList {
    private Node head = null;
	 /**
     * 表头插入节点
     * 1 将新节点的前驱节点指向null
     * 2 新节点的后续节点指向表头
     * 3 将表头的前驱节点指向新节点
     *
     * @param data
     */
    public void addFirst(int data) {
        //创建新节点
        Node newNode = new Node(data);
        // 如果表头为空直接将新节点作为头
        if (head == null) {
            head = newNode;
        } else {
            // 1将新节点的前驱节点指向null(声明的时候本来就是null)
            // 2新节点的后续节点指向表头
            newNode.next = head;
            // 3将表头的前驱节点指向新节点
            head.previous = newNode;
            // head重新赋值
            head = newNode;
        }
    }
	/**
     * 表尾插入节点
     * 思路 ：
     * 1 表尾的后续节点指向新节点
     * 2 新节点的前驱节点指向表尾
     * 3 新节点的后续节点指向null
     *
     * @param data
     */
    public void addLast(int data) {
        //创建新节点
        Node newNode = new Node(data);
        // 如果表头为空直接将新节点作为头
        if (head == null) {
            head = newNode;
        } else {
            Node currentNode = head;
            // 寻找尾节点,遍历链表到尾结点
            while (currentNode.next != null) {
                currentNode = currentNode.next;
            }
            // 1表尾的后续节点指向新节点
            currentNode.next = newNode;
            // 2新节点的前驱节点指向表尾
            newNode.previous = currentNode;
            // 3新节点的后续节点指向null(声明的时候本来就是null)
        }
    }
    /**
     * 指定位置插入节点
     * 假设在AB直接插入新节点C
     * 1 A 节点的后续节点指向 C
     * 2 C 节点 的前驱节点指向 A
     * 3 C 节点的后续节点指向 B
     * 4 B 节点的前驱节点指向 C
     *
     * @param data
     * @param index
     */
    public void add(int data, int index) {
        int length = length();
        // 索引超出，非法
        if (index < 0 || index > length) {
            System.out.println("非法索引");
            return;
        }
        // 如果索引为0，调用addFirst方法
        if (index == 0) {
            addFirst(data);
            return;
        }
        // 如果索引等于链表的长度，调用addLast方法
        if (index == length) {
            addLast(data);
            return;
        }
        // 创建新节点
        Node newNode = new Node(data);
        // 当前节点
        Node currentNode = head;
        // 定义指针
        int point = 0;
        // 寻找插入新节点B的前驱节点A
        while ((index - 1) != point) {
            currentNode = currentNode.next;
            point++;
        }
        // currentNode:A
        // nextNode(currentNode.next):B
        // newNode:C
        // 转存当前节点的后续节点B
        Node nextNode = currentNode.next;
        // 1当前节点的后续节点指向新节点C
        currentNode.next = newNode;
        // 2新接的前驱节点指向当前节点
        newNode.previous = currentNode;
        // 3新节点的后续节点指向转存的节点
        newNode.next = nextNode;
        // 4转存节点的前驱节点指向新节点
        nextNode.previous = newNode;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108

    3、获取链表长度

    遍历链表，一个节点代表一个单位的长度

    ✍️ 算法实现

       /**
     * 获得链表长度
     * 遍历链表，一个节点代表一个单位的长度
     *
     * @return
     */
    public int length() {
        int length = 0;
        // 当前节点
        Node currentNode = head;
        while (currentNode != null) {
            // 一个节点 length 长度就加1
            length++;
            // 将下一个节点作为当前节点
            currentNode = currentNode.next;
        }
        return length;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    4、打印链表

    从链表的头遍历到链表的尾巴

    ✍️ 算法实现

        /**
     * 顺序打印链表
     * 从链表的头遍历到链表的尾巴
     */
    public void displayNext() {
        // 将表头作为当前节点
        Node currentNode = head;
        // 遍历链表
        while (currentNode != null) {
            // 打印数据
            System.out.println(currentNode.num);
            // 将下一个节点作为当前节点
            currentNode = currentNode.next;
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    5、删除数据

    大致分为三种方式，步骤如下:

    1. 删除表头
      • 获取表头的后续节点
      • 将表头的后续节点的前驱节点指向null
      • 将表头的后续节点赋值给表头
    2. 删除表尾
      • 找到表尾的前驱节点 Node.next.next == null
      • 将表尾的前驱节点的后续节点置为null
    3. 指定位置删除节点
      • 假设有ABC节点要删除B节点
      • 将A节点的后续节点指向C节点
      • 将C节点前驱节点指向A节点

    ✍️ 算法实现

    	/**
     * 删除表头
     * 1 获取表头的后续节点
     * 2 将表头的后续节点的前驱节点指向null
     * 3 将表头的后续节点赋值给表头
     */
    public void removeFirst() {
        int length = length();
        if (length == 0) {
            return;
        }
        // 只有一个节点直接清空表头
        if (length == 1) {
            head = null;
            return;
        }
        // 获取表头的后续节点
        Node temNode = head.next;
        // 将表头的后续节点的前驱节点指向null
        temNode.previous = null;
        // 将表头的后续节点赋值给表头
        head = temNode;
    }

    /**
     * 删除表尾
     * 1 找到表尾的前驱节点 Node.next.next == null
     * 2 将表尾的前驱节点的后续节点置为null
     */
    public void removeLast() {
        if (length() == 0) {
            return;
        }
        // 只有一个节点直接清空表头
        if (length() == 1) {
            head = null;
            return;
        }
        Node previousNode = head;
        // 寻找尾节点的前驱节点
        while (previousNode.next.next != null) {
            previousNode = previousNode.next;
        }
        previousNode.next = null;
    }

    /**
     * 指定位置删除节点
     * 假设有ABC节点要删除B节点
     * 1 将A节点的后续节点指向C节点
     * 2 将C节点前驱节点指向A节点
     * @param index
     */
    public void remove(int index) {
        int length = length();
        if (index < 0 || index >= length) {
            System.out.println("非法索引");
            return;
        }
        // 头节点
        if (index == 0) {
            removeFirst();
            return;
        }
        // 尾节点
        if (index == (length - 1)) {
            removeLast();
            return;
        }
        // 欲想删除节点的前驱节点
        Node previousNode = head;
        // 定义指针
        int point = 0;
        // 寻找要删除节点B的前驱节点A
        while ((index - 1) != point) {
            previousNode = previousNode.next;
            point++;
        }
        // previousNode:A
        // previousNode.next:B
        // nextNode(previousNode.next.next):C
        // 获取想删除节点B的后续节点C
        Node nextNode = previousNode.next.next;
        // 将想删除节点B的前驱节点A的后续节点指向B的后续节点C
        previousNode.next = nextNode;
        // 将想删除节点B的后续节点C的前驱节点指向B的前驱节点A
        nextNode.previous = previousNode;

    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89

    🌞 完整代码

    package com.wpc.csdn.linkedList;

import org.junit.jupiter.api.Test;

public class LinkedList {
}

class Node {
    public Integer num = null;
    public Node previous = null;
    public Node next = null;

    public Node(int num) {
        this.num = num;
    }
}

class DouLinkedList {
    private Node head = null;

    /**
     * 表头插入节点
     * 1 将新节点的前驱节点指向null
     * 2 新节点的后续节点指向表头
     * 3 将表头的前驱节点指向新节点
     *
     * @param data
     */
    public void addFirst(int data) {
        //创建新节点
        Node newNode = new Node(data);
        // 如果表头为空直接将新节点作为头
        if (head == null) {
            head = newNode;
        } else {
            // 1将新节点的前驱节点指向null(声明的时候本来就是null)
            // 2新节点的后续节点指向表头
            newNode.next = head;
            // 3将表头的前驱节点指向新节点
            head.previous = newNode;
            // head重新赋值
            head = newNode;
        }
    }

    /**
     * 表尾插入节点
     * 思路 ：
     * 1 表尾的后续节点指向新节点
     * 2 新节点的前驱节点指向表尾
     * 3 新节点的后续节点指向null
     *
     * @param data
     */
    public void addLast(int data) {
        //创建新节点
        Node newNode = new Node(data);
        // 如果表头为空直接将新节点作为头
        if (head == null) {
            head = newNode;
        } else {
            Node currentNode = head;
            // 寻找尾节点,遍历链表到尾结点
            while (currentNode.next != null) {
                currentNode = currentNode.next;
            }
            // 1表尾的后续节点指向新节点
            currentNode.next = newNode;
            // 2新节点的前驱节点指向表尾
            newNode.previous = currentNode;
            // 3新节点的后续节点指向null(声明的时候本来就是null)
        }
    }

    /**
     * 获得链表长度
     * 遍历链表，一个节点代表一个单位的长度
     *
     * @return
     */
    public int length() {
        int length = 0;
        // 当前节点
        Node currentNode = head;
        while (currentNode != null) {
            // 一个节点 length 长度就加1
            length++;
            // 将下一个节点作为当前节点
            currentNode = currentNode.next;
        }
        return length;
    }

    /**
     * 指定位置插入节点
     * 假设在AB直接插入新节点C
     * 1 A 节点的后续节点指向 C
     * 2 C 节点 的前驱节点指向 A
     * 3 C 节点的后续节点指向 B
     * 4 B 节点的前驱节点指向 C
     *
     * @param data
     * @param index
     */
    public void add(int data, int index) {
        int length = length();
        // 索引超出，非法
        if (index < 0 || index > length) {
            System.out.println("非法索引");
            return;
        }
        // 如果索引为0，调用addFirst方法
        if (index == 0) {
            addFirst(data);
            return;
        }
        // 如果索引等于链表的长度，调用addLast方法
        if (index == length) {
            addLast(data);
            return;
        }
        // 创建新节点
        Node newNode = new Node(data);
        // 当前节点
        Node currentNode = head;
        // 定义指针
        int point = 0;
        // 寻找插入新节点B的前驱节点A
        while ((index - 1) != point) {
            currentNode = currentNode.next;
            point++;
        }
        // currentNode:A
        // nextNode(currentNode.next):B
        // newNode:C
        // 转存当前节点的后续节点B
        Node nextNode = currentNode.next;
        // 1当前节点的后续节点指向新节点C
        currentNode.next = newNode;
        // 2新接的前驱节点指向当前节点
        newNode.previous = currentNode;
        // 3新节点的后续节点指向转存的节点
        newNode.next = nextNode;
        // 4转存节点的前驱节点指向新节点
        nextNode.previous = newNode;
    }

    /**
     * 删除表头
     * 1 获取表头的后续节点
     * 2 将表头的后续节点的前驱节点指向null
     * 3 将表头的后续节点赋值给表头
     */
    public void removeFirst() {
        int length = length();
        if (length == 0) {
            return;
        }
        // 只有一个节点直接清空表头
        if (length == 1) {
            head = null;
            return;
        }
        // 获取表头的后续节点
        Node temNode = head.next;
        // 将表头的后续节点的前驱节点指向null
        temNode.previous = null;
        // 将表头的后续节点赋值给表头
        head = temNode;
    }

    /**
     * 删除表尾
     * 1 找到表尾的前驱节点 Node.next.next == null
     * 2 将表尾的前驱节点的后续节点置为null
     */
    public void removeLast() {
        if (length() == 0) {
            return;
        }
        // 只有一个节点直接清空表头
        if (length() == 1) {
            head = null;
            return;
        }
        Node previousNode = head;
        // 寻找尾节点的前驱节点
        while (previousNode.next.next != null) {
            previousNode = previousNode.next;
        }
        previousNode.next = null;
    }

    /**
     * 指定位置删除节点
     * 假设有ABC节点要删除B节点
     * 1 将A节点的后续节点指向C节点
     * 2 将C节点前驱节点指向A节点
     * @param index
     */
    public void remove(int index) {
        int length = length();
        if (index < 0 || index >= length) {
            System.out.println("非法索引");
            return;
        }
        // 头节点
        if (index == 0) {
            removeFirst();
            return;
        }
        // 尾节点
        if (index == (length - 1)) {
            removeLast();
            return;
        }
        // 欲想删除节点的前驱节点
        Node previousNode = head;
        // 定义指针
        int point = 0;
        // 寻找要删除节点B的前驱节点A
        while ((index - 1) != point) {
            previousNode = previousNode.next;
            point++;
        }
        // previousNode:A
        // previousNode.next:B
        // nextNode(previousNode.next.next):C
        // 获取想删除节点B的后续节点C
        Node nextNode = previousNode.next.next;
        // 将想删除节点B的前驱节点A的后续节点指向B的后续节点C
        previousNode.next = nextNode;
        // 将想删除节点B的后续节点C的前驱节点指向B的前驱节点A
        nextNode.previous = previousNode;

    }

    /**
     * 顺序打印链表
     * 从链表的头遍历到链表的尾巴
     */
    public void displayNext() {
        // 将表头作为当前节点
        Node currentNode = head;
        // 遍历链表
        while (currentNode != null) {
            // 打印数据
            System.out.println(currentNode.num);
            // 将下一个节点作为当前节点
            currentNode = currentNode.next;
        }
    }

    @Test
    public void test() {
        DouLinkedList douLinkedList = new DouLinkedList();
        for (int i = 0; i < 5; i++) {
            douLinkedList.addLast(i);
        }
//        douLinkedList.removeLast();
        douLinkedList.remove(3);
        douLinkedList.displayNext();
        System.out.println("*******************");
        System.out.println(douLinkedList.length());
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266

    如果觉得对你有帮助的话:
    👍 点赞，你的认可是我创作的动力！
    ⭐️ 收藏，你的青睐是我努力的方向！
    ✏️ 评论，你的意见是我进步的财富！

    ​​

  • 相关阅读:
    实时采集福利彩票的中奖信息和最新开奖信息-JAVA
    Map集合源码分析
    云原生之深入解析Prometheus Pushgetway的原理分析和实战操作
    浅析synchronized锁升级的原理与实现
    蛋白质致病突变的计算方法（二）
    超详细的MySQL三万字总结
    5-Spring架构源码分析-Spring IOC之 Spring 统一资源加载策略
    Pygame入门 2022 （1）
    浅读-《深入浅出Nodejs》
    无线通信技术_Fundamentals of Wireless Communication
  • 原文地址：https://blog.csdn.net/qq_41080854/article/details/126162543