• 数据结构之顺序表和链表

    码文不易，给个双击~

    码文不易，给个双击~

    码文不易，给个双击~

    目录

    一、线性表

    二、顺序表

    1、概念及结构

    （1）静态顺序表：使用定长数组存储元素。

    （2）动态顺序表：使用动态开辟的数组存储

    2、接口实现

    3、力扣经典题目

    (1)移除元素

    (2)删除有序数组中的重复项

    （3）合并两个有序数组

    4、顺序表的不足之处

    三、链表

    1、链表的概念及结构

    2、链表的分类

    （1）单向或者双向

    （2）带头或者不带头

    （3）循环或者非循环

     3、无头单向非循环链表的实现

    4、单链表经典在线OJ题

    小贴士1：

    小贴士2：

    （1）移除链表元素

    （2）反转链表

    （3）链表的中间结点

    （4）链表中的倒数第k个结点

    （5）合并两个有序链表

    （6）链表分割

    （7）链表的回文结构

    （8）相交链表

    （9）环形链表

    （10）环形链表二

    （11）复制带随机指针的链表

    5、带头双向循环链表的实现

    四、顺序表和链表的区别

    一、线性表

    线性表是n个具有相同特性的数据元素的有限序列。

    常见的线性表：顺序表、链表、栈、队列、字符串……

    线性表在逻辑上是线性结构，但在物理上存储时，通常以数组和链式结构的形式存储。

     

    二、顺序表

    1、概念及结构

    顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

    （1）静态顺序表：使用定长数组存储元素。

    1. //顺序表的静态存储
    2. #define N 12
    3. typedef int SLDataType;
    4. typedef struct SeqList
    5. {
    6. 	SLDataType arr[N];//定长数组
    7. 	size_t size;//有效数据的个数
    8. }SeqList;

    （2）动态顺序表：使用动态开辟的数组存储

    1. //顺序表的动态存储
    2. typedef struct SeqList
    3. {
    4. 	SLDataType* arr;//指向动态开辟的数组
    5. 	size_t size;//有效数据的个数
    6. 	size_t capicity;//容量空间的大小
    7. }SeqList;

     


    2、接口实现

    实际应用中基本上使用动态顺序表，根据需要动态地分配空间大小。

    基本增删查改接口有多种，如下：

    顺序表初始化

    顺序表检查空间，如果满了，进行增容

    顺序表尾插

    顺序表尾删

    顺序表头插

    顺序表头删

    顺序表查找

    顺序表在pos位置插入x

    顺序表删除pos位置的值

    顺序表改变pos位置的值

    顺序表销毁

    顺序表打印

    test.c

    1. #include"OrderTable.h"
    2. void TestOT()
    3. {
    4. 	OT s;//定义一个结构体变量，即顺序表
    5. 	//顺序表初始化
    6. 	OTInit(&s);
    7. 	//顺序表检查空间，如果满了，进行增容
    8. 	OTCheckCapacity(&s);
    9. 	//顺序表尾插
    10. 	OTPushBack(&s, 1);
    11. 	OTPushBack(&s, 2);
    12. 	OTPushBack(&s, 3);
    13. 	OTPushBack(&s, 4);
    14. 	OTPushBack(&s, 5);
    15. 	//顺序表打印
    16. 	OTPrint(&s);
    17. 	//顺序表尾删
    18. 	OTPopBack(&s);
    19. 	//顺序表头插
    20. 	OTPushFront(&s, 1);
    21. 	OTPushFront(&s, 2);
    22. 	OTPushFront(&s, 3);
    23. 	OTPushFront(&s, 4);
    24. 	OTPushFront(&s, 5);
    25. 	OTPrint(&s);
    26. 	//顺序表头删
    27. 	OTPopFront(&s);
    28. 	//顺序表查找
    29. 	OTFind(&s, 2);
    30. 	//顺序表在pos位置插入x,pos是指下标
    31. 	OTInsert(&s, 0, 100);
    32. 	//顺序表删除pos位置的值
    33. 	OTErase(&s, 1);
    34. 	//顺序表改变pos位置的值
    35. 	OTChange(&s, 2,99);
    36. 	//顺序表销毁
    37. 	OTDestroy(&s);
    38. }
    39. int main()
    40. {
    41. 	TestOT();//测试顺序表基本增删查改接口功能
    42. 	return 0;
    43. }

    OrderTable.h

    1. #include
    2. #include
    3. #pragma once
    4. #include
    5. //顺序表的动态存储
    6. typedef int OTDataType;
    7. typedef struct OrderTable
    8. {
    9. 	OTDataType* a;//指针指向动态开辟的数组
    10. 	size_t size;//有效数据的个数
    11. 	size_t capacity;//存储空间的大小
    12. }OT;
    13.  
    14. //顺序表初始化
    15. void OTInit(OT* s);
    16. //顺序表检查空间，如果满了，进行增容
    17. void OTCheckCapacity(OT* s);
    18. //顺序表尾插
    19. void OTPushBack(OT* s, OTDataType x);
    20. //顺序表打印
    21. void OTPrint(OT* s);
    22. //顺序表尾删
    23. void OTPopBack(OT* s);
    24. //顺序表头插
    25. void OTPushFront(OT* s, OTDataType x);
    26. //顺序表头删
    27. void OTPopFront(OT* s);
    28. //顺序表查找
    29. void OTFind(OT* s, OTDataType x);
    30. //顺序表在pos位置插入x
    31. void OTInsert(OT* s, size_t pos, OTDataType x);
    32. //顺序表删除pos位置的值
    33. void OTErase(OT* s, size_t pos);
    34. //顺序表改变pos位置的值
    35. void OTChange(OT* s, size_t pos, OTDataType x);
    36. //顺序表销毁
    37. void OTDestroy(OT* s);

    OrderTable.c

    1. #include"OrderTable.h"
    2.  
    3. void OTInit(OT* s)
    4. {
    5. 	assert(s);
    6. 	s->a = NULL;
    7. 	s->size = 0;
    8. 	s->capacity = 0;
    9. }
    10.  
    11. void OTCheckCapacity(OT* s)
    12. {
    13. 	assert(s);
    14. 	//检查容量
    15. 	if (s->size == s->capacity)
    16. 	{
    17. 		size_t newcapacity = s->capacity == 0 ? 4 : s->capacity * 2;
    18. 		OTDataType* tmp = (OTDataType*)realloc(s->a, newcapacity * sizeof(OTDataType));
    19. 		if (tmp == NULL)
    20. 		{
    21. 			perror("realloc fail\n");
    22. 			return;
    23. 		}
    24. 		s->a = tmp;
    25. 		s->capacity = newcapacity;
    26. 	}
    27. }
    28.  
    29. void OTPushBack(OT* s, OTDataType x)
    30. {
    31. 	assert(s);
    32. 	OTCheckCapacity(s);
    33. 	s->a[s->size] = x;
    34. 	s->size++;
    35. }
    36.  
    37. void OTPrint(const OT* s)
    38. {
    39. 	assert(s);
    40. 	int i = 0;
    41. 	for (i = 0; i < s->size; ++i)
    42. 	{
    43. 		printf("%d ", s->a[i]);
    44. 	}
    45. 	printf("\n");
    46. }
    47.  
    48. void OTPopBack(OT* s)
    49. {
    50. 	assert(s);
    51. 	if (s->size == 0)
    52. 	{
    53. 		return;
    54. 	}
    55. 	s->size--;
    56. }
    57.  
    58. void OTPushFront(OT* s, OTDataType x)
    59. {
    60. 	assert(s);
    61. 	OTCheckCapacity(s);
    62. 	//挪动数据
    63. 	int end = s->size - 1;
    64. 	while (end >= 0)
    65. 	{
    66. 		s->a[end + 1] = s->a[end];
    67. 		--end;
    68. 	}
    69. 	s->a[0] = x;
    70. 	s->size++;
    71. }
    72.  
    73. void OTPopFront(OT* s)
    74. {
    75. 	assert(s);
    76. 	assert(s->size > 0);
    77. 	int begin = 1;
    78. 	while (begin < s->size)
    79. 	{
    80. 		s->a[begin - 1] = s->a[begin];
    81. 		++begin;
    82. 	}
    83. 	s->size--;
    84. }
    85.  
    86. void OTFind(OT* s, OTDataType x)
    87. {
    88. 	assert(s);
    89. 	int i = 0;
    90. 	for (i = 0; i < s->size; ++i)
    91. 	{
    92. 		if (s->a[i] == x)
    93. 		{
    94. 			return i;
    95. 		}
    96. 	}
    97. 	return -1;
    98. }
    99.  
    100. void OTInsert(OT* s, size_t pos, OTDataType x)
    101. {
    102. 	assert(s);
    103. 	assert(pos <= s->size);
    104. 	OTCheckCapacity(s);
    105. 	//挪动数据
    106. 	size_t end = s->size - 1;
    107. 	while (end >= pos)
    108. 	{
    109. 		s->a[end + 1] = s->a[end];
    110. 		--end;
    111. 	}
    112. 	s->a[pos] = x;
    113. 	s->size++;
    114. }
    115.  
    116. void OTErase(OT* s, size_t pos)
    117. {
    118. 	assert(s);
    119. 	assert(pos < s->size);
    120. 	size_t begin = pos;
    121. 	while (begin < s->size - 1)
    122. 	{
    123. 		s->a[begin] = s->a[begin + 1];
    124. 		++begin;
    125. 	}
    126. 	s->size--;
    127. }
    128.  
    129. void OTChange(OT* s, size_t pos, OTDataType x)
    130. {
    131. 	assert(s);
    132. 	assert(pos <= s->size - 1);
    133. 	s->a[pos] = x;
    134. }
    135.  
    136. void OTDestroy(OT* s)
    137. {
    138. 	assert(s);
    139. 	free(s->a);
    140. 	s->a = NULL;
    141. 	s->size = 0;
    142. 	s->capacity = 0;
    143. }

    3、力扣经典题目

    (1)移除元素

    给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

    不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

    元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

    https://leetcode.cn/problems/remove-element/

    (2)删除有序数组中的重复项

    给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

    由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

    将最终结果插入 nums 的前 k 个位置后返回 k 。

    不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

    https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

    （3）合并两个有序数组

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

    请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

    注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

    https://leetcode.cn/problems/merge-sorted-array/

    4、顺序表的不足之处

    1. 中间/头部的插入删除，时间复杂度为O(N)
    2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
    3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到
    200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

    因此，我们便有了链表~

    三、链表

    1、链表的概念及结构

    链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

    假设在32位系统上，结点中值域为int类型，则一个节点的大小为8个字节，则可能有下述链表：

    从上图可知：

    a.链式结构在逻辑上是连续的，但是在物理上不一定连续

    b.现实中的结点一般都是从堆上申请出来的

    c. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

    2、链表的分类

    （1）单向或者双向

    （2）带头或者不带头

    （3）循环或者非循环

    实际中最常用的是无头单向非循环链表和带头双向循环链表：

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

     3、无头单向非循环链表的实现

    定义一个结构体类型的变量，即链表的结点：

    1. typedef int SLDataType;
    2. //定义一个结构体类型的变量，即链表的结点
    3. typedef struct SListNode
    4. {
    5. 	SLDataType data;
    6. 	struct SListNode* next;
    7. }SLN;

    注意：

    1. typedef int SLDataType;
    2. //定义一个结构体类型的变量，即链表的结点
    3. typedef struct SListNode
    4. {
    5. 	SLDataType data;
    6. 	struct SListNode* next;
    7. }SLN, * PSLN;
    8. //以下三种结构体指针等价
    9. //SLN*
    10. //PSLN  PSLN是指针而不是指针变量
    11. //struct SListNode

    无头单向非循环链表的实现包括：

    单链表打印

    1. //此处SLN不需要断言，因为结点（结构体类型）是允许为空的，即没有结点
    2. void SListPrint(SLN* phead)
    3. {
    4. 	SLN* current = phead;
    5. 	while (current != NULL)
    6. 	{
    7. 		printf("%d->", current->data);
    8. 		current = current->next;
    9. 	}
    10. 	printf("NULL\n");
    11. }

    动态申请一个节点

    1. SLN* SLBuyNode(SLDataType x)
    2. {
    3. 	//为什么不直接用静态空间呢？因为静态空间是在栈区上创建的，使用完后立即销毁，
    4. 	//而动态空间只有free之后才会被回收
    5. 	SLN* nownode = (SLN*)malloc(sizeof(SLN));
    6. 	if (nownode == NULL)
    7. 	{
    8. 		perror("malloc fail\n");
    9. 		exit(-1);
    10. 	}
    11. 	nownode->data = x;
    12. 	nownode->next = NULL;
    13. 	return nownode;
    14. }

    单链表尾插

    1. //此处结点传参的时候用二级指针，是因为我们将要改变的就是指针，就好比交换两个数，
    2. //我们将数的地址作为实参才能改变数，同理，我们将指针的地址作为实参才能改变指针
    3. void SListPushBack(SLN** pphead, SLDataType x)
    4. {
    5. 	assert(pphead);//此时断言是因为指针的地址一定不能为空，否则程序错误
    6. 	SLN* nownode = SLBuyNode(x);
    7. 	if (*pphead == NULL)
    8. 	{
    9. 		*pphead = nownode;
    10. 	}
    11. 	else
    12. 	{
    13. 		SLN* tail = *pphead;
    14. 		while (tail->next != NULL)
    15. 		{
    16. 			tail = tail->next;
    17. 		}
    18. 		tail->next = nownode;
    19. 	}
    20. }

    单链表头插

    1. void SListPushFront(SLN** pphead, SLDataType x)
    2. {
    3. 	assert(pphead);
    4. 	SLN* newnode = SLBuyNode(x);
    5. 	newnode->next = *pphead;
    6. 	*pphead = newnode;
    7. }

    单链表尾删

    1. void SListPopBack(SLN** pphead)
    2. {
    3. 	assert(pphead);
    4. 	assert(*pphead != NULL);//这里断言是因为要保持链表至少有一个结点，才有删除的余地
    5. 	//一个结点
    6. 	if ((*pphead)->next == NULL)
    7. 	{
    8. 		free(*pphead);
    9. 		*pphead = NULL;
    10. 	}
    11. 	//多个结点
    12. 	else
    13. 	{
    14. 		//找尾
    15. 		SLN* previous = NULL;//这里的previous用来配合tail找到最后一个结点和倒数第二个结点，自有妙用
    16. 		SLN* tail = *pphead;
    17. 		while (tail->next != NULL)
    18. 		{
    19. 			previous = tail;
    20. 			tail = tail->next;
    21. 		}
    22. 		previous->next = NULL;
    23. 		free(tail);
    24. 		tail = NULL;
    25. 		//或者
    26. 	/*	SLN* tail = *pphead;
    27. 		while (tail->next->next != NULL)
    28. 		{
    29. 			tail = tail->next;
    30. 		}
    31. 		free(tail->next);
    32. 		tail->next = NULL;*/
    33. 	}
    34. }

    单链表头删

    1. void SListPopFront(SLN** pphead)
    2. {
    3. 	assert(pphead);
    4. 	assert(pphead != NULL);
    5. 	SLN* delete = *pphead;
    6. 	*pphead = (*pphead)->next;
    7. 	free(delete);
    8. 	delete = NULL;
    9. }

    单链表查找

    1. SLN* SListFind(SLN* phead, SLDataType x)
    2. {
    3. 	SLN* current = phead;
    4. 	while (current != NULL)
    5. 	{
    6. 		if (current->data == x)
    7. 		{
    8. 			return current;
    9. 		}
    10. 		current = current->next;
    11. 	}
    12. 	return NULL;
    13. }

    单链表在position位置之前插入

    1.     position = SListFind(pList, 2);
    2.     if (position != NULL)
    3.     {
    4.     	SListInsert(&pList, position, 20);
    5.     }    
    6.  
    7.  
    8.  
    9. void SListInsert(SLN** pphead, SLN* position, SLDataType x)
    10. {
    11. 	assert(pphead);
    12. 	assert(position);
    13. 	if (position == *pphead)
    14. 	{
    15. 		SListPushFront(pphead, 20);
    16. 	}
    17. 	else
    18. 	{
    19. 		SLN* previous = *pphead;
    20. 		while (previous->next!=position)
    21. 		{
    22. 			previous = previous->next;
    23. 			assert(previous);//暴力检查，如果position不指向链表，prev为空，还没有找到pos，说明pos传错了
    24. 		}
    25. 		SLN* newnode = SLBuyNode(x);
    26. 		previous->next = newnode;
    27. 		newnode->next = position;
    28. 	}
    29. }

    单链表在position位置之后插入

    1. 	position = SListFind(pList, 1);
    2. 	if (position != NULL)
    3. 	{
    4. 		SListInsertAfter(position, 10);
    5. 	}
    6.  
    7.  
    8.  
    9. void SListInsertAfter(SLN* position, SLDataType x)
    10. {
    11. 	assert(position);
    12. 	SLN* newnode = SLBuyNode(x);
    13. 	newnode->next = position->next;
    14. 	position->next = newnode;
    15. }

    单链表删除position处的位置

    1. 	position = SListFind(pList, 2);
    2. 	if (position != NULL)
    3. 	{
    4. 		SListErase(&pList, position);
    5. 		position = NULL;
    6. 	}
    7.  
    8.  
    9.  
    10. void SListErase(SLN** pphead, SLN* position)
    11. {
    12. 	assert(pphead);
    13. 	assert(position);
    14. 	if (position == *pphead)
    15. 	{
    16. 		SListPopFront(pphead);
    17. 	}
    18. 	else
    19. 	{
    20. 		SLN* previous = *pphead;
    21. 		if (previous->next != position)
    22. 		{
    23. 			previous = previous->next;
    24. 			assert(previous);
    25. 		}
    26. 		previous->next = position->next;
    27. 		free(position);
    28. 		position = NULL;
    29. 	}
    30. }

    单链表删除position之后的位置

    1. 	position = SListFind(pList, 2);
    2. 	if (position != NULL)
    3. 	{
    4. 		SListEraseAfter(position);
    5. 		position = NULL;
    6. 	}
    7.  
    8.  
    9.  
    10. void SListEraseAfter(SLN* position)
    11. {
    12. 	assert(position);
    13. 	if (position->next == NULL)
    14. 	{
    15. 		return;
    16. 	}
    17. 	else
    18. 	{
    19. 		SLN* next = position->next;
    20. 		position->next = next->next;
    21. 		free(next);
    22. 		next = NULL;
    23. 	}
    24. }

    单链表销毁

    1. void SListDestroy(SLN** pphead)
    2. {
    3. 	assert(pphead);
    4. 	SLN* current = *pphead;
    5. 	while (current != NULL)
    6. 	{
    7. 		SLN* next = current->next;
    8. 		free(current);
    9. 		current = next;
    10. 	}
    11. 	*pphead = NULL;
    12. }

    增删改查各功能图解：

     

    源代码：

    Test.c:

    1. #include"SList.h"
    2. void TestSList()
    3. {
    4. 	SLN* pList = NULL;
    5. 	SListPushBack(&pList, 1);//单链表尾插
    6. 	SListPushBack(&pList, 2); 
    7. 	SListPushBack(&pList, 3);
    8. 	SListPushBack(&pList, 4);
    9. 	SListPrint(pList);//单链表打印
    10. 	SListPushFront(&pList, 1);//单链表头插
    11. 	SListPushFront(&pList, 2);
    12. 	SListPushFront(&pList, 3);
    13. 	SListPushFront(&pList, 4);
    14. 	SListPrint(pList);//单链表打印
    15. 	SListPopBack(&pList);//单链表尾删
    16. 	SListPrint(pList);//单链表打印
    17. 	SListPopFront(&pList);//单链表头删
    18. 	SListPrint(pList);//单链表打印
    19. 	SLN* position = SListFind(pList, 3);//单链表查找
    20. 	if (position != NULL)
    21. 	{
    22. 		position->data *= 10;
    23. 		printf("找到了\n");
    24. 	}
    25. 	else
    26. 	{
    27. 		printf("没找到\n");
    28. 	}
    29. 	SListPrint(pList);//单链表打印
    30. 	//单链表在position之前插入
    31. 	position = SListFind(pList, 2);
    32. 	if (position != NULL)
    33. 	{
    34. 		SListInsert(&pList, position, 20);
    35. 	}
    36. 	SListPrint(pList);//单链表打印
    37. 	position = SListFind(pList, 1);
    38. 	if (position != NULL)
    39. 	{
    40. 		SListInsertAfter(position, 10);
    41. 	}
    42. 	SListPrint(pList);//单链表打印
    43. 	//单链表删除position处的位置
    44. 	position = SListFind(pList, 2);
    45. 	if (position != NULL)
    46. 	{
    47. 		SListErase(&pList, position);
    48. 		position = NULL;
    49. 	}
    50. 	SListPrint(pList);//单链表打印
    51. 	//单链表删除position之后的位置
    52. 	position = SListFind(pList, 2);
    53. 	if (position != NULL)
    54. 	{
    55. 		SListEraseAfter(position);
    56. 		position = NULL;
    57. 	}
    58. 	SListPrint(pList);//单链表打印	
    59.     SListDestroy(&pList);//单链表销毁
    60. }
    61. int main()
    62. {
    63. 	TestSList();
    64. 	return 0;
    65. }

    SList.h:

    1. #pragma once//避免头文件的重复引入
    2. #include
    3. #include
    4. #include
    5.  
    6.  
    7. typedef int SLDataType;
    8. //定义一个结构体类型的变量，即链表的结点
    9. typedef struct SListNode
    10. {
    11. 	SLDataType data;
    12. 	struct SListNode* next;
    13. }SLN;
    14.  
    15. //单链表打印
    16. void SListPrint(SLN* phead);
    17. //动态申请一个结点
    18. SLN* SLBuyNode(SLDataType x);
    19. //单链表尾插
    20. void SListPushBack(SLN** pphead, SLDataType x);
    21. //单链表头插
    22. void SListPushFront(SLN** pphead, SLDataType x);
    23. //单链表尾删
    24. void SListPopBack(SLN** pphead);
    25. //单链表头删
    26. void SListPopFront(SLN** pphead);
    27. //单链表查找
    28. SLN* SListFind(SLN* phead, SLDataType x);
    29. //在position位置之前插入
    30. void SListInsert(SLN** pphead, SLN* position, SLDataType x);
    31. //在position位置之后插入
    32. void SListInsertAfter(SLN* position, SLDataType x);
    33. //删除position位置的值
    34. void SListErase(SLN** pphead, SLN* position);
    35. //删除position之后的位置
    36. void SListEraseAfter(SLN* position);
    37. //单链表销毁
    38. void SListDestroy(SLN** pphead);

    SList.c:

    1. #include"SList.h"
    2.  
    3. //此处SLN不需要断言，因为结点（结构体类型）是允许为空的，即没有结点
    4. void SListPrint(SLN* phead)
    5. {
    6. 	SLN* current = phead;
    7. 	while (current != NULL)
    8. 	{
    9. 		printf("%d->", current->data);
    10. 		current = current->next;
    11. 	}
    12. 	printf("NULL\n");
    13. }
    14.  
    15. SLN* SLBuyNode(SLDataType x)
    16. {
    17. 	//为什么不直接用静态空间呢？因为静态空间是在栈区上创建的，使用完后立即销毁，
    18. 	//而动态空间只有free之后才会被回收
    19. 	SLN* newnode = (SLN*)malloc(sizeof(SLN));
    20. 	if (newnode == NULL)
    21. 	{
    22. 		perror("malloc fail\n");
    23. 		exit(-1);
    24. 	}
    25. 	newnode->data = x;
    26. 	newnode->next = NULL;
    27. 	return newnode;
    28. }
    29.  
    30. //此处结点传参的时候用二级指针，是因为我们将要改变的就是指针，就好比交换两个数，
    31. //我们将数的地址作为实参才能改变数，同理，我们将指针的地址作为实参才能改变指针
    32. void SListPushBack(SLN** pphead, SLDataType x)
    33. {
    34. 	assert(pphead);//此时断言是因为指针的地址一定不能为空，否则程序错误
    35. 	SLN* newnode = SLBuyNode(x);
    36. 	if (*pphead == NULL)
    37. 	{
    38. 		*pphead = newnode;
    39. 	}
    40. 	else
    41. 	{
    42. 		//找尾
    43. 		SLN* tail = *pphead;
    44. 		while (tail->next != NULL)
    45. 		{
    46. 			tail = tail->next;
    47. 		}
    48. 		tail->next = newnode;
    49. 	}
    50. }
    51.  
    52. void SListPushFront(SLN** pphead, SLDataType x)
    53. {
    54. 	assert(pphead);
    55. 	SLN* newnode = SLBuyNode(x);
    56. 	newnode->next = *pphead;
    57. 	*pphead = newnode;
    58. }
    59.  
    60. void SListPopBack(SLN** pphead)
    61. {
    62. 	assert(pphead);
    63. 	assert(*pphead != NULL);//这里断言是因为要保持链表至少有一个结点，才有删除的余地
    64. 	//一个结点
    65. 	if ((*pphead)->next == NULL)
    66. 	{
    67. 		free(*pphead);
    68. 		*pphead = NULL;
    69. 	}
    70. 	//多个结点
    71. 	else
    72. 	{
    73. 		//找尾
    74. 		SLN* previous = NULL;//这里的previous用来配合tail找到最后一个结点和倒数第二个结点，自有妙用
    75. 		SLN* tail = *pphead;
    76. 		while (tail->next != NULL)
    77. 		{
    78. 			previous = tail;
    79. 			tail = tail->next;
    80. 		}
    81. 		previous->next = NULL;
    82. 		free(tail);
    83. 		tail = NULL;
    84. 		//或者
    85. 	/*	SLN* tail = *pphead;
    86. 		while (tail->next->next != NULL)
    87. 		{
    88. 			tail = tail->next;
    89. 		}
    90. 		free(tail->next);
    91. 		tail->next = NULL;*/
    92. 	}
    93. }
    94.  
    95. void SListPopFront(SLN** pphead)
    96. {
    97. 	assert(pphead);
    98. 	assert(pphead != NULL);
    99. 	SLN* delete = *pphead;
    100. 	*pphead = (*pphead)->next;
    101. 	free(delete);
    102. 	delete = NULL;
    103. }
    104.  
    105. SLN* SListFind(SLN* phead, SLDataType x)
    106. {
    107. 	SLN* current = phead;
    108. 	while (current != NULL)
    109. 	{
    110. 		if (current->data == x)
    111. 		{
    112. 			return current;
    113. 		}
    114. 		current = current->next;
    115. 	}
    116. 	return NULL;
    117. }
    118.  
    119. void SListInsert(SLN** pphead, SLN* position, SLDataType x)
    120. {
    121. 	assert(pphead);
    122. 	assert(position);
    123. 	if (position == *pphead)
    124. 	{
    125. 		SListPushFront(pphead, 20);
    126. 	}
    127. 	else
    128. 	{
    129. 		SLN* previous = *pphead;
    130. 		while (previous->next!=position)
    131. 		{
    132. 			previous = previous->next;
    133. 			assert(previous);//暴力检查，如果position不指向链表，prev为空，还没有找到pos，说明pos传错了
    134. 		}
    135. 		SLN* newnode = SLBuyNode(x);
    136. 		previous->next = newnode;
    137. 		newnode->next = position;
    138. 	}
    139. }
    140.  
    141. void SListInsertAfter(SLN* position, SLDataType x)
    142. {
    143. 	assert(position);
    144. 	SLN* newnode = SLBuyNode(x);
    145. 	newnode->next = position->next;
    146. 	position->next = newnode;
    147. }
    148.  
    149. void SListErase(SLN** pphead, SLN* position)
    150. {
    151. 	assert(pphead);
    152. 	assert(position);
    153. 	if (position == *pphead)
    154. 	{
    155. 		SListPopFront(pphead);
    156. 	}
    157. 	else
    158. 	{
    159. 		SLN* previous = *pphead;
    160. 		if (previous->next != position)
    161. 		{
    162. 			previous = previous->next;
    163. 			assert(previous);
    164. 		}
    165. 		previous->next = position->next;
    166. 		free(position);
    167. 		position == NULL;
    168. 	}
    169. }
    170.  
    171. void SListEraseAfter(SLN* position)
    172. {
    173. 	assert(position);
    174. 	if (position->next == NULL)
    175. 	{
    176. 		return;
    177. 	}
    178. 	else
    179. 	{
    180. 		SLN* next = position->next;
    181. 		position->next = next->next;
    182. 		free(next);
    183. 		next == NULL;
    184. 	}
    185. }
    186.  
    187. void SListDestroy(SLN** pphead)
    188. {
    189. 	assert(pphead);
    190. 	SLN* current = *pphead;
    191. 	while (current != NULL)
    192. 	{
    193. 		SLN* next = current->next;
    194. 		free(current);
    195. 		current = next;
    196. 	}
    197. 	*pphead = NULL;
    198. }

    4、单链表经典在线OJ题

    小贴士1：

    带哨兵头(guard)和不带哨兵头(head)

    小贴士2：

    找工作正式笔试中没有测试用例，也不能进行调试，所以我们就应该学会自己猜测试用例。

    测试主要分为常规场景和极端场景（边界）。

    测试代码（自己备份好，平时练习时遇到可以用）：

    1. int main()
    2. {
    3. 	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    4. 	assert(n1);
    5. 	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    6. 	assert(n2);
    7. 	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    8. 	assert(n3);
    9. 	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    10. 	assert(n4);
    11. 	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
    12. 	assert(n5);
    13. 	struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
    14. 	assert(n6);
    15. 	struct ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));
    16. 	assert(n7);
    17.  
    18. 	n1->next = n2;
    19. 	n2->next = n3;
    20. 	n3->next = n4;
    21. 	n4->next = n5;
    22. 	n5->next = n6;
    23. 	n6->next = n7;
    24. 	n7->next = NULL;
    25.  
    26. 	n1->val = 1;
    27. 	n2->val = 2;
    28. 	n3->val = 6;
    29. 	n4->val = 3;
    30. 	n5->val = 4;
    31. 	n6->val = 5;
    32. 	n7->val = 6;
    33. 	struct ListNode* head = removeElements(n1, 6);
    34.  
    35.  
    36. 	return 0;
    37. }

    （1）移除链表元素

    给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

    https://leetcode.cn/problems/remove-linked-list-elements/

    （2）反转链表

    给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

    https://leetcode.cn/problems/reverse-linked-list/description/

    （3）链表的中间结点

    给定一个头结点为 head 的非空单链表，返回链表的中间结点。

    如果有两个中间结点，则返回第二个中间结点。

    https://leetcode.cn/problems/middle-of-the-linked-list/description/

    （4）链表中的倒数第k个结点

    输入一个链表，输出该链表中倒数第k个结点。

    https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

    （5）合并两个有序链表

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    https://leetcode.cn/problems/merge-two-sorted-lists/description/

    （6）链表分割

    现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

    https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

    （7）链表的回文结构

    对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

    https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

    （8）相交链表

    给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

    https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

    （9）环形链表

    给你一个链表的头节点 head ，判断链表中是否有环。

    如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

    如果链表中存在环 ，则返回 true 。 否则，返回 false 。

    https://leetcode.cn/problems/linked-list-cycle/description/

    （10）环形链表二

    给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

    如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

    不允许修改 链表。

    https://leetcode.cn/problems/linked-list-cycle-ii/description/

    （11）复制带随机指针的链表

    给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

    构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

    例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

    返回复制链表的头节点。

    https://leetcode.cn/problems/copy-list-with-random-pointer/description/

    5、带头双向循环链表的实现

    首先在头文件中声明结构体类型

    1. //声明一个结构体类型，即双链表的结点
    2. typedef int LTDataType;
    3. typedef struct ListNode
    4. {
    5. 	struct ListNode* prev;
    6. 	struct ListNode* next;
    7. 	LTDataType data;
    8. }LTNode;

    带头双向循环链表增删改查各功能的实现：

    创建返回链表的头结点（即初始化）

    1. //以下方法是使用带哨兵头的方法，当然也可以使用二级指针传参的方式
    2. LTNode* ListInit()
    3. {
    4. 	LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
    5. 	if (guard == NULL)
    6. 	{
    7. 		printf("malloc fail\n");
    8. 		exit(-1);
    9. 	}
    10. 	guard->next = guard;
    11. 	guard->prev = guard;
    12. 	return guard;
    13. }

    双向链表打印

    1. void ListPrint(LTNode* phead)
    2. {
    3. 	assert(phead);
    4. 	LTNode* cur = phead->next;
    5. 	printf("head<=>");
    6. 	while (cur != phead)
    7. 	{
    8. 		printf("%d<=>", cur->data);
    9. 		cur = cur->next;
    10. 	}
    11. 	printf("\n");
    12. }

    新建一个结点

    1. LTNode* BuyListNode(LTDataType x)
    2. {
    3. 	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    4. 	if (node == NULL)
    5. 	{
    6. 		printf("malloc fail\n");
    7. 		exit(-1);
    8. 	}
    9. 	node->next = NULL;
    10. 	node->prev = NULL;
    11. 	node->data = x;
    12. 	return node;
    13. }

    双向链表尾插

    1. void ListPushBack(LTNode* phead, LTDataType x)
    2. {
    3. 	LTNode* newnode = BuyListNode(x);
    4. 	LTNode* tail = phead->prev;
    5. 	tail->next = newnode;
    6. 	newnode->prev = tail;
    7. 	newnode->next = phead;
    8. 	phead->prev=newnode;
    9. }

    双向链表尾删

    1. void ListPopBack(LTNode* phead)
    2. {
    3. 	assert(phead);
    4. 	assert(!ListEmpty(phead));
    5. 	LTNode* tail = phead->prev;
    6. 	LTNode* prev = tail->prev;
    7. 	prev->next = phead;
    8. 	phead->prev = prev;
    9. 	free(tail);
    10. }

    双向链表头插

    1. void ListPushFront(LTNode* phead, LTDataType x)
    2. {
    3. 	assert(phead);
    4. 	LTNode* newnode = BuyListNode(x);
    5. 	//newnode->next = phead->next;
    6. 	//phead->next->prev = newnode;
    7. 	//phead->next = newnode;
    8. 	//newnode->prev = phead;
    9. 	//不关心顺序的方法
    10. 	LTNode* first = phead->next;
    11. 	phead->next = newnode;
    12. 	newnode->prev = phead;
    13. 	newnode->next = first;
    14. 	first->prev = newnode;
    15. }

    双向链表头删

    1. void ListPopFront(LTNode* phead)
    2. {
    3. 	assert(phead);
    4. 	assert(!ListEmpty(phead));
    5. 	LTNode* first = phead->next;
    6. 	LTNode* second = first->next;
    7. 	phead->next = second;
    8. 	second->prev = phead;
    9. 	free(first);
    10. }

    双向链表查找

    1. LTNode* ListFind(LTNode* phead, LTDataType x)
    2. {
    3. 	assert(phead);
    4. 	LTNode* cur = phead->next;
    5. 	while (cur != phead)
    6. 	{
    7. 		if (cur->data == x);
    8. 		{
    9. 			return cur;
    10. 		}
    11. 		cur = cur->next;
    12. 	}
    13. 	return NULL;
    14. }

    双向链表在pos位置前插入

    1. void ListInsert(LTNode* pos, LTDataType x)
    2. {
    3. 	assert(pos);
    4. 	LTNode* prev = pos->prev;
    5. 	LTNode* newnode = BuyListNode(x);
    6. 	prev->next = newnode;
    7. 	newnode->prev = prev;
    8. 	newnode->next = pos;
    9. 	pos->prev = newnode;
    10. }

    双向链表删除pos位置的结点

    1. void ListErase(LTNode* pos)
    2. {
    3. 	assert(pos);
    4. 	LTNode* prev = pos->prev;
    5. 	LTNode* next = pos->next;
    6. 	prev->next = next;
    7. 	next->prev = prev;
    8. 	free(pos);
    9. 	pos = NULL;
    10. }

    双向链表销毁

    1. void ListDestroy(LTNode* phead)
    2. {
    3. 	assert(phead);
    4. 	LTNode* cur = phead->next;
    5. 	while (cur != phead)
    6. 	{
    7. 		LTNode* next = cur->next;
    8. 		free(cur);
    9. 		cur = next;
    10. 	}
    11. 	free(phead);
    12. 	phead = NULL;
    13. }

    源代码：

    List.h:

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6.  
    7. //声明一个结构体类型，即双链表的结点
    8. typedef int LTDataType;
    9. typedef struct ListNode
    10. {
    11. 	struct ListNode* prev;
    12. 	struct ListNode* next;
    13. 	LTDataType data;
    14. }LTNode;
    15.  
    16. //创建返回链表的头结点
    17. LTNode* ListInit();
    18. //双向链表打印
    19. void ListPrint(LTNode* phead);
    20. //双向链表尾插
    21. void ListPushBack(LTNode* phead, LTDataType x);
    22. //如果是链表是空则返回真，否则返回假
    23. bool ListEmpty(LTNode* phead);
    24. //双向链表尾删
    25. void ListPopBack(LTNode* phead);
    26. //双向链表头插
    27. void ListPushFront(LTNode* phead, LTDataType);
    28. //双向链表头删
    29. void ListPopFront(LTNode* phead);
    30. //统计链表结点个数（不包括哨兵头）
    31. size_t ListSize(LTNode* phead);
    32. //双向链表查找
    33. LTNode* ListFind(LTNode* phead, LTDataType x);
    34. //双向链表在pos位置之前插入
    35. void ListInsert(LTNode* phead, LTDataType x);
    36. //双向链表删除pos位置的结点
    37. void ListErase(LTNode* pos);
    38. //双向链表销毁
    39. void ListDestroy(LTNode* phead);

    List.c:

    1. #include "List.h"
    2.  
    3. #define _CRT_SECURE_NO_WARNINGS
    4.  
    5. LTNode* ListInit()
    6. {
    7. 	LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
    8. 	if (guard == NULL)
    9. 	{
    10. 		printf("malloc fail\n");
    11. 		exit(-1);
    12. 	}
    13. 	guard->next = guard;
    14. 	guard->prev = guard;
    15. 	return guard;
    16. }
    17.  
    18. void ListPrint(LTNode* phead)
    19. {
    20. 	assert(phead);
    21. 	LTNode* cur = phead->next;
    22. 	printf("head<=>");
    23. 	while (cur != phead)
    24. 	{
    25. 		printf("%d<=>", cur->data);
    26. 		cur = cur->next;
    27. 	}
    28. 	printf("\n");
    29. }
    30.  
    31. //新建一个结点
    32. LTNode* BuyListNode(LTDataType x)
    33. {
    34. 	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    35. 	if (node == NULL)
    36. 	{
    37. 		printf("malloc fail\n");
    38. 		exit(-1);
    39. 	}
    40. 	node->next = NULL;
    41. 	node->prev = NULL;
    42. 	node->data = x;
    43. 	return node;
    44. }
    45.  
    46. void ListPushBack(LTNode* phead, LTDataType x)
    47. {
    48. 	LTNode* newnode = BuyListNode(x);
    49. 	LTNode* tail = phead->prev;
    50. 	tail->next = newnode;
    51. 	newnode->prev = tail;
    52. 	newnode->next = phead;
    53. 	phead->prev=newnode;
    54. }
    55.  
    56. bool ListEmpty(LTNode* phead)
    57. {
    58. 	assert(phead);
    59. 	//if (phead->next == phead)
    60. 	//	return true;
    61. 	//else
    62. 	//	return false;
    63. 	return phead->next == phead;
    64. }
    65.  
    66. void ListPopBack(LTNode* phead)
    67. {
    68. 	assert(phead);
    69. 	assert(!ListEmpty(phead));
    70. 	LTNode* tail = phead->prev;
    71. 	LTNode* prev = tail->prev;
    72. 	prev->next = phead;
    73. 	phead->prev = prev;
    74. 	free(tail);
    75. }
    76.  
    77. void ListPushFront(LTNode* phead, LTDataType x)
    78. {
    79. 	assert(phead);
    80. 	LTNode* newnode = BuyListNode(x);
    81. 	//newnode->next = phead->next;
    82. 	//phead->next->prev = newnode;
    83. 	//phead->next = newnode;
    84. 	//newnode->prev = phead;
    85. 	//不关心顺序的方法
    86. 	LTNode* first = phead->next;
    87. 	phead->next = newnode;
    88. 	newnode->prev = phead;
    89. 	newnode->next = first;
    90. 	first->prev = newnode;
    91. }
    92.  
    93. void ListPopFront(LTNode* phead)
    94. {
    95. 	assert(phead);
    96. 	assert(!ListEmpty(phead));
    97. 	LTNode* first = phead->next;
    98. 	LTNode* second = first->next;
    99. 	phead->next = second;
    100. 	second->prev = phead;
    101. 	free(first);
    102. }
    103.  
    104. size_t ListSize(LTNode* phead)
    105. {
    106. 	assert(phead);
    107. 	size_t n = 0;
    108. 	LTNode* cur = phead->next;
    109. 	while (cur != phead)
    110. 	{
    111. 		++n;
    112. 		cur = cur->next;
    113. 	}
    114. 	return n;
    115. }
    116.  
    117. LTNode* ListFind(LTNode* phead, LTDataType x)
    118. {
    119. 	assert(phead);
    120. 	size_t n = 0;
    121. 	LTNode* cur = phead->next;
    122. 	while (cur != phead)
    123. 	{
    124. 		if (cur->data == x);
    125. 		{
    126. 			return cur;
    127. 		}
    128. 		cur = cur->next;
    129. 	}
    130. 	return NULL;
    131. }
    132.  
    133. void ListInsert(LTNode* pos, LTDataType x)
    134. {
    135. 	assert(pos);
    136. 	LTNode* prev = pos->prev;
    137. 	LTNode* newnode = BuyListNode(x);
    138. 	prev->next = newnode;
    139. 	newnode->prev = prev;
    140. 	newnode->next = pos;
    141. 	pos->prev = newnode;
    142. }
    143.  
    144. void ListErase(LTNode* pos)
    145. {
    146. 	assert(pos);
    147. 	LTNode* prev = pos->prev;
    148. 	LTNode* next = pos->next;
    149. 	prev->next = next;
    150. 	next->prev = prev;
    151. 	free(pos);
    152. 	pos = NULL;
    153. }
    154.  
    155. void ListDestroy(LTNode* phead)
    156. {
    157. 	assert(phead);
    158. 	LTNode* cur = phead->next;
    159. 	while (cur != phead)
    160. 	{
    161. 		LTNode* next = cur->next;
    162. 		free(cur);
    163. 		cur = next;
    164. 	}
    165. 	free(phead);
    166. 	phead = NULL;
    167. }

    Test.c:

    1. #include"List.h"
    2. void TestList()
    3. {
    4. 	LTNode* pList = ListInit();//创建一个哨兵头
    5. 	ListPushBack(pList, 1);//双向链表尾插
    6. 	ListPushBack(pList, 2);
    7. 	ListPushBack(pList, 3);
    8. 	ListPushBack(pList, 4);
    9. 	ListPrint(pList);//双向链表打印
    10. 	ListPopBack(pList);//双向链表尾删
    11. 	ListPopBack(pList);
    12. 	ListPrint(pList);//双向链表打印
    13. 	ListPushFront(pList, 10);//双向链表头插
    14. 	ListPushFront(pList, 20); 
    15. 	ListPushFront(pList, 30);
    16. 	ListPushFront(pList, 40);
    17. 	ListPrint(pList);//双向链表打印
    18. 	ListPopFront(pList);//双向链表头删
    19. 	ListPopFront(pList);
    20. 	ListPrint(pList);//双向链表打印
    21. 	size_t n = ListSize(pList);//统计链表中结点的个数
    22. 	printf("结点个数：%d\n", n);
    23. 	LTNode* pos = ListFind(pList, 1);//双向链表查找
    24. 	ListInsert(pos, 100);//双向链表插入
    25. 	ListPrint(pList);//双向链表打印
    26. 	LTNode* pos = ListFind(pList, 2);//双向链表查找
    27. 	ListErase(pos);//删除pos位置的结点
    28. 	ListPrint(pList);//双向链表打印
    29. 	ListDestroy(phead);//双向链表销毁
    30. }
    31. int main()
    32. {
    33. 	TestList();
    34. 	return 0;
    35. }

    四、顺序表和链表的区别

    不同点顺序表链表
    存储空间上物理上一定连续逻辑上连续，但物理上不一定
    连续
    随机访问支持O(1)不支持：O(N)
    任意位置插入或者删除
    元素    		可能需要搬移元素，效率低O(N)只需修改指针指向
    插入动态顺序表，空间不够时需要扩容没有容量的概念
    应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁
    缓存利用率高低

     本篇文章全网最细，没有更细，小编花了一周多的时间总结，麻烦给个双击，后续不断更新优质内容~

  • 相关阅读:
    如何在idea中修改包名(多图指导！超简单有效，不会报错)(maven项目)
    【flink进阶】-- Flink kubernetes operator 版本升级
    Unittest单元自动化测试框架-知识点总结
    js正则的前瞻释义
    linux 磁盘命令之du和df命令
    pytorch双线性插值
    debian的使用笔记
    第七章 查找 七、红黑树
    你有没有用代码写过暑假作业
    大数据存储解决方案：HDFS与NoSQL数据库详解
  • 原文地址：https://blog.csdn.net/lang_965/article/details/126021492