相信如果看完了上期顺序表的小伙伴应该发现了顺序表的诸多缺点:
🤒 中间/头部的插入删除,时间复杂度为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语言指针,结构体,动态内存这几张的内容!当你能把这个单链表理解透彻了,下一期的带头双向循环链表也很容易理解的,代码实现起来更轻松,加油吧!