数据结构 - 单链表

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

文章目录

目录

文章目录

一、什么是链表?

线性表:

顺序表:

二、链表的分类和实现

分类:

实现:

1.创建节点类

2.创建单链表 

1.addTail(尾增)

 

2.删除节点值为key的第一个节点

 3.插入节点(在指定位置)

4.获取链表长度 

总结


前言

大家好,这篇博客给大家讲一下什么是链表以及单链表的实现过程


一、什么是链表?

再讲解什么是链表时,先给大家讲一下大体上的分类线性表和顺序表

线性表:

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构,常见的线性表:链表、栈、队列... 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物 理上存储时,通常以数组和链式结构的形式存储。

数据结构 - 单链表,数据结构与算法,链表,数据结构

数据结构 - 单链表,数据结构与算法,链表,数据结构 

可以看到链表在内存中并不是连续的,只是在逻辑上是连续的,链表中的节点见缝插针般的在内存中存储 

顺序表:

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成 数据的增删查改。


二、链表的分类和实现

分类:

链表根据是否包含头结点来分可以分为两类,根据是否循环来分也可以分为两类

其中循环和非循环相对来说差别不大,下面我们将围绕是否包含头节点来进行谈论

问题1:含头节点的链表和不含头节点的链表有什么不同?

数据结构 - 单链表,数据结构与算法,链表,数据结构

带头结点的链表的第一个节点不存数据,实现起来相对比较容易

不带头结点的第一个节点就是数据节点,实现起来比带头结点的难一些,并且是刷题和面试的重点

下面我将带大家来实现最经典的单链表:不带头节点的非循环链表

实现:

思路分析:

1.创建节点类Node,用来表示链表中的节点

2.创建单链表 SingleList

3.实现方法 增,删,查.......

1.创建节点类

来思考一下节点类中应该存在的信息?

日常工作生活中节点中记录的信息是多种多样的,为了简单起见我们按最简单的来,即节点中只包含

val和指向下一个节点的指针next

class Node{
    public int val;
    public Node next;

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

2.创建单链表 

有了节点类,我们就可以把一个个节点组合起来,组合成为一个在逻辑上是连续的链表了

那么在单链表中应该存在什么呢?

首先应该有个头结点,要不然无法知道链表从哪里开始,也不能将链表作为参数传递出去

其次应该有构造方法,不然写这么个链表就会毫无意义

还有就是一些方法,基础代码给出,下面我们来一个一个实现方法

public class SingleListDemo {
    private Node head;

    public SingleListDemo(){
    }

}


class Node{
    public int val;
    public Node next;

    public Node(int val){
        this.val = val;
    }
}
1.addTail(尾增)
 
public void addTail(int val) {
    Node newNode = new Node(val);

    if (head == null) {
        head = newNode;
        return;
    }

    Node cur = head;
    while (cur.next != null) {
        cur = cur.next;
    }

    cur.next = newNode;
}

数据结构 - 单链表,数据结构与算法,链表,数据结构

在这里我们可以延伸出在头部插入节点的情况,即将新的节点的next指针指向头结点,将头结点的指向更改为新的节点即可 

2.删除节点值为key的第一个节点
// 删除节点的Data值为key的第一个节点
public void DeleteKey(int key) {
    // 判断链表是否为空
    if (head == null) {
        System.out.println("链表为空");
        return;
    }
    // 判断第一个节点是否是要删除的节点
    if (head.val == key) {
        HeadDelete();
        return;
    }
    Node cur = head;
    while (cur.next != null) {
        if (cur.next.val == key) {
            cur.next = cur.next.next;
            return;
        }
        cur = cur.next;
    }
}

 拓展: 删除值为key的所有节点,要求时间复杂度不超过O(n)

// 法一 循环遍历
public void Delete(int Data) {
    if (head == null) {
        return;
    }
    while (head.val == Data) {
        head = head.next;
        if (head == null) {
            return;
        }
    }
    Node cur = head;// 定义临时节点代替头结点遍历链表并删除元素
    while (true) {
        if (cur.next == null) {
            return;
        }

        if (cur.next.val == Data) {
            System.out.println("删除成功!");
            cur.next = cur.next.next;
            continue;
        }
        cur = cur.next;
    }

}

// 法二 - 双指针
public void Delete2(int Data) {
    if (head == null) {
        return;
    }
    Node pre = head;
    Node cur = head.next;

    while (cur != null) {
        if (cur.val == Data) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    if (head.val == Data) {
        head = head.next;
    }
}
 3.插入节点(在指定位置)
// 在指定位置插入节点,第一个节点为0号下标
public void InsertAny(int index, int val) {
    // 判断链表下标是否合法
    if (index < 0 && index > getSize()) {
        System.out.println("下标不合法!");
        return;
    }
    if (index == 0) {
        HeadAdd(val);
        return;
    }
    Node node = new Node(val);
    Node cur = head;
    // 遍历链表找到下标为index-1的元素
    while (index > 1) {//index-1
        index--;
        cur = cur.next;
    }
    node.next = cur.next;
    cur.next = node;
}
4.获取链表长度 
public int getSize() {
    Node node = head;
    int size = 0;
    while (node != null) {
        node = node.next;
        size++;
    }
    return size;
} 

以上就是一些比较重要的方法了,下期见。 


总结

大家多多刷题吧,链表可是面试中笔试题的重点!文章来源地址https://www.toymoban.com/news/detail-703406.html

到了这里,关于数据结构 - 单链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构入门 — 链表详解_单链表

    数据结构入门 — 单链表详解 * 博客主页链接:https://blog.csdn.net/m0_74014525 关注博主,后期持续更新系列文章 文章末尾有源码 *****感谢观看,希望对你有所帮助***** 第一篇:数据结构入门 — 链表详解_单链表 第二篇:数据结构入门 — 链表详解_双向链表 第三篇:数据结构入门

    2024年02月11日
    浏览(51)
  • 【数据结构】-- 单链表 vs 双向链表

    🌈 个人主页: 白子寰 🔥 分类专栏: python从入门到精通,魔法指针,进阶C++,C语言,C语言题集,C语言实现游戏 👈 希望得到您的订阅和支持~ 💡 坚持创作博文(平均质量分82+),分享更多关于深度学习、C/C++,python领域的优质内容!(希望得到您的关注~)  目录  单链表和

    2024年04月17日
    浏览(43)
  • <数据结构> 链表 - 单链表(c语言实现)

    哨兵位结点也叫哑节点。哨兵位结点 也是头结点 。该节点 不存储有效数据,只是为了方便操作 (如尾插时用带哨兵位的头结点很爽,不需要判空)。 有哨兵位结点的链表,第一个元素应该是链表第二个节点(head - next,head为哨兵位结点)对应的元素。 有哨兵位结点的链表

    2023年04月11日
    浏览(113)
  • 【数据结构】反转链表、链表的中间节点、链表的回文结构(单链表OJ题)

    正如标题所说,本文会图文详细解析三道单链表OJ题,分别为:  反转链表 (简单)  链表的中间节点 (简单)  链表的回文结构 (较难) 把他们放在一起讲的原因是:  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说?请往下看: 目录 1. 反转链

    2024年02月13日
    浏览(68)
  • 【数据结构】认识链表和模拟实现单链表

    即使骑的小电驴,也要奋力前进 目录 1.链表 1.1 链表的概念  1.2 链表的逻辑结构图和物理结构图 1.2.1 链表的逻辑结构图  1.2.2 链表的物理结构图  1.3链表结构的分类 1.3.1 链表通过什么进行结构的分类  1.3.2 不同链表结构的逻辑图 2.模拟实现一个单向链表  2.1 MyLinkedList类的

    2024年02月14日
    浏览(55)
  • 【数据结构】 链表简介与单链表的实现

    在【数据结构】 ArrayList简介与实战中我们已经熟悉了ArrayList的使用,并且进行了简单模拟实现。通过源码知道,ArrayList底层使用数组来存储元素 由于其底层是一段连续空间, 当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为

    2024年02月12日
    浏览(167)
  • 【数据结构】链表(单链表与双链表实现+原理+源码)

    博主介绍:✌全网粉丝喜爱+、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战✌有需要可以联系作者我哦! 🍅附上相关C语言版源码讲解🍅 👇🏻 精彩专栏推荐订阅👇🏻 不然下次找

    2024年01月24日
    浏览(122)
  • 【数据结构】--单链表力扣面试题②反转链表

    目录 题目链接:反转链表   法一:直接反转法 法二:头插法 题目分析: 创建一个新链表,然后值是逆置的行吗?不行。因为题目要求的是在 原链表上逆置,改变原链表的指向,并不是值的拷贝后的逆转 。 那其实总共有三种方法 。 法一,直接原地翻转。法二,头插法。

    2024年02月06日
    浏览(37)
  • [C语言][数据结构][链表] 单链表的从零实现!

    目录 零.必备知识 1.一级指针 二级指针 2. 节点的成员列表     a.数据     b.指向下一个节点的指针. 3. 动态内存空间的开辟 (malloc-calloc-realloc) 一.单链表的实现与销毁          1.1 节点的定义         1.2 单链表的尾插         1.3 单链表的头插         1.4 单链表的尾删  

    2024年04月11日
    浏览(72)
  • 链表的总体涵盖以及无哨兵位单链表实现——【数据结构】

     😊W…Y:个人主页 在学习之前看一下美丽的夕阳,也是很不错的。 如果觉得博主的美景不错,博客也不错的话,关注一下博主吧💕 在上一期中,我们说完了顺序表,并且提出顺序表中的问题 1. 中间/头部的插入删除,时间复杂度为O(N) 2. 增容需要申请新空间,拷贝数据,释

    2024年02月14日
    浏览(64)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包