单链表的实现与常见接口的详细图解剖析

简介: 相信如果看完了上期顺序表的小伙伴应该发现了顺序表的诸多缺点:

相信如果看完了上期顺序表的小伙伴应该发现了顺序表的诸多缺点

🤒 中间/头部的插入删除,时间复杂度为O(N)!

😑 增容需要申请新的空间,拷贝数据,释放旧空间,会有不少的消耗。

🙄 增容一般是呈倍增长,势必会有一定的空间浪费。

链表的OJ题会单独出一期的哦!

那么,如何解决以上的问题呢?

🤨 那么什么是链表呢?—— 链表是一种物理存储结构上非连续非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

实际中要实现的链表的结构非常多样,以下情况组合起来就有8种链表结构:

1. 单向、双向         2. 带头、不带头            3. 循环、非循环

我们只讲最简单和最复杂的,毕竟一句老话,冬天到了春天还会远吗?🎄

今天我们讲头单向非循环链表下期讲带头双向循环链表 !

好的,有了上面的认识正式进入我们本期的学💪。

无头单向非循环链表:结构简单一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构,如哈希桶图的邻接表等等。另外这种结构在笔试面试中出现很多

我们来看到单链表的架构:

🎨 单链表和顺序表不一样,我们是需要的时候动态申请一个节点空间就够了!

SLTNode* BuySListNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
    return NULL;//做空指针判断
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}

这里我们利用malloc函数开辟了一个SLTNode大小的空间(得用SLTNode* 来接收),malloc和realloc一样如果开辟失败会返回空指针,所以这我们需要先做判断!不为空则把数据放入data,并且把指向下一个节点的 next 置空!并且返回新节点的地址!(这里如果不明白则需要补充结构体,指针,动态内存开辟的知识)

🎋 首先我们还是来实现单链表的头部插入数据!

这里我们可以看到,不带哨兵位(带头链表)链表需要改变头指针位置,下期我们学带头双向循环链表就可以不用双指针了!

🧵 下面是我们的单链表尾部插入数据!

🧶 接着来实现单链表头部删除数据!

🛒 下面来到单链表的尾部删除数据!

👓 在指定元素前插入节点!

这个我们首先需要找到指定节点元素的地址!

接下来就是实现我们的指定元素前插入节点的函数了!

🦺 同理我们接着来实现删除指定元素的节点!

最后其实还有一个修改节点数据,这个看了上期的顺序表实现起来就很简单,留给你们自己研究去啦!学好编程多想,多敲代码准没错!

 

    那么以上这就是我们无头单向非循环链表的常见接口了,如果你看完感觉比较吃力看不懂的话,建议多去回顾下c语言指针,结构体,动态内存这几张的内容!当你能把这个单链表理解透彻了,下一期的带头双向循环链表也很容易理解的,代码实现起来更轻松,加油吧!

相关文章
【数据结构】图文并茂,通过逻辑图带你轻松拿捏链表,实现各种接口功能(2)
【数据结构】图文并茂,通过逻辑图带你轻松拿捏链表,实现各种接口功能(2)
70 0
|
存储
【数据结构】图文并茂,通过逻辑图带你轻松拿捏链表,实现各种接口功能
【数据结构】图文并茂,通过逻辑图带你轻松拿捏链表,实现各种接口功能
142 0
|
存储
【双链表增删查改接口的实现】
【双链表增删查改接口的实现】
52 0
双链表(常见的10个函数接口,配图详解每一个函数接口)(下)
双链表(常见的10个函数接口,配图详解每一个函数接口)(下)
118 0
双链表(常见的10个函数接口,配图详解每一个函数接口)(下)
|
存储
双链表(常见的10个函数接口,配图详解每一个函数接口)(上)
双链表(常见的10个函数接口,配图详解每一个函数接口)(上)
129 0
双链表(常见的10个函数接口,配图详解每一个函数接口)(上)
|
存储 Java 索引
set接口方法(数组+链表+红黑树)以及子类LinkedHashSet的使用
set接口方法(数组+链表+红黑树)以及子类LinkedHashSet的使用
Go 语言接口及使用接口实现链表插入(下)
4. 接口嵌套 5. 类型断言 5.1 断言判断 5.2 多类型判断 6. 使用接口实现链表插入
Go 语言接口及使用接口实现链表插入(上)
1. 接口定义 1.1 空接口 1.2 实现单一接口 1.3 接口多方法实现 2. 多态 2.1 为不同数据类型的实体提供统一的接口 2.2 多接口的实现 3. 系统接口调用
|
6月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
6月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表