数据结构与算法之单链表

举报
未见花闻 发表于 2022/05/31 17:28:31 2022/05/31
【摘要】 本篇文章带大家认识数据结构与算法之单链表，链表是一种在逻辑结构连续，物理结构不连续的数据结构，可以分为单链表与双链表两类，正文将介绍单链表的增删查改，双链表在后续博文中详细介绍。描述代码：Java。

⭐️前面的话⭐️

本篇文章带大家认识数据结构与算法之单链表，链表是一种在逻辑结构连续，物理结构不连续的数据结构，可以分为单链表与双链表两类，正文将介绍单链表的增删查改，双链表在后续博文中详细介绍。描述代码：Java。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创！
📆华为云首发时间：🌴2022年5月31日🌴
✉️坚持和努力一定能换来诗与远方！
💭参考书籍：📚《Java核心技术卷1》，📚《数据结构》，📚《Java编程思想》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

😄1.链表的概念与分类

😆1.1链表概念

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表结构包括两部分：一是数据域，二是指针域，Java中没有指针这个概念，那不妨称为引用域吧！其中，数据域用来存放数据，它可以是基本数据类型，也可以是引用数据类型，不论是前者还是后者，在面向对象编程当中通通叫做对象；引用域用来存放地址，这个地址指向下一个链表结点或前一个链表结点，对于引用域的引用变量可以是一个也可以是两个，只有一个引用变量，则该链表为单链表，有两个引用变量，一个指向前驱结点，另一个指向后继结点，则该链表为双链表。
1
2

😆1.2链表分类

链表在实际当中有非常多类，主要依据以下三点进行分类：

  1. 带头与不带头
  2. 循环与不循环
  3. 链表引用（指针）域的指向是一个与两个

由第1点链表可分为：带头链表与不带头链表；
由第2点链表可分为：循环链表与非循环链表；
由第3点链表可分为：单链表与双链表。
由这三点可将链表分为8类：
1-3

不妨将这个数据域的变量命名为val，引用域的指向下一个结点的引用变量命名为next，指向前一个结点的引用变量命名为prev。

单链表（非循环） 单链表（非循环）
4
单链表的最后一个结点的next指向null。

双链表（非循环） 双链表（非循环）
5
双链表的最后一个结点的next与第一个结点的prev指向null。

对于循环的单链表，最后一个结点的next指向第一个结点（仔细想一想，单链表成环了，所以叫做循环单链表），双链表同理，第一个结点的prev指向最后一个结点，最后一个结点的next指向第一个结点（又成环咯！），最后一个问题，带头与不带头，其实就是在链表前增加一个结点，该结点的数据域是没有意义的，它的引用域指向第一个链表结点，如果是双链表，引用域prev指向null，next指向第一个链表结点，就相当于在链表中有一个结点，它的数据域无效，引用域正常的首个结点。

链表使用最多的是不带头非循环的单双链表，本篇博文将介绍单链表（不带头，非循环）增删查改的实现。

😆1.3链表与顺序表区别

顺序表的物理结构是连续的，逻辑结构也是连续的，它的优点是支持随机访问，获取和修改一个数据非常地方便，缺点是插入，删除元素不方便，空间利用率不高，可能存在大量空间浪费。
链表的物理结构不连续，逻辑结构连续，它完美解决了顺序表的缺点，它的优点是插入，删除元素方便，空间利用率高，随取随用，缺点是访问不方便，不支持随机访问。

所以说，顺序表的优点解决了链表的缺点，链表的优点解决了顺序表的缺点，两者各有各的优势。

😄2.单链表实现的理论基础

😆2.1单链表结构

😊2.1.1结点结构

class ListNode {
    public int val;//数据域
    ListNode next;//引用（指针）域
    ListNode() {}
    ListNode(int val) {
        this.val = val;//初始化链表结点值构造方法
    }
}

7

😊2.1.2单链表结构与类

public class SList {

    public ListNode head;//头引用，指向第一个链表结点地址（不是头结点）
    //增删查改方法
    ...
}

6

😆2.2单链表增删查改清单

public class SList {

    public ListNode head;
    //头插法
    public void addFirst(int data){
    }
    //尾插法
    public void addLast(int data){
    }
    //任意位置插入,第一个数据节点为0号下标
    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(){
	}
}

😄3.单链表从理论到实践

😆3.1单链表数据的插入

😊3.1.1头插法

在第一个结点前面插入数据，先链接后一个结点再将头引用指向node。
7
如果链表为空，直接让头引用指向node。

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

😊3.1.2尾插法

先遍历链表找到最后一个结点，再将新结点插入再最后一个结点后。
8

如果链表为空，让头引用指向新结点。

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

😊3.1.3任意位置插入

不妨记在第pos个结点后插入，如果插入位置pos为0，采用头插法，如果在最后一个结点后插入，即pos=链表长度，采用尾插法，如果其他位置插入，先将新结点指向指向第pos+1个结点，再将第pos个结点指向新结点。
9
如果链表为空，让头引用指向新结点。

    //任意位置插入,第一个数据节点为0号下标
    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;
        }
        ListNode node  = new ListNode(data);
        ListNode prev = this.head;
        while (index - 1 != 0) {
            prev = prev.next;
            index--;
        }
        node.next = prev.next;
        prev.next = node;
    }

😆3.2单链表的打印

遍历一遍链表即可，根据最后一个结点的next为null作遍历条件。

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

😆3.3单链表数据的查找

遍历一遍单链表，判断数据域的值是否等于目标值。

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

😆3.4获取单链表的数据个数

遍历大法。

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

😆3.5单链表数据的删除

😊3.5.1删除链表中第一次出现的目标值

删除链表结点时，需要目标结点cur和目标结点前一个结点prev，让prev.next = cur,next即可。如果链表只有一个结点，直接让头引用指向null。
10
要删除链表中第一次出现的目标值，需要先找到目标结点，怎么找呢？就是遍历，但是在遍历过程中需要记住目标结点前一个结点，因为链表是单向的，如果不记住前一个结点，无法删除目标结点。因为只删除链表第一次出现目标值的结点，因此找到目标值删除后，程序就可以返回了。

删除链表某一个数据分为两种情况：

  1. 目标值在首结点，直接让头引用指向原结点的后一个结点或null。
  2. 目标值不在首结点，遍历链表。
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if (this.head == null) {
            return;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode cur = this.head.next;
        ListNode prev = this.head;
        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                return;
            }
            prev = cur;
            cur = cur.next;
        }
        System.out.println("未找到目标结点！");
    }

😊3.5.2删除所有链表中所有的目标值

这个和删除第一次出现目标值的思路基本一样，差别在于在删除一个目标值结点后，继续遍历查找删除。

    //删除所有值为key的节点
    public void removeAllKey(int key){
        if (this.head == null) {
            return;
        }
        while (this.head.val == key) {
            this.head = this.head.next;
            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;
            }
        }
    }

😆3.6单链表的销毁

链表的销毁需对每个结点进行删除，不妨先保存需要删除结点的后一结点，再删除结点，以此类推直到删除所有链表结点。

    public void clear(){
        if (this.head == null) {
            return;
        }
        while (head != null) {
            ListNode next = head.next;
            head.next = null;
            head = next;
        }
    }
}

😄4.单链表增删查改源代码

😆4.1单链表类

class ListNode {
    public int val;//数据域
    ListNode next;//引用（指针）域
    ListNode() {}
    ListNode(int val) {
        this.val = val;//初始化链表结点值构造方法
    }
}


public class SList {

    public ListNode head;
    //头插法
    public void addFirst(int data){
        ListNode node  = new ListNode(data);
        if (this.head == null) {
            this.head = node;
        }
        node.next = this.head;
        this.head = node;
    }
    //尾插法
    public void addLast(int data){
        ListNode node  = new ListNode(data);
        if (this.head == null) {
            this.head = node;
        }
        ListNode cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
    //任意位置插入,第一个数据节点为0号下标
    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;
        }
        ListNode node  = new ListNode(data);
        ListNode prev = this.head;
        while (index - 1 != 0) {
            prev = prev.next;
            index--;
        }
        node.next = prev.next;
        prev.next = node;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        if (this.head == null) {
            return false;
        }
        ListNode 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 == null) {
            return;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode cur = this.head.next;
        ListNode prev = this.head;
        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                return;
            }
            prev = cur;
            cur = cur.next;
        }
        System.out.println("未找到目标结点！");
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if (this.head == null) {
            return;
        }
        while (this.head.val == key) {
            this.head = this.head.next;
            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;
            }
        }
    }
    //得到单链表的长度
    public int size(){
        int len = 0;
        ListNode cur = this.head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        return len;
    }
    public void display(){
        ListNode cur  = this.head;
        while (cur != null) {
            System.out.print(cur.val + "  ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void clear(){
        if (this.head == null) {
            return;
        }
        while (head != null) {
            ListNode next = head.next;
            head.next = null;
            head = next;
        }
    }
}

😆4.2测试代码

public class Test {
    public static void main(String[] args) {
        ListNode s1 = new ListNode(1);
        ListNode s2 = new ListNode(2);
        ListNode s3 = new ListNode(3);
        ListNode s4 = new ListNode(4);
        ListNode s5 = new ListNode(5);
        s1.next = s2;
        s2.next = s3;
        s3.next = s4;
        s4.next = s5;
        SList list = new SList();
        list.head = s1;
        list.display();
        list.addFirst(12);
        list.addFirst(12);
        list.addFirst(14);
        list.display();
        list.addLast(15);
        list.addLast(15);
        list.addLast(17);
        list.display();
        list.addIndex(0, 22);
        list.addIndex(12,23);
        list.addIndex(2,24);
        list.display();
        list.remove(23);
        list.remove(22);
        list.remove(24);
        list.display();
        list.removeAllKey(12);
        list.removeAllKey(17);
        list.removeAllKey(15);
        list.removeAllKey(14);
        list.display();
        System.out.println(list.contains(1));
        System.out.println(list.contains(2));
        System.out.println(list.contains(5));
        System.out.println(list.contains(13));
        System.out.println("------------");
        list.clear();
        list.display();
    }
}

11

😆4.3项目文件

途径1：
博主的码云gitee，平常博主写的程序代码都在里面。
途径2：
博主的github，平常博主写的程序代码都在里面。
途径3：
联系我！

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
Java 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入