devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【DS】链表的介绍和实现(单/双链表)_ds双链

作者：盐析白兔 | 2024-05-19 10:45:15

赞

踩

ds双链

在这里插入图片描述✨博客主页: XIN-XIANG荣
✨系列专栏:【Java实现数据结构】
✨一句短话: 难在坚持,贵在坚持,成在坚持!

文章目录

一. 链表的概念和分类

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

img实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

  • 单向或者双向

img

  • 带头或者不带头

img

  • 循环或者非循环

img

这里列出这8种链表结构

  1. 不带头单向不循环链表
  2. 不带头单向循环链表
  3. 不带头双向不循环链表
  4. 不带头双向循环链表
  5. 带头单向不循环链表
  6. 带头单向循环链表
  7. 带头双向不循环链表
  8. 带头双向循环链表

这里对于带头和不带头要注意区分一下 , 带头链表中链表的头节点是固定不变的且头节点的数值域是虚拟的 (无效的 , 不存放数据) , 不管数据在哪里插入和删除 , 头节点都不会变化 ; 而不带头链表 , 链表的第一个节点 (头节点) 是有效节点 , 数值域是有效的 , 如果在不带头链表中进行头插或者删除第一个节点 , 头节点会发生变化 .

本篇博客重点介绍下面两种链表 , 使用Java语言去实现 :

  • 无头单向非循环链表：

结构简单，一般不会单独用来存数据 ; 实际中更多是作为其他数据结构的子结构，如 哈希桶、图的邻接表等等。

  • 无头双向不循环链表 :

在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

二. 无头单向非循环链表实现

下图所示为无头单向非循环链表的结构

img

img

MySigleLinkedList.java

public class MySigleLinkedList {
    //内部类实现节点
    static class ListNode {
        public int val;//存放元素
        public ListNode next;//记录下一个节点的引用

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;//记录头节点的引用

    //打印链表里面的数据，默认从头开始打印
    public void display() {
        ListNode cur = this.head;
        //条件不能是cur.next,否则最后一个节点无法打印
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

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

    //查找某个数据key是否在单链表中
    public boolean contains(int key) {
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = this.head;
        this.head = node;
    }

    //尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        if(cur == null) {
            this.head = node;
        }else {
            //找到最后一个节点
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    //在任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) throws IndexWrongfulException{
        if(index < 0 || index > size()) {
            throw new IndexWrongfulException("index位置不合法！");
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        //先走index-1步，找到要插入位置的前一个位置
        ListNode cur = findIndexSubOne(index);
        ListNode node = new ListNode(data);
        //插入，修改指向
        node.next = cur.next;
        cur.next = node;
    }

    private ListNode findIndexSubOne(int index) {
        ListNode cur = this.head;
        while(index-1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
    //删除第一次出现数据key的节点
    public void remove(int key) {
        if(this.head == null) {
            return;
        }
        //判断头节点
        if(this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        //先找到key位置的上一个位置
        ListNode cur = findPrevOfKey(key);
        if(cur == null) {
            System.out.println("不存在你要删除的元素"+key);
            return;
        }
        //删除
        cur.next = cur.next.next;
    }

    private ListNode findPrevOfKey(int key) {
        ListNode cur = this.head;
        while(cur.next != null) {
            if(cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if(this.head == null) {
            return;
        }
        //从第二个节点开始判断
        ListNode cur = this.head.next;
        ListNode prev = this.head;//记录要判断节点的上一个节点
        while(cur != null) {
            if(cur.val == key) {
                //删除
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
            //最后判断头节点
            if(this.head.val == key) {
                this.head = this.head.next;
            }
        }
    }
    /*public ListNode removeElements(int val) {
        if(head == null) {
            return null;
        }
        //从第二个元素开始判断
        ListNode cur = this.head;
        while(cur.next != null) {
            if(cur.next.val == val) {
                cur.next = cur.next.next;
            }else {
                cur = cur.next;
            }
        }
        //最后判断头节点
        if(this.head.val == val) {
            this.head = this.head.next;
        }
        return this.head;
    }*/

    //清空单链表
    public void clear() {
        this.head = null;
    }
}

  • 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

IndexWrongfulException.java

public class IndexWrongfulException extends RuntimeException{
    public IndexWrongfulException() {
    }

    public IndexWrongfulException(String message) {
        super(message);
    }
}

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

TestList.java

public class TestList {
    public static void main(String[] args) {
        MySigleLinkedList linkedList = new MySigleLinkedList();

        System.out.println("头插测试");
        linkedList.addFirst(1);
        linkedList.addFirst(2);
        linkedList.display();

        System.out.println("尾插测试");
        linkedList.addLast(3);
        linkedList.addLast(2);
        linkedList.addLast(1);
        linkedList.addLast(4);
        linkedList.display();

        System.out.println("任意位置插入");
        try {
            linkedList.addIndex(2,666);
            linkedList.addIndex(8,666);
        } catch(IndexWrongfulException e) {
            e.printStackTrace();
        }
        linkedList.display();

        System.out.println("单链表中有"+linkedList.size()+"个数据");

        System.out.println("看单链表中是否包含某个数据");
        System.out.println(linkedList.contains(666));

        System.out.println("删除第一个指定数据");
        linkedList.remove(1);
        linkedList.remove(9);
        linkedList.display();

        System.out.println("删除全部的指定数据");
        linkedList.removeAllKey(2);
        linkedList.display();

        System.out.println("清空单链表后再添加一个数据");
        linkedList.clear();
        linkedList.addFirst(888);
        linkedList.display();
    }
}

  • 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

执行结果

img

注意事项

  1. 在代码中需要进行遍历链表时 , 要注意区分 cur != null 和 cur.next != null 的使用 , 虽然二者都可以去遍历链表 , 但cur != null , 最后一次循环判断使cur指向为null ; 而cur.next != null 的最后一次循环判断使cur指向的是链表的最后一个节点 .
  2. 单链表中插入和删除数据 , 需要先找到要处理位置的上一个位置 , 然后再进行指针指向的修改 .
  3. Java当中没有指针的概念 , 这里的节点通过类来实现 , 创建一个引用类型变量 , 这个引用就是Java当中的 “指针” 了 .
  4. 单链表中实现清空单链表只需要置空头节点即可 , 要与双链表中的清空区分

三. 无头双向非循环链表实现

给出结构图

img

img

MyLinkedList.java

public class MyLinkedList {
    //内部类定义节点
    static class ListNode {
        public int val;
        public ListNode next;//记录下一个节点
        public ListNode prev;//记录前一个节点

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;//指向头节点
    public ListNode tail;//指向尾巴节点

    //打印链表
    public void display() {
        ListNode cur = this.head;
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    //获取链表中元素的个数
    public int size() {
        ListNode cur = this.head;
        int count = 0;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //判断数据在链表中是否存在
    public boolean contains(int key) {
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if(this.head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }

    //尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if(this.head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        this.tail.next = node;
        node.prev = this.tail;
        this.tail = node;
    }

    //在任意位置插入, 认为头节点为0位置
    public void addIndex(int index, int data) {
        if(index < 0 || index > this.size()) {
            throw new IndexWrongfulException("index位置不合法");
        }
        if(index == 0) {
            this.addFirst(data);
            return;
        }
        if(index == size()) {
            this.addLast(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = findIndexListNode(index);
        node.next = cur;
        node.prev = cur.prev;
        cur.prev.next = node;
        cur.prev = node;
    }

    public ListNode findIndexListNode(int index) {
        ListNode cur = this.head;
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //删除第一个出现的指定元素
    public void remove(int key) {
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                //如果要删除的是头节点
                if(this.head == cur) {
                    this.head = this.head.next;
                    //如果链表中只有一个节点
                    if(this.head != null){
                        this.head.prev = null;
                    }
                }else{
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {//如果要删除的是尾巴节点
                        this.tail = cur.prev;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }

    //删除全部的指定元素
    public void removeAll(int key) {
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                //如果要删除的是头节点
                if(this.head == cur) {
                    this.head = this.head.next;
                    //如果链表中只有一个节点
                    if(this.head != null){
                        this.head.prev = null;
                    }
                }else{
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {//如果要删除的是尾巴节点
                        this.tail = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

    //清空
    public void clear() {
        ListNode cur =this.head;
        while(cur != null) {
            cur.prev = null;
            cur.next = null;
            cur = cur.next;
        }
        this.head = null;
        this.tail = null;
    }
}

  • 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

IndexWrongfulException.java

public class IndexWrongfulException extends RuntimeException{
    public IndexWrongfulException() {
    }

    public IndexWrongfulException(String message) {
        super(message);
    }
}

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

TestList.java

public class TestList {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        System.out.println("头插测试");
        list.addFirst(1);
        list.addFirst(2);
        list.addFirst(3);
        list.display();

        System.out.println("尾插测试");
        list.addLast(4);
        list.addLast(5);
        list.addLast(6);
        list.display();

        System.out.println("获取链表中元素的个数");
        System.out.println(list.size());

        System.out.println("判断数据在链表中是否存在");
        System.out.println(list.contains(4));
        System.out.println(list.contains(8));

        System.out.println("在任意位置插入");
        list.addIndex(0, 666);
        list.addIndex(3, 666);
        list.addIndex(list.size(), 666);
        list.display();

        System.out.println("删除第一个出现的指定元素");
        list.remove(4);
        list.display();

        System.out.println("删除全部的指定元素");
        list.removeAll(666);
        list.display();

        System.out.println("清空链表后再添加一个元素");
        list.clear();
        list.addFirst(888);
        list.display();
    }
}

  • 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

执行结果

img

注意事项

  1. 与单链表中的插入和删除实现进行区分 , 这里双链表中的插入和删除 , 因为此时链表是双向的 , 所以不需要像单链表一样找要处理位置的前一个位置 , 只需要找到要处理的位置去改变前驱和后记指针指向即可 .
  2. 在进行删除元素操作时 , 需要考虑的细节比较多 , 特别需要注意删除头节点与尾节点时的操作(考虑prev为null和next为null , 与删除中间节点不同) , 具体实现看上面给出的代码 .
  3. 注意双链表的清空链表实现 , 与单链表中的进行区分 , 双链表中需要手动去将每个节点的两个指针域置为null , 最后再将head和tail去置空 .
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/592502
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号