1. Toy模板网首页
  2. > Toy博客

【一起学数据结构与算法】快速教你了解并实现单链表

9月前 作者：摸鱼王胖嘟嘟 分类：Toy博客 阅读(43) 违法举报

这篇具有很好参考价值的文章主要介绍了【一起学数据结构与算法】快速教你了解并实现单链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

此篇是对单链表知识的学习和实现，基本上大体的方法实现和思路都已经表达，如果有不对的地方，还请各位大佬多多指教！

一、单链表的概念

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

二、单链表内一些方法的实现

2.1 单链表长什么样子？

单链表不教链接吗,一起学数据结构与算法系列
像上面这样式的就是一种单链表！

由上图可以看出我们一些属性来表示单链表！

class ListNode {
    public int val;
    public ListNode next;

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

2.2 创建单链表

创建链表之前我们需要定义一个成员变量head表示链表的头结点！

 //成员变量
    public ListNode head;//链表的头引用

由于咱们是初步学习单链表，所有咱们就简单的创建的单链表

public void createList() {

        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        this.head = listNode1;

    }

2.3 打印单链表

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

为什么会定义一个cur来指向head了？
那是因为如果拿head来遍历链表，那么最后head就指向了null，就找不到链表的头了，所以使用cur来完成操作！

2.4 查找是否包含关键字key是否在单链表中

我们只需要拿cur去遍历链表，看cur是否等于key，如果有就返回true，没有就返回false。
实现cur遍历的过程的代码就是：cur = cur.next;

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

2.5 得到单链表的长度

一样的操作，此处通过定义一个count作为计数器，直到cur遍历完整个链表就停止.

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

2.6 addFirst – 头插

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

单链表不教链接吗,一起学数据结构与算法系列

2.7 addLast – 尾插

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

单链表不教链接吗,一起学数据结构与算法系列

2.8 addIndex – 任意位置插入

/**
     * 找到index - 1 位置结点的地址
     * @param index
     * @return
     */
    public ListNode findIndex(int index) {
        ListNode cur = this.head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //任意位置插入，第一个数据结点为0号下标
    public void addIndex(int index, int data) {
        if (index < 0 || index > size()) {
            System.out.println("index位置不合法!");
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = findIndex(index);
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
    }

单链表不教链接吗,一起学数据结构与算法系列

2.9 remove – 删除第一次出现的key

 /**
     * 找到要删除关键字的前驱
     * @param key
     * @return
     */
    public ListNode searchPrev(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 remove(int key) {
        if (this.head == null) {
            System.out.println("单链表为空，不能删除！");
            return;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode cur = searchPrev(key);
        if (cur == null) {
            System.out.println("没有你要删除的结点！");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }

单链表不教链接吗,一起学数据结构与算法系列

2.10 removeAllkey – 删除所有值为key的结点

//删除所有值为key的结点
    public ListNode removeAllKey(int key) {
        if (this.head == null) return null;

        ListNode prev = this.head;
        ListNode cur = this.head.next;

        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;
        }
        return this.head;
    }

1.如果先处理头，则需要写成循环，因为当链表所有结点都是待删除的情况时，一个if条件语句处 理不了

2.while循环里面的条件不能写成cur.next == null，因为removeSubOne函数如果没找到待删除 的结点，它返回的是一个null，如果写成cur.next != null，则可能会报空指针异常文章来源地址https://www.toymoban.com/news/detail-827737.html

2.11 清空单链表

public void clear() {
        this.head = null;
    }

三、MyLinkedList.java

import java.util.LinkedList;

@SuppressWarnings({"all"})

class ListNode {
    public int val;
    public ListNode next;

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

    //成员变量
    public ListNode head;//链表的头引用

    public void createList() {

        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        this.head = listNode1;

    }

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

    //查找是否包含关键字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 int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

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

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

    /**
     * 找到index - 1 位置结点的地址
     * @param index
     * @return
     */
    public ListNode findIndex(int index) {
        ListNode cur = this.head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //任意位置插入，第一个数据结点为0号下标
    public void addIndex(int index, int data) {
        if (index < 0 || index > size()) {
            System.out.println("index位置不合法!");
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = findIndex(index);
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
    }

    /**
     * 找到要删除关键字的前驱
     * @param key
     * @return
     */
    public ListNode searchPrev(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 remove(int key) {
        if (this.head == null) {
            System.out.println("单链表为空，不能删除！");
            return;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode cur = searchPrev(key);
        if (cur == null) {
            System.out.println("没有你要删除的结点！");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }

    //删除所有值为key的结点
    public ListNode removeAllKey(int key) {
        if (this.head == null) return null;

        ListNode prev = this.head;
        ListNode cur = this.head.next;

        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;
        }
        return this.head;
    }

    public void clear() {
        this.head = null;
    }
}

四、Test.java

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
       /* myLinkedList.createList();
        myLinkedList.display();
        boolean flag = myLinkedList.contains(34);
        System.out.println(flag);
        int size = myLinkedList.size();
        System.out.println(size);*/
        myLinkedList.addFirst(12);
        myLinkedList.addFirst(23);
        myLinkedList.addLast(39);
        myLinkedList.addLast(37);
        myLinkedList.addIndex(0,99);
        myLinkedList.addIndex(5,99);
        myLinkedList.addIndex(3,99);
        myLinkedList.display();
        myLinkedList.remove(12);
        myLinkedList.removeAllKey(99);
        myLinkedList.display();
        myLinkedList.clear();
        myLinkedList.display();

    }
}

到了这里，关于【一起学数据结构与算法】快速教你了解并实现单链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 手把手教你 ，带你彻底掌握八大排序算法【数据结构】

    手把手教你 ，带你彻底掌握八大排序算法【数据结构】

    直接插入排序是一种简单的插入排序法，其基本思想:是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 可以理解为一遍摸扑克牌，一边进行排序 在待排序的元素中，假设前面n-1(其中n=2)个数

    2024年02月02日
    浏览(67)
  • 数据结构--》深入了解栈和队列，让算法更加高效

    数据结构--》深入了解栈和队列，让算法更加高效

            本文将带你深入了解数据结构栈和队列，这两种基础的线性数据结构在算法中的重要性不言而喻。我们将会详细介绍栈和队列的概念、分类、实现以及应用场景，在理解栈和队列的基础上，还将探讨如何通过栈和队列来高效地解决算法问题。         无论你是

    2024年02月10日
    浏览(40)
  • 数据结构与算法：快速排序

    数据结构与算法：快速排序

    荷兰国旗问题 想要理解快速排序，就先理解这个问题： [LeetCode75.颜色分类] 荷兰国旗是由红白蓝三色组成的： 现在将其颜色打乱 然后根据一定的算法，将其复原为红白蓝三色，这就叫做荷兰国旗问题。 在LeetCode的题目中，其将荷兰国旗的三个颜色用0，1，2来表达，也就是说

    2024年01月15日
    浏览(43)
  • 数据结构——排序算法之快速排序

    数据结构——排序算法之快速排序

        个人主页： 日刷百题 系列专栏 ： 〖C/C++小游戏〗 〖Linux〗 〖数据结构〗   〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ ​ 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。 基本思想： 任取待排序元素序列中 的某元素作为基准值，按照

    2024年01月21日
    浏览(60)

  • 数据结构与算法之快速排序

    快速排序 （Quick Sort），又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数

    2024年02月10日
    浏览(43)
  • 【数据结构与算法】三个经典案例带你了解动态规划

    【数据结构与算法】三个经典案例带你了解动态规划

    从表中我们可以看到，最大的公共子串长度为2，一共有两个长度为2的公共子串，分别是第一个字符串的第2个字符到第3个字符和第一个字符串的第3个字符到第4个字符，即 ba 和 ac 根据上面的方法，我们来用代码封装一下求取最大公共子串的函数 function publicStr(s1, s2) { // 创建

    2024年04月09日
    浏览(95)
  • 【数据结构与算法】十大经典排序算法-快速排序

    【数据结构与算法】十大经典排序算法-快速排序

    🌟 个人博客： www.hellocode.top 🏰 Java知识导航： Java-Navigate 🔥 CSDN： HelloCode. 🌞 知乎 ：HelloCode 🌴 掘金 ：HelloCode ⚡如有问题，欢迎指正，一起学习~~ 快速排序（Quick Sort）是一种高效的排序算法，是对冒泡排序的优化。它采用分治法（Divide and Conquer）的思想，将待排序序列

    2024年02月13日
    浏览(65)
  • 【数据结构与算法】：选择排序与快速排序

    【数据结构与算法】：选择排序与快速排序

    🔥 个人主页 ： Quitecoder 🔥 专栏 ：数据结构与算法 我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：腾讯云 欢迎来到排序的第二个部分：选择排序与快速排序！ 选择排序是一种简单直观的比较排序算法。该算法的基本思想是在每一轮中选出当前未排序部分的最

    2024年03月17日
    浏览(53)

  • 【数据结构与算法】【约瑟夫问题】还在用递归？教你用链表秒杀约瑟夫

     🎉🎉欢迎光临🎉🎉 🏅我是苏泽，一位对技术充满热情的探索者和分享者。🚀🚀 🌟特别推荐给大家我的最新专栏 《数据结构与算法：初学者入门指南》📘📘 本专栏纯属为爱发电永久免费！！！ 这是苏泽的个人主页可以看到我其他的内容哦👇👇 努力的苏泽 http://su

    2024年02月19日
    浏览(39)
  • 数据结构和算法——快速排序（算法概述、选主元、子集划分、小规模数据的处理、算法实现）

    数据结构和算法——快速排序（算法概述、选主元、子集划分、小规模数据的处理、算法实现）

    目录 算法概述 图示 伪代码 选主元 子集划分 小规模数据的处理 算法实现 快速排序和归并排序有一些相似，都是用到了分而治之的思想：   通过初步的认识，我们能够知道快速排序算法最好的情况应该是： 每次都正好中分 ，即每次选主元都为元素的中位数的位置。 最好情

    2024年02月15日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包