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

迈不过友情╰ 2023-09-26 10:02 49阅读 0赞

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

#### 文章目录 ####

*  一. 链表的概念和分类
 *  二. 无头单向非循环链表实现
 *   *  MySigleLinkedList.java
     *  IndexWrongfulException.java
     *  TestList.java
     *  执行结果
     *  注意事项
 *  三. 无头双向非循环链表实现
 *   *  MyLinkedList.java
     *  IndexWrongfulException.java
     *  TestList.java
     *  执行结果
     *  注意事项

## 一. 链表的概念和分类 ##

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

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

*  单向或者双向

![img][img 1]

*  带头或者不带头

![img][img 2]

*  循环或者非循环

![img][img 3]

这里列出这8种链表结构

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

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

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

*  **无头单向非循环链表**：

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

*  **无头双向不循环链表** :

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

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

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

![img][img 4]

![img][img 5]

### 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;
        }
    }

### IndexWrongfulException.java ###

public class IndexWrongfulException extends RuntimeException{
        
        public IndexWrongfulException() {
        
        }
    
        public IndexWrongfulException(String message) {
        
            super(message);
        }
    }

### 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();
        }
    }

### 执行结果 ###

![img][img 6]

### 注意事项 ###

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

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

给出结构图

![img][img 7]

![img][img 8]

### 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;
        }
    }

### IndexWrongfulException.java ###

### 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();
        }
    }

### 执行结果 ###

![img][img 9]

### 注意事项 ###

1.  与单链表中的**插入和删除**实现进行区分 , 这里双链表中的插入和删除 , 因为此时链表是双向的 , 所以不需要像单链表一样找要处理位置的前一个位置 , **只需要找到要处理的位置**去改变前驱和后记指针指向即可 .
2.  **在进行删除元素操作时 , 需要考虑的细节比较多 , 特别需要注意删除头节点与尾节点时的操作(考虑prev为null和next为null , 与删除中间节点不同)** , 具体实现看上面给出的代码 .
3.  注意双链表的**清空链表**实现 , 与单链表中的进行区分 , **双链表中需要手动去将每个节点的两个指针域置为null** , **最后再将head和tail去置空** .

[078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]: https://img-blog.csdnimg.cn/078b66f87e3c4e309d7f34d79c5776c4.gif#pic_center
[_XIN-XIANG]: https://blog.csdn.net/Trong_?spm=1000.2115.3001.5343
[Java]: https://blog.csdn.net/trong_/category_11997769.html
[img]: https://img-blog.csdnimg.cn/img_convert/16d1b33e505d9639ab90575afce43dc7.png
[img 1]: https://img-blog.csdnimg.cn/img_convert/d69da3fb464039fb7fcfa982f371b7d8.png
[img 2]: https://img-blog.csdnimg.cn/img_convert/6bb0252d7b45c89f4d4f9b472ba2f0b3.png
[img 3]: https://img-blog.csdnimg.cn/img_convert/2707be613a452b9bc9022d1790e11226.png
[img 4]: https://img-blog.csdnimg.cn/img_convert/36a2a8c9ffd3cf791e0118b4f2bcc012.png
[img 5]: https://img-blog.csdnimg.cn/img_convert/b83461e6c2e8da546472f6b1b36f2c3d.png
[img 6]: https://img-blog.csdnimg.cn/img_convert/5d8e15fefbc64881b3322f3f660d1fd7.png
[img 7]: https://img-blog.csdnimg.cn/img_convert/8ee31ce9ec82557651235a16cd57fe9f.png
[img 8]: https://img-blog.csdnimg.cn/img_convert/f637a30ee8a03387e40f80d3855356f0.png
[img 9]: https://img-blog.csdnimg.cn/img_convert/d1fb18b36baf6835f76070c949b6109f.png