横看成岭侧成峰，远近高低各不同。                          ——苏轼《题西林壁》

---

“你有没有遇到过插入数据时数组移动太慢？或者链表访问数据像‘寻宝’一样慢？”

不同的数据结构影响程序性能，如何选择？

底搞懂顺序表和链表的区别，学会如何选择

一.了解线性表

• 线性表是n个具有相同特性的数据元素的有限序列
• 线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

根据线性表的概念我们可以得知，顺序表与链表都是线性表的一种。

二.顺序表详解 

2.1什么是顺序表

顺序表（Sequential List）是一种线性表的实现方式，它使用一段连续的物理内存来存储数据元素，逻辑上相邻的元素在内存中也相邻。

顺序表的特点

1. 基于数组：底层通常用数组实现，支持随机访问（通过下标直接访问元素，时间复杂度 O(1)）。

2. 内存连续：所有元素存储在连续的内存空间，类似于排队占位，不能“插队”导致中间有空隙。

简单来说顺序表的实现是在数组的基础上，因此他的特点也与数组一致.
两者主要的区别是：顺序表对数组进行了封装，并增加了增删减改查等功能.

2.2顺序表的分类

        （1）静态顺序表

                静态顺序表是使用定长数组来存储数据，基本结构为        

struct SeqList{
    int arr[10];//数组的类型可以是任何类型，由要求决定
    //大小是固定的
    int size;//有效的数据个数
}

 这里不做过多讲述了解即可，因为在绝大多数的情况下，静态顺序表的实际意义不大，存储的数据很多时候是不固定的.

        （2）动态顺序表

                动态顺序表与静态顺序表最大的不同是按需申请，动态顺序表可以根据其需要的大小，从而申请其大小

struct SeqList{
    int* a;
    int size; //a中有多少元素
    int capacity;//a的容量大小
}

 

2.3顺序表的基本功能 

在c语言中其功能需要自己手动完成，核心功能为以下几个

//初始化
void SqLinit(SL* p);

//销毁
void SqlDestory(SL* p);

//打印
void sqlprint(SL p);
//扩容
void sqlreal(SL* p);

//增加
void Sqlpushback(SL* p, SqlDataType x);//尾插
void Sqlpushfront(SL* p, SqlDataType x);//头插

//删除
void sqlDelback(SL* p);//尾删
void sqlDelfront(SL* p);//头删

//指定位置插入数据
void SLInsert(SL* ps, int pos, SqlDataType x);

//在指定位置删除数据
void SLErase(SL* ps, int pos);

//查找
int SLFind(SL* ps, SqlDataType x);

可以试着自己完成一下，相关代码放在了结尾 

2.4顺序表的优缺点 

优点：

• 访问速度快（可以通过下标快速访问到相关数据）
• 内存缓冲利用率高
• 实现简单

缺点：

• 扩容时容易造成浪费（当调整capacity的大小时，可能会重新分配内存）
• 插入/删除元素速度慢(需要移动元素) 

优点中的内存缓冲利用率高，是因为内存进入缓冲区后，会将相邻的地址的内容也同时放入缓冲区中（当CPU访问内存中的一个元素时，会将该元素所在的整个缓存行（通常64字节）一起加载到缓存中），因为顺序表的内存是连续的，因此进入缓冲区的内容都是顺序表的有效内容,从而使缓冲区利用率变高. 

• 命中缓存：访问耗时约 1~3 个时钟周期。

• 未命中缓存：需从主存加载，耗时约 100~300 个时钟周期。

三.链表详解

3.1什么是链表

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

特点：

• 非连续存储，通过指针（或引用）连接节点。

• 不支持随机访问，必须从头遍历.

 大致内存的存储情况如上图，链表在逻辑上是连续的，但在实际的内存中并不是连续的.

3.2链表的分类

链表的种类有很多，如下图

组成2*2*2=8种方式的链表，上方所画的图为不带头单向不循环链表，接下来的图分别为其他几种类型的大致图

（1）不带头单向循环链表

最后一个链表的节点可以找到第一个链表的节点

（2）不带头双向不循环链表

可以通过下一个链表的节点找到上一个链表的节点

（3）不带头双向循环链表

在看带头链表前我们先看一下，带头中这个“头是什么”，

带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨的，哨兵位实际上与后方节点相同，只不过哨兵位不存储数据.
它的存在意义是什么：

遍历循环链表避免死循环

（4）带头单向循环链表

（5）带头单向不循环链表

（6）带头双向循环链表

（7）带头双向不循环链表

总结其类型：

虽然上面有着很多类型，但是实际的结构体类型只有两个

第一种是单向链表的结构体类型

struct SListNode{
    int val;//可以是其他类型也可以有包含多个数据
    struct SListNode* next;//获得下一个节点的地址，从而可以找到下一个节点的位置
}

第二种是双向链表的结构体类型

struct SListNode{
    int val;//可以是其他类型也可以有包含多个数据
    struct SListNode* next;//获得下一个节点的地址，从而可以找到下一个节点的位置
    struct SListNode* prev;//获取上一个节点的地址，从而可以找到上一个节点的位置
}

3.3.单向链表的基本功能

        

 同理，代码也放在结尾

3.4双向链表的基本功能

 3.5链表的优缺点

优点：

• 插入删除快（只需修改指针）
• 动态扩展，无扩容问题.

缺点：

• 访问慢（必须通过遍历，不能像顺序表一样，通过下标直接找到值）
• 内存开销大（需存储指针）
• 缓存利用率低

4.顺序表与链表的对比

5.总结

• 顺序表：适合读取多、数据固定的场景。

• 链表：适合频繁增删、动态数据的场景。

6.代码 

1.顺序表部分代码

//初始化
void SqLinit(SL* p)
{
	p->arr = NULL;
	p->size = p->capacity = 0;
}

//销毁
void SqlDestory(SL* p)
{
	if (p->arr)
	{
		free(p->arr);
	}
	p->capacity = p->size = 0;
}
//打印
void sqlprint(SL p)
{
	for (int i = 0;i < p.size;i++)
	{
		printf("%d ", p.arr[i]);
	}
	printf("\n");
}
//扩容
void sqlreal(SL* p)
{
	if (p->size == p->capacity)
	{
		int a = 0;
		a = p->capacity == 0 ? 4 : 2 * p->capacity;
		SqlDataType* tmp = (SqlDataType*)realloc(p->arr, sizeof(SqlDataType) * a);
		//realloc 函数有一个特殊的行为：当传入的指针是 NULL 时，realloc 的行为会等同于 malloc
		if (tmp == NULL)
		{
			perror("realloc failed!");
			exit(1);
		}
		p->arr = tmp;
		p->capacity = a;
	}
}
//增加

//尾插
void Sqlpushback(SL* p, SqlDataType x)
{
	sqlreal(p);
	p->arr[p->size++] = x;
}

//头插
void Sqlpushfront(SL* p, SqlDataType x)
{
	sqlreal(p);
	for (int i = p->size;i>0;i--)
	{
		p->arr[i] = p->arr[i-1];
	}
	p->arr[0] = x;
	p->size++;
}

//指定位置插入
void SLInsert(SL* ps, int pos, SqlDataType x)
{
	assert(ps);
	sqlreal(ps);
	if (pos<0 || pos>ps->size)
	{
		printf("无法插入\n");
		exit(1);
	}
	for (int i = ps->size;i > pos;i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

//删除

//指定位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	if (pos >= ps->size || pos < 0)
	{
		exit(1);
	}
	for (int i = pos;i < ps->size-1;i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//尾删
void sqlDelback(SL* p)
{
	assert(p);
	assert(p->size);
	p->size--;
}

//头删
void sqlDelfront(SL* p)
{
	assert(p);
	assert(p->size);
	memmove(p->arr,p->arr+1,(p->size-1)*sizeof(SqlDataType));
	p->size--;
}

//查找
int SLFind(SL* ps, SqlDataType x)
{
	int i = 0;
	for (i;i < ps->size;i++)
	{
		if (ps->arr[i] == x)
		{
			return  i;//返回找到的下标
		}
	}
	return -1;//没找到
}

2.单向链表部分的代码

//打印
void SLNDataPrint(SLN* phead)
{
	SLN* pl = phead;
	while (pl)
	{
		printf("%d->",pl->Data);
		pl = pl->Next;
	}
	printf("NULL\n");
}
//创建新节点
SLN* NewNode(DataType x)
{
	 SLN* node = (SLN*)malloc(sizeof(SLN));
	 if (node == NULL)
	 {
		 perror("malloc");
		 exit(1);
	 }
	 node->Data = x;
	 node->Next = NULL;
	 return node;
}

//尾插
void SLNDataPushBack(SLN** pphead, DataType x)//传的为&node1
{
	assert(pphead);
	SLN* node = NewNode(x);
	if (*pphead == NULL)
	{
		*pphead = node;
	}
	else
	{
		SLN* ptail = *pphead;
		while(ptail->Next)
		{
			ptail=ptail->Next;
		}
		ptail->Next=node;
	}
}
//头插
void SLNDataPushFront(SLN** pphead, DataType x)
{
	assert(pphead);
	SLN* node=NewNode(x);
	node->Next = *pphead;
	*pphead = node;
}
//尾删
void SLNDataDelback(SLN** pphead)
{
	assert(pphead && (*pphead));
	if ((*pphead)->Next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else {
		SLN* phead = *pphead;
		SLN* pre = phead;
		while (phead->Next)
		{
			pre = phead;
			phead = phead->Next;
		}
		free(phead);
		phead = NULL;
		pre->Next = NULL;
	}
}
//头删
void SLNDataDelFront(SLN** pphead)
{
	assert(pphead&&*pphead);

		SLN* phead = *pphead;
		*pphead = (*pphead)->Next;
		free(phead);
		phead = NULL;
	
}
//查找
SLN* SLTFind(SLN* phead,DataType x)
{
		while(phead)
		{
			if (phead->Data==x)
			{	
				return phead;
			}
			phead = phead->Next;
		}
		printf("没有这个数据\n");
		return NULL;
}
//删除pos节点
void SLNErase(SLN** pphead, SLN* pos)
{
	assert(pphead&&pos&&(*pphead));
		SLN* pre = *pphead;
		SLN* phead = *pphead;
		while (phead)
		{
			if (phead == pos)
			{
				phead = phead->Next;
				free(pos);
				pos = NULL;
				pre->Next = phead;

				printf("成功删除\n");
				return;
			}
			pre = phead;
			phead = phead->Next;
		}
		printf("没有该数据\n");
}

//删除pos节点
void SLNErase(SLN** pphead, SLN* pos)
{
	assert(pphead && (*pphead) && pos);
	if (pos == *pphead)
	{
		//*pphead = pos->Next;
		//free(pos);
		SLNDataDelFront(pphead);
	}
	else
	{
		SLN* next = pos->Next;
		SLN* prev = *pphead;
		while (prev->Next != pos)
		{
			prev = prev->Next;
		}
		free(pos);
		prev->Next = next;
	}
}
//在指定位置之前插入数据
void SLNInsert(SLN** pphead, SLN* pos, DataType x)
{
	assert(pphead&&*pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLNDataPushFront(pphead, x);
	}
	else
	{
		SLN* newnode = NewNode(x);
		SLN* pf = *pphead;
		while (pf->Next != pos)
		{
			pf = pf->Next;
		}
		pf->Next = newnode;
		newnode->Next = pos;
	}
}
//在指定位置之后插入数据
void SLTInsertAfter(SLN* pos, DataType x)
{
	assert(pos);
	SLN* node = NewNode(x);
	SLN* p = pos->Next;
	pos->Next = node;
	node->Next = p;
}
//删除指定位置之后的所有节点
void SLTEraseAfter(SLN* pos)
{
	assert(pos);
	SLN* phead = pos->Next;
	SLN* PN = pos->Next;
	while (phead)
	{
		PN = phead;
		phead = phead->Next;
		free(PN);
	}
	PN = NULL;
	pos->Next = NULL;
}
//删除指定位置之后的节点
void SLTEraseOneAfter(SLN* pos)
{
	assert(pos&&pos->Next);
	SLN* del = pos->Next;
	pos->Next = pos->Next->Next;
	free(del);
	del = NULL;
}
//销毁链表
void SListDesTroy(SLN** pphead)
{
	assert(pphead);
	SLN* phead = *pphead;
	SLN* pre = *pphead;
	while (phead)
	{
		pre = phead;
		phead = phead->Next;
		free(pre);
	}
	pre = NULL;
	phead = NULL;
	*pphead = NULL;
}

3.双向链表部分的代码

void LNInit(ListNode** phead)
{
	assert(phead);
	*phead = LNBuyNode(-1);
}
//创建新节点
ListNode* LNBuyNode(LNDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->next = newnode;
	newnode->prev = newnode;
	newnode->data = x;
	return newnode;
}

//初始化
ListNode* LNInit2()
{
	ListNode* phead = LNBuyNode(-1);
	return phead;
}
//打印
void LNPrint(ListNode* phead)
{

	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->",pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
//尾插
void LNPushBack(ListNode* phead, LNDataType x)
{
	assert(phead);//双向链表要有头节点
	ListNode*newnode1=LNBuyNode(x);
	newnode1->next = phead;
	newnode1->prev = phead->prev;

	phead->prev->next = newnode1;
	phead->prev = newnode1;
}
//头插 
void LNPushFront(ListNode* phead, LNDataType x)
{
	assert(phead);
	ListNode* newnode = LNBuyNode(x);
	newnode->next = phead->next;
	newnode->prev =phead ;

	phead->next->prev = newnode;
	phead->next = newnode;
}
//尾删
void LNPopBack(ListNode* phead)
{
	assert(phead&&phead->next!=phead);//头节点不能被删除
	ListNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
}
//头删
void LNPopFront(ListNode* phead)
{
	assert(phead && phead->next != phead);
	ListNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}
//查找
ListNode* LNFind(ListNode* phead, LNDataType x)
{
	assert(phead);
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data==x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//在指定位置之后插入数据
void LNInsert(ListNode* pos, LNDataType x)
{
	assert(pos);
	ListNode* newnode = LNBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}
//删除指定节点
void LNDel(ListNode* pos)
{
	assert(pos);//此外pos不能为phead，头节点不能被删除或者更改，因为此处没有传头节点，因此不做检验
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}
//销毁
void LNDestory(ListNode* phead)
{
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		ListNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}