深圳幻海软件技术有限公司 欢迎您！
更多

【数据结构初阶】线性表——单链表（手撕单链表）

2023-05-06

next cur pos
大家好我是沐曦希💕链表1.链表的概念及结构2.链表的分类3.单链表的实现SList.hSList.ctest.c4.单链表改进4.1替换法删除pos4.2替换法pos之前插入节点5.写在最后1.链表的概念及结构概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的

大家好我是沐曦希💕

链表

  • 1.链表的概念及结构
  • 2.链表的分类
  • 3.单链表的实现
    • SList.h
    • SList.c
    • test.c
  • 4.单链表改进
    • 4.1 替换法删除pos
    • 4.2 替换法pos之前插入节点
  • 5.写在最后

1.链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
链表逻辑的结构（形象化）：
物理结构（在内存中时间存储结构）:

2.链表的分类

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

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

    虽然有这么多的链表的结构，但是实际中最常用还是两种结构：
  1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

3.单链表的实现

SList.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//打印单链表
void SListPrint(SLTNode* phead);
//销毁单链表
void SListDestory(SLTNode** pphead);
//动态申请一个节点
SLTNode* BuyListNode(SLTDataType x);
//单链表的尾插数据
void SListPushBack(SLTNode** pphead, SLTDataType x);
//单链表的头插数据
void SListPushFront(SLTNode** pphead, SLTDataType x);
//单链表的尾删数据
void SListPopBack(SLTNode** pphead);
//单链表的头删数据
void SListPopFront(SLTNode** pphead);
//单链表的查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
// 单链表在pos位置之前插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 单链表删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos);
// 单链表在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SLTNode* pos);

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

要更改头结构体指针plist时，应该进行传址调用，所以用二级指针来接受。
改谁用谁的指针。
在很多库里面都会分别有在pos前后插入x的函数和分别有删除pos位置和删除pos位置之后的值的。

// 单链表在pos位置之前插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 单链表删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos);
// 单链表在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SLTNode* pos);

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

区别在于：
1.在pos前插入x和删除pos位置的函数声明要传单链表的头结构体指针。
在pos前插入x时，当pos为第一个节点时，要改变头结构体指针的指向新的节点，就要传头结构体指针的地址。头结构体指针指向新的节点，新的节点的next指针指向第一个节点或者NULL。

删除pos位置的值时，当pos为第一个节点时，要改变头结构体指针的指向新的节点，就要传头结构体指针的地址。头结构体指针应该指向第二个节点或者NULL。

2.在pos前插入x和删除pos位置的实现要进行分情况讨论，
即第一种情况为pos为第一个节点和第二种情况pos不为第一个节点，代码更为复杂。

SList.c

要更改头结构体指针plist时，应该进行传址调用，所以用二级指针来接受。
改谁用谁的指针，并且传的是头节点指针的地址。

#include"SList.h"
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
void SListDestory(SLTNode** pphead)
{
assert(pphead);
if (*pphead == NULL)
{
return;
}
SLTNode* cur = *pphead;
SLTNode* prev = *pphead;
while (cur->next)
{
prev = cur;
cur = cur->next;
free(prev);
}
free(cur);
cur = NULL;
prev = NULL;
}
SLTNode* BuyListNode(SLTDataType x)
{
SLTNode* ret = (SLTNode*)malloc(sizeof(SLTNode));
if (ret)
{
ret->data = x;
ret->next = NULL;
return ret;
}
return NULL;
}
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* tail = *pphead;
SLTNode* newnode = BuyListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
return;
}
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SListPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* cur = *pphead;
if (cur->next == NULL)
{
free(cur);
cur = NULL;
*pphead = NULL;
}
else
{
SLTNode* prev = *pphead;
while (cur->next)
{
prev = cur;
cur = cur->next;
}
free(cur);
cur = NULL;
prev->next = NULL;
}
}
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* cur = *pphead;
*pphead = cur->next;
free(cur);
cur = NULL;
}
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
assert(phead);
SLTNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
SLTNode* prev = *pphead;
if (pos == *pphead)
{
SListPushFront(pphead, x);
return;
}
while (prev->next != pos)
{
prev = prev->next;
assert(prev);
}
SLTNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->next = pos;
}
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
SLTNode* prev = *pphead;
if (prev == pos)
{
SListPopFront(pphead);
return;
}
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* cur = prev->next;
prev->next = cur->next;
free(cur);
cur = NULL;
}
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuyListNode(x);
SLTNode* cur = pos->next;
pos->next = newnode;
newnode->next = cur;
}
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;
}
SLTNode* cur = pos->next;
pos->next = cur->next;
free(cur);
cur = NULL;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170

1.因为头插数据，尾插数据和任意位置插入数据都需要创建一个新节点，那么就可以分装一个函数BuyListNode来创建一个新节点，并且将data设为要传的数值。
2.在头插入数据x时，要改变头结构体指针的指向新的节点，就要传头结构体指针的地址。头结构体指针指向新的节点，新的节点的next指针指向第一个节点或者NULL。

3.尾插分为两种情况：
第一种情况：当链表为空，可以调用头插函数。
第二种情况：当链表不为空，让最后一个节点的指针next存储新节点的地址，新节点的next指针置为空。

4.尾删和头删都要分三种情况讨论：
第一种情况：链表为空。

第二种情况：链表只有一个节点。

第三种情况：链表不止一个节点，那么此时尾删和头删代码就有区别了。

头删

尾删

5.链表的销毁：通过快慢指针进行销毁，一一释放慢指针的节点。快指针控制循环是否结束。

test.c

#include"SList.h"
void TestSList1()
{
SLTNode* plist = NULL;
SListPrint(plist);
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPrint(plist);
SListDestory(&plist);
}
void TestSList2()
{
SLTNode* plist = NULL;
SListPrint(plist);
SListPushFront(&plist, 10);
SListPushFront(&plist, 20);
SListPushFront(&plist, 30);
SListPushFront(&plist, 40);
SListPushFront(&plist, 50);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SLTNode* ret = SListFind(plist, 40);
if (ret != NULL)
{
SListInsert(&plist, ret, 100);
}
SListPrint(plist);
ret = SListFind(plist, 100);
if (ret != NULL)
{
SListErase(&plist, ret);
}
SListPrint(plist);
ret = SListFind(plist, 40);
if (ret != NULL)
{
SListInsertAfter(ret, 200);
}
SListPrint(plist);
ret = SListFind(plist, 200);
if (ret != NULL)
{
SListEraseAfter(ret);
}
SListPrint(plist);
SListDestory(&plist);
}
int main()
{
TestSList1();
TestSList2();
return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61

4.单链表改进

4.1 替换法删除pos

链表只给pos这个参数和插入的值x，要求删除pos位置，并且时间复杂度是O(1)。
用替换法，将pos和pos->next的值互换，创建一个新指针dele指向pos->next。将pos->next->next赋值给pos->next，然后释放掉dele节点。

可以看出该方法解决这道题的致命缺点：pos不能是尾部节点。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
struct SListNode
{
int val;
struct SListNode* next;
};
void SListErase(struct SListNode* pos)
{
assert(pos);
struct SListNode* dele = pos;
dele = dele->next;
pos->val = dele->val;
pos->next = dele->next;
free(dele);
}
int main()
{
struct SListNode* n1 = (struct SListNode*)malloc(sizeof(struct SListNode));
assert(n1);
struct SListNode* n2 = (struct SListNode*)malloc(sizeof(struct SListNode));
assert(n2);
struct SListNode* n3 = (struct SListNode*)malloc(sizeof(struct SListNode));
assert(n3);
struct SListNode* n4 = (struct SListNode*)malloc(sizeof(struct SListNode));
assert(n4);
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;
n1->val = 1;
n2->val = 2;
n3->val = 3;
n4->val = 4;
struct SListNode* cur = n1;
while (cur != NULL)
{
printf("%d->", cur->val);
cur = cur->next;
}
printf("NULL\n");
SListErase(n2);
cur = n1;
while (cur != NULL)
{
printf("%d->", cur->val);
cur = cur->next;
}
printf("NULL");
free(n1);
n1 = NULL;
free(n2);
n2 = NULL;
free(n4);
n4 = NULL;
return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58

4.2 替换法pos之前插入节点

链表只给pos这个参数，要求pos之前插入新节点，并且时间复杂度是O(1)。
用替换法，在pos后面插入一个新节点，并且新节点newcode的val是pos节点的val，pos->next赋值给newcode->next，pos->next指向newcode。

这种方法解决改问题是没有缺陷的。

void SListInsert(struct SListNode* pos, int x)
{
assert(pos);
struct SListNode* newcode = BuyListNode(pos->val);
pos->val = x;
newcode->next = pos->next;
pos->next = newcode;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

5.写在最后

单链表只适合头插头删，因为时间时间复杂度为O(1)。双向链表适合任意位置高效的插入和删除。
那么单链表的学习就到这里了。

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览45641 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪