顺序表和链表(详解)

线性表

线性表（ linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

注意我们学习数据结构也就是学习增删查改，后期会围绕这四个字进行讲解，本文的讲解会把基础模拟实现部分讲的很透彻，算法oj题可以基于基础知识向外扩展，有了基础数据结构理解相信算法oj题也很好拿下了

顺序表

2.1概念及结构

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

顺序表一般可以分为：

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

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

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

接口实现

我们一般需要定义3个变量，数组，容量和实际数据数量，因为要方便后续扩容操作

下面我会把每个接口的意义讲解，这部分需要结构体和动态内存的基础，我前边讲的很详细，可以去看看每个函数都会断言，所以我们不会每个都讲，但是大家一定要明白断言的意义，一般是防止对空指针操作和检查越界

顺序表的初始化，默认先开辟一块4个整形（我们假设存储整形）的空间，size和capacity置为0。

销毁，先释放malloc的空间，将指针置空，容量和size置0

打印数据，也就是遍历这个数组很简单，用下标访问数据

检查扩容操作，当实际数据数量等于容量，要扩容，当我们插入数据时，先判断是否需要扩容，再插入，这样就能实现简易版的vector了（注意要断言是因为防止传空指针）

pos是要插入的下标，end最后一个数据下标，size是实际数据个数

插入逻辑，要记得断言下标要大于等于0并且小于等于size，下标是0相当于头插，下标是size相当于尾插，这部分一定要画图，画图以后这个插入逻辑也就是挪动覆盖，下标<size是随机插入，下标=size是尾插

删除逻辑，断言+挪动数据覆盖逻辑

 

尾插很简单，（注释的部分和没注释的是两个版本，可以用常规思路扩容+尾插，也可以直接复用插入逻辑，把参数改成最后一个下标就行）

尾删，要记得先断言检查下标，有效数据个数一定要大于0才能尾删，也可以直接复用删除逻辑

头插很简单，可以直接复用插入逻辑，参数给0就行

头删也很简单，复用删除逻辑

修改逻辑很简单，一行代码，可是为什么这一行代码也封装成一个函数呢，因为我们最好不要直接访问数组数据，缺少断言检查，用这个函数可以防止我们传越界的参数

以上就是关于顺序表实现的全部逻辑，希望能对大家有用

顺序表实现的完整代码

seqlist.h#include<stdio.h>#include<stdlib.h>#include<assert.h>// 静态顺序表//#define N 1000//typedef int SLDataType;////struct SeqList//{ //	SLDataType a[N];//	int size;//};// 动态顺序表typedef int SLDataType;typedef struct SeqList{ 	SLDataType* a;	int size;        // 存储有效数据个数	int capacity;    // 空间大小}SL;// 管理数据 -- 增删查改void SLInit(SL* ps);void SLDestroy(SL* ps);void SLPrint(SL* ps);void SLCheckCapacity(SL* ps);// 头插头删 尾插尾删void SLPushBack(SL* ps, SLDataType x);void SLPopBack(SL* ps);void SLPushFront(SL* ps, SLDataType x);void SLPopFront(SL* ps);// 返回下标，没有找打返回-1int SLFind(SL* ps, SLDataType x);// 在pos位置插入xvoid SLInsert(SL* ps, int pos, SLDataType x);// 删除pos位置的值void SLErase(SL* ps, int pos);void SLModify(SL* ps, int pos, SLDataType x);

seqlist.c

#include"seqlist.h"void SLInit(SL* ps){ 	assert(ps);	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);	if (ps->a == NULL)	{ 		perror("malloc failed");		exit(-1);		//return;	}	ps->size = 0;	ps->capacity = 4;}void SLDestroy(SL* ps){ 	assert(ps);	free(ps->a);	ps->a = NULL;	ps->capacity = ps->size = 0;}void SLPrint(SL* ps){ 	assert(ps);	for (int i = 0; i < ps->size; i++)	{ 		printf("%d ", ps->a[i]);	}	printf("\n");}void SLCheckCapacity(SL* ps){ 	assert(ps);	// 满了要扩容	if (ps->size == ps->capacity)	{ 		SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));		if (tmp == NULL)		{ 			perror("realloc failed");			exit(-1);		}		ps->a = tmp;		ps->capacity *= 2;	}}// 17:25继续void SLPushBack(SL* ps, SLDataType x){ 	assert(ps);	/*SLCheckCapacity(ps);	ps->a[ps->size] = x;	ps->size++;*/	SLInsert(ps, ps->size, x);}void SLPopBack(SL* ps){ 	assert(ps);	// 温柔的检查	//if (ps->size == 0)		//return;	// 暴力的检查	//assert(ps->size > 0);	ps->a[ps->size - 1] = 0;	//ps->size--;	SLErase(ps, ps->size - 1);}void SLPushFront(SL* ps, SLDataType x){ 	assert(ps);	//SLCheckCapacity(ps);	 挪动数据	//int end = ps->size - 1;	//while (end >= 0)	//{ 	//	ps->a[end + 1] = ps->a[end];	//	--end;	//}	//ps->a[0] = x;	//ps->size++;	SLInsert(ps, 0, x);}void SLPopFront(SL* ps){ 	assert(ps);	/*assert(ps->size > 0);	int begin = 1;	while (begin < ps->size)	{ 		ps->a[begin - 1] = ps->a[begin];		++begin;	}	ps->size--;*/	SLErase(ps, 0);}int SLFind(SL* ps, SLDataType x){ 	assert(ps);	for (int i = 0; i < ps->size; i++)	{ 		if (ps->a[i] == x)		{ 			return i;		}	}	return -1;}// 在pos位置插入xvoid SLInsert(SL* ps, int pos, SLDataType x){ 	assert(ps);	assert(pos >= 0 && pos <= ps->size);	SLCheckCapacity(ps);	int end = ps->size - 1;	while (end >= pos)	{ 		ps->a[end + 1] = ps->a[end];		--end;	}	ps->a[pos] = x;	ps->size++;}// 删除pos位置的值void SLErase(SL* ps, int pos){ 	assert(ps);	assert(pos >= 0 && pos < ps->size);	int begin = pos + 1;	while (begin < ps->size)	{ 		ps->a[begin - 1] = ps->a[begin];		++begin;	}	ps->size--;}void SLModify(SL* ps, int pos, SLDataType x){ 	assert(ps);	assert(pos >= 0 && pos < ps->size);	ps->a[pos] = x;}

还有一些测试用例，感兴趣的可以尝试运行一下，已经测试过了代码都是对的

#include<stdio.h>#include"seqlist.h"void TestSeqList1(){ 	SL sl;	SLInit(&sl);	SLPushBack(&sl, 1);	SLPushBack(&sl, 2);	SLPushBack(&sl, 3);	SLPushBack(&sl, 4);	SLPushBack(&sl, 5);	SLPushBack(&sl, 6);	SLPushBack(&sl, 6);	SLPushBack(&sl, 0);	SLPushBack(&sl, 0);	SLPrint(&sl);	SLPopBack(&sl);	SLPopBack(&sl);	SLPrint(&sl);	SLPopBack(&sl);	SLPopBack(&sl);	SLPopBack(&sl);	SLPopBack(&sl);	SLPopBack(&sl);	SLPopBack(&sl);	SLPopBack(&sl);	//SLPopBack(&sl);	//SLPopBack(&sl);	/*SLPopBack(&sl);	SLPopBack(&sl);	SLPopBack(&sl);	SLPopBack(&sl);*/	SLPrint(&sl);	SLPushBack(&sl, 1);	SLPushBack(&sl, 2);	SLPrint(&sl);	SLDestroy(&sl);}void TestSeqList2(){ 	SL sl;	SLInit(&sl);	SLPushBack(&sl, 1);	SLPushBack(&sl, 2);	SLPushBack(&sl, 3);	SLPushBack(&sl, 4);	SLPushBack(&sl, 5);	SLPrint(&sl);	SLPushFront(&sl, 10);	SLPushFront(&sl, 20);	SLPushFront(&sl, 30);	SLPushFront(&sl, 40);	SLPrint(&sl);	SLDestroy(&sl);}void TestSeqList3(){ 	SL sl;	SLInit(&sl);	SLPushBack(&sl, 1);	SLPushBack(&sl, 2);	SLPushBack(&sl, 3);	SLPushBack(&sl, 4);	SLPushBack(&sl, 5);	SLPrint(&sl);	SLPopFront(&sl);	SLPopFront(&sl);	SLPrint(&sl);	SLPopFront(&sl);	SLPopFront(&sl);	SLPopFront(&sl);	//SLPopFront(&sl);	SLPrint(&sl);	SLPushBack(&sl, 4);	SLPushBack(&sl, 5);	SLPrint(&sl);	SLDestroy(&sl);}void TestSeqList4(){ 	SL sl;	SLInit(&sl);	SLPushBack(&sl, 1);	SLPushBack(&sl, 2);	SLPushBack(&sl, 3);	SLPushBack(&sl, 4);	SLPushBack(&sl, 5);	SLPushFront(&sl, -1);	SLPushFront(&sl, -2);	SLPrint(&sl);	SLInsert(&sl, 3, 40);	SLPrint(&sl);	int x;	scanf("%d", &x);	int pos = SLFind(&sl, x);	if (pos != -1)	{ 		SLInsert(&sl, pos, x * 10);	}	SLPrint(&sl);	SLDestroy(&sl);}void TestSeqList5(){ 	SL sl;	SLInit(&sl);	SLPushBack(&sl, 1);	SLPushBack(&sl, 2);	SLPushBack(&sl, 3);	SLPushBack(&sl, 4);	SLPushBack(&sl, 5);	SLPrint(&sl);	SLErase(&sl, 2);	SLPrint(&sl);	int x;	scanf("%d", &x);	int pos = SLFind(&sl, x);	if (pos != -1)	{ 		SLErase(&sl, pos);	}	SLPrint(&sl);	SLDestroy(&sl);}void TestSeqList6(){ 	SL sl;	SLInit(&sl);	SLPushBack(&sl, 1);	SLPushBack(&sl, 2);	SLPushBack(&sl, 3);	SLPushBack(&sl, 4);	SLPushBack(&sl, 5);	SLPrint(&sl);	SLModify(&sl, 2, 20);	sl.a[2] = 20;	SLPrint(&sl);	/*int x;	scanf("%d", &x);	int pos = SLFind(&sl, x);	if (pos != -1)	{ 		SLModify(&sl, pos, x*10);	}	SLPrint(&sl);*/	int pos, x;	scanf("%d%d", &pos, &x);	//sl.a[pos] = x;	SLModify(&sl, pos, x);	SLPrint(&sl);	SLDestroy(&sl);}void TestSeqList7(){ 		SL sl;	SLInit(&sl);	SLPushBack(&sl, 1);	SLPushBack(&sl, 2);	SLPushBack(&sl, 3);	SLPushBack(&sl, 4);	SLPushBack(&sl, 5);	SLPrint(&sl);	SLPopFront(&sl);	SLDestroy(&sl);}int main(){ 	TestSeqList1();	return 0;}

相关oj题

27. 移除元素 - 力扣（LeetCode）

26. 删除有序数组中的重复项 - 力扣（LeetCode）

88. 合并两个有序数组 - 力扣（LeetCode）

顺序表的讲解基本结束，还有顺序表和链表的对比，在STL我已经写过了，可以看看是一个道理

链表

链表的概念及结构

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

现实中链表存放的都是malloc出来的地址，是随机值，但是也不排除会有这种很规律的取值

我们要注意单链表是没有哨兵位，且只有一个next后继指针，头指针存放第一个节点的地址，后边的内存块如图所示，每个内存块存放有下一个内存块的地址，最后一个内存块存放NULL（这个是规则）

链表的分类

别看有这么多种链表，其实实际常用的也就是单链表和双向带头循环链表

其实学会这两种链表就行，单链表适合做oj题，双向链表适合存储数据

带头双向循环链表由哨兵位，哨兵位可以理解为不存有效数据的第一个头结点，遍历只会遍历有效数据结点，只有一个哨兵位等价于链表为NULL

单链表没有哨兵位头结点，只有头指针，所以我们要控制头指针一直指向第一个节点，就要用二级指针进行管理

单链表的实现

注意单链表部分一定要学会传二级指针，因为我们要改变结构体指针的内容（当链表为空），因为没有哨兵位，只有一个头指针，后边的带头双向循环链表由哨兵位的头结点，就不用传二级指针了(单链表的增删查改的情况有些多，大致分为链表为空或者链表非空来讨论)

链表内部存储两个数据，一个是值x，一个是结构体指针*next（用来存放下一个结点的地址）

打印操作,参数是结构体变量的地址，拿到数据向后遍历，最后一个数据next为空，停下来

这个函数用来申请一个新节点的空间，并且初始化为NULL和x，类似c++的new

尾插操作，参数要传二级指针（也就是头结点指针的地址，这样在链表第一个节点为空的时候可以直接尾插）

链表不为空，要多定义一个尾指针，遍历链表到最后一个，将NULL改为新new处结点的地址，就完成链表的插入了（道理很简单，实在没想明白可以画图，数据结构部分就是要多画图才能学好）

头删很简单，先断言plist不能是NULL，空链表没必要删除了

先保存要删除结点的下一个结点地址，然后再free掉要删除的节点，并且让头指针指向新的首结点

尾删结点，是空链表或者只有一个结点的链表很简单，当两个以上的时候定义一个前驱指针tailprev，遍历链表，当tail的next是NULL的时候，跳出循环并且free掉尾指针指向的结点，将前驱指针的next置空，这样就完成了尾删很简单

头插很简单，先new（并不是c++的new，只是我想这样写）一个新节点，将新节点的next存放第一个结点的地址，plist存放新节点的地址，就完成头插

查询某个值，很简单遍历一下，找到就返回下标，没找到就返回NULL

在pos位置之前插入，如果我们要在第一个结点前插入，直接复用头插逻辑，其他情况我们要定义一个前驱指针prev，用来指向pos位置之前的结点，当prev指向要插入位置之前结点的时候，跳出循环，链接数据。很简单

删除pos位置的值，和插入逻辑相似，删除第一个节点直接复用头删逻辑，其他情况（因为要删除后边的某个节点）定义一个前驱指针保存删除节点前一个位置，当prev指向pos之前的结点时，链接要删除节点左右节点，删除pos结点并且置空（也可以不置空，因为栈帧到此会销毁结束，我们也访问不到了）

以上就是我对单链表的理解，希望能帮到大家

单链表完整源码

#include<stdio.h>#include<stdlib.h>#include<assert.h>typedef int SLTDataType;typedef struct SListNode{ 	SLTDataType data;	struct SListNode* next;}SLTNode;void SLTPrint(SLTNode* phead);SLTNode* BuySListNode(SLTDataType x);void SLTPushBack(SLTNode** pphead, SLTDataType x);//SLTNode* SLTPushBack(SLTNode* phead, SLTDataType x);void SLTPushFront(SLTNode** pphead, SLTDataType x);void SLTPopBack(SLTNode** pphead);void SLTPopFront(SLTNode** pphead);SLTNode* SLTFind(SLTNode* phead, SLTDataType x);// 在pos之前插入xvoid SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);// 删除pos位置void SLTErase(SLTNode** pphead, SLTNode* pos);

#include"slist.h"void SLTPrint(SLTNode* phead){ 	SLTNode* cur = phead;	//while (cur != NULL)	while (cur)	{ 		printf("%d->", cur->data);		cur = cur->next;	}	printf("NULL\n");}SLTNode* BuySListNode(SLTDataType x){ 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));	if (newnode == NULL)	{ 		perror("malloc fail");		exit(-1);	}	newnode->data = x;	newnode->next = NULL;	return newnode;}// 16:07继续void SLTPushBack(SLTNode** pphead, SLTDataType x){ 	assert(pphead);	SLTNode* newnode = BuySListNode(x);	if (*pphead == NULL)	{ 		// 改变的结构体的指针，所以要用二级指针		*pphead = newnode;	}	else	{ 		SLTNode* tail = *pphead;		while (tail->next != NULL)		{ 			tail = tail->next;		}		// 改变的结构体，用结构体的指针即可		tail->next = newnode;	}}void SLTPushFront(SLTNode** pphead, SLTDataType x){ 	assert(pphead);	SLTNode* newnode = BuySListNode(x);	newnode->next = *pphead;	*pphead = newnode;}void SLTPopBack(SLTNode** pphead){ 	assert(pphead);	// 1、空	assert(*pphead);	// 2、一个节点	// 3、一个以上节点	if ((*pphead)->next == NULL)	{ 		free(*pphead);		*pphead = NULL;	}	else	{ 				SLTNode* tailPrev = NULL;		SLTNode* tail = *pphead;		while (tail->next)		{ 			tailPrev = tail;			tail = tail->next;		}		free(tail);		//tail = NULL;		tailPrev->next = NULL;	}}void SLTPopFront(SLTNode** pphead){ 	assert(pphead);	// 空	assert(*pphead);	// 非空	SLTNode* newhead = (*pphead)->next;	free(*pphead);	*pphead = newhead;}SLTNode* SLTFind(SLTNode* phead, SLTDataType x){ 	SLTNode* cur = phead;	while (cur)	{ 		if (cur->data == x)		{ 			return cur;		}		cur = cur->next;	}	return NULL;}void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){ 	assert(pphead);	assert(pos);	if (pos == *pphead)	{ 		SLTPushFront(pphead, x);	}	else	{ 		SLTNode* prev = *pphead;		while (prev->next != pos)		{ 			prev = prev->next;		}		SLTNode* newnode = BuySListNode(x);		prev->next = newnode;		newnode->next = pos;	}}// 删除pos位置void SLTErase(SLTNode** pphead, SLTNode* pos){ 	assert(pphead);	assert(pos);	if (pos == *pphead)	{ 		SLTPopFront(pphead);	}	else	{ 		SLTNode* prev = *pphead;		while (prev->next != pos)		{ 			prev = prev->next;		}		prev->next = pos->next;		free(pos);		//pos = NULL;	}}

#define _CRT_SECURE_NO_WARNINGS 1#include"slist.h"void TestSList1(){ 	int n;	printf("请输入链表的长度：");	scanf("%d", &n);	printf("\n请依次输入每个节点的值:");	SLTNode* plist = NULL;	for (size_t i = 0; i < n; i++)	{ 		int val;		scanf("%d", &val);		SLTNode* newnode = BuySListNode(val);		// 头插		newnode->next = plist;		plist = newnode;	}	SLTPrint(plist);	SLTPushBack(&plist, 10000);	SLTPrint(plist);}void TestSList2(){ 	SLTNode* plist = NULL;	SLTPushBack(&plist, 1);	SLTPushBack(&plist, 2);	SLTPushBack(&plist, 3);	SLTPushBack(&plist, 4);	SLTPushBack(&plist, 5);	SLTPrint(plist);	SLTPushFront(&plist, 10);	SLTPushFront(&plist, 20);	SLTPushFront(&plist, 30);	SLTPushFront(&plist, 40);	SLTPrint(plist);}void TestSList3(){ 	SLTNode* plist = NULL;	SLTPushBack(&plist, 1);	SLTPushBack(&plist, 2);	SLTPushBack(&plist, 3);	SLTPushBack(&plist, 4);	SLTPushBack(&plist, 5);	SLTPrint(plist);	SLTPopBack(&plist);	SLTPrint(plist);	SLTPopBack(&plist);	SLTPrint(plist);	SLTPopBack(&plist);	SLTPrint(plist);	SLTPopBack(&plist);	SLTPrint(plist);	SLTPopBack(&plist);	SLTPrint(plist);	// SLTPopBack(&plist);	// SLTPrint(plist);}void TestSList4(){ 	SLTNode* plist = NULL;	SLTPushBack(&plist, 1);	SLTPushBack(&plist, 2);	SLTPushBack(&plist, 3);	SLTPushBack(&plist, 4);	SLTPushBack(&plist, 5);	SLTPrint(plist);	SLTPopFront(&plist);	SLTPrint(plist);	SLTPopFront(&plist);	SLTPrint(plist);	SLTPopFront(&plist);	SLTPrint(plist);	SLTPopFront(&plist);	SLTPrint(plist);	SLTPopFront(&plist);	//SLTPopFront(&plist);	SLTPrint(plist);}void TestSList5(){ 	SLTNode* plist = NULL;	SLTPushBack(&plist, 1);	SLTPushBack(&plist, 2);	SLTPushBack(&plist, 3);	SLTPushBack(&plist, 4);	SLTPushBack(&plist, 5);	SLTPrint(plist);	SLTNode* pos = SLTFind(plist, 40);	if (pos)	{ 		pos->data *= 10;	}	SLTPrint(plist);	int x;	scanf("%d", &x);	pos = SLTFind(plist, x);	if (pos)	{ 		SLTInsert(&plist, pos, x * 10);	}	SLTPrint(plist);}int main(){ 	TestSList1();	return 0;}

双向链表的实现

带头双向循环链表，有前驱指针，后继指针和数据

最基础的申请新结点空间，赋值并且置空，后期new的雏形，申请空间+初始化都干了

这个是哨兵位头结点，会返回给外边的plist用来控制增删查改逻辑

打印逻辑，遍历链表并且打印值

在某个位置之前插入

pos之前插入很简单，定义一个posprev前驱指针，将newnode链接上去

牛逼的地方是，传哨兵位的下一个节点也就是头结点的指针，就成为头插了；传哨兵位指针，完成尾插，因为哨兵位的前一个节点就是整个链表最后一个数据

尾删

头删

删除逻辑很简单将要删除结点的前结点和后结点保存，删除pos位置节点，然后链接左右节点

尾插直接复用插入逻辑，传哨兵位指针过去就行，完成尾插，当然也可以自己实现，但是建议直接复用，节省代码

头插也就是在哨兵位下一个之前插入，直接复用

尾部删除，注意要断言（，当只有哨兵位结点时不能删除，此时有效数据为0），直接复用删除逻辑

头删直接复用删除逻辑，删除哨兵位下一个结点就是头删

最后还有一个求有效数据个数的代码，很简单，遍历链表到哨兵位结束也就是计算了有效数据（除哨兵位）

以上就是我对双向链表的理解，很透彻希望对大家有用

双向链表模拟实现完整代码

#include"List.h"LTNode* BuyLTNode(LTDataType x){ 	LTNode* node = (LTNode*)malloc(sizeof(LTNode));	if (node == NULL)	{ 		perror("malloc fail");		exit(-1);	}	node->data = x;	node->next = NULL;	node->prev = NULL;	return node;}LTNode* LTInit(){ 	LTNode* phead = BuyLTNode(0);	phead->next = phead;	phead->prev = phead;	return phead;}void LTPrint(LTNode* phead){ 	assert(phead);	printf("phead<=>");	LTNode* cur = phead->next;	while (cur != phead)	{ 		printf("%d<=>", cur->data);		cur = cur->next;	}	printf("\n");}void LTPushBack(LTNode* phead, LTDataType x){ 	assert(phead);	LTInsert(phead, x);}void LTPopBack(LTNode* phead){ 	assert(phead);	assert(phead->next != phead);	LTErase(phead->prev);}void LTPushFront(LTNode* phead, LTDataType x){ 	assert(phead);	LTInsert(phead->next, x);}void LTPopFront(LTNode* phead){ 	assert(phead);	assert(phead->next != phead);	LTErase(phead->next);}int LTSize(LTNode* phead){ 	assert(phead);	int size = 0;	LTNode* cur = phead->next;	while (cur != phead)	{ 		++size;		cur = cur->next;	}	return size;}// pos֮ǰxvoid LTInsert(LTNode* pos, LTDataType x){ 	assert(pos);	LTNode* posPrev = pos->prev;	LTNode* newnode = BuyLTNode(x);	posPrev->next = newnode;	newnode->prev = posPrev;	newnode->next = pos;	pos->prev = newnode;}// ɾposλvoid LTErase(LTNode* pos){ 	assert(pos);	LTNode* posPrev = pos->prev;	LTNode* posNext = pos->next;	free(pos);	posPrev->next = posNext;	posNext->prev = posPrev;}

#include<stdio.h>#include<stdlib.h>#include<assert.h>typedef int LTDataType;typedef struct ListNode{ 	struct ListNode* next;	struct ListNode* prev;	LTDataType data;}LTNode;LTNode* BuyLTNode(LTDataType x);LTNode* LTInit();void LTPrint(LTNode* phead);void LTPushBack(LTNode* phead, LTDataType x);void LTPopBack(LTNode* phead);void LTPushFront(LTNode* phead, LTDataType x);void LTPopFront(LTNode* phead);int LTSize(LTNode* phead);LTNode* LTFind(LTNode* phead, LTDataType x);// pos֮ǰxvoid LTInsert(LTNode* pos, LTDataType x);// ɾposλvoid LTErase(LTNode* pos);

#include"List.h"void TestList1(){ 	LTNode* plist = LTInit();	LTPushBack(plist, 1);	LTPushBack(plist, 2);	LTPushBack(plist, 3);	LTPushBack(plist, 4);	LTPushBack(plist, 5);	LTPrint(plist);	LTPushFront(plist, 10);	LTPushBack(plist, 10);	LTPrint(plist);}void TestList2(){ 	LTNode* plist = LTInit();	LTPushBack(plist, 1);	LTPushBack(plist, 2);	LTPushBack(plist, 3);	LTPushBack(plist, 4);	LTPushBack(plist, 5);	LTPrint(plist);	LTPopBack(plist);	LTPopFront(plist);	LTPrint(plist);	LTPopFront(plist);	LTPopFront(plist);	LTPopFront(plist);	//LTPopFront(plist);	LTPrint(plist);}void TestList3(){ 	LTNode* plist = LTInit();	LTPushBack(plist, 1);	LTPushBack(plist, 2);	LTPushBack(plist, 3);	LTPushBack(plist, 4);	LTPushBack(plist, 5);	LTPrint(plist);	LTPushFront(plist, 10);	LTPushFront(plist, 20);	LTPushFront(plist, 30);	LTPushFront(plist, 40);	LTPrint(plist);}void TestList4(){ 	LTNode* plist = LTInit();	LTPushBack(plist, 1);	LTPushBack(plist, 2);	LTPushBack(plist, 3);	LTPushBack(plist, 4);	LTPushBack(plist, 5);	LTPrint(plist);	LTPopFront(plist);	LTPrint(plist);	LTPopBack(plist);	LTPrint(plist);}int main(){ 	TestList4();	return 0;}

链表面试oj题

203. 移除链表元素 - 力扣（LeetCode）

206. 反转链表 - 力扣（LeetCode）

876. 链表的中间结点 - 力扣（LeetCode）

21. 合并两个有序链表 - 力扣（LeetCode）

链表分割_牛客题霸_牛客网

链表的回文结构_牛客题霸_牛客网

160. 相交链表 - 力扣（LeetCode）

141. 环形链表 - 力扣（LeetCode）

142. 环形链表 II - 力扣（LeetCode）

138. 随机链表的复制 - 力扣（LeetCode）

题目有点多，都是经典链表的题，可以研究一下（有了基础内容的讲解，算法题可以尝试完成）

顺序表和链表的区别

打对钩的是优点，错误是缺点，可以了解一下，因为各有各的优势，在不同场景要用不同的数据结构

以上就是我对数据结构链表和顺序表的全部理解，以后会创作更多用心作品(目录有对应的模块，需要什么看什么)

感谢大家的支持！！！