数据结构修炼——顺序表和链表的区别与联系

一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上，或者说实际的数据存储中，并不一定是连续的，线性表中的元素在物理存储时，通常以数组或链式结构的形式存储。

二、顺序表

2.1 概念及结构

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

顺序表一般可以分为静态顺序表与动态顺序表。
静态顺序表：使用定长数组存储数据元素。
动态顺序表：使用动态开辟的数组存储数据元素。

例如：

//静态顺序表的实现
#define CAPACITY 10//宏定义数组长度 CAPACITY
typedef int SLDataType//数组元素类型重命名为 SLDataType
typedef struct SeqList
{SLDataType array[NUMSSIZE];//定长数组size_t size;//有效数据的个数
}SeqList;

首先是宏定义#define，为了方便统一修改与重定义定长数组的长度，通常会使用宏定义一个变量作为数组长度，这样变量就可以用来定义数组长度了。相似的，为了方便统一修改与重定义数组元素的类型，通常会使用typedef将数组元素类型重命名为SLDataType。其次是在顺序表的结构体定义中，通常除了数组这个结构体成员外，还有一个size_t类型的结构体成员用于记录数组的有效元素个数，同时也记录了数组最后一个元素的下标即有效数据个数减1。

//动态顺序表的实现
typedef int SLDataType//数组元素类型重命名为SLDataType
typedef struct SeqList
{SLDataType* array;//指向动态数组地址的指针size_t size;//有效数据个数size_t capacity;//动态数组最大容量空间的大小
}SeqList;

与静态顺序表一样，为了方便修改动态数组元素类型，对数组元素类型进行了重命名。在顺序表的结构体内部，动态顺序表定义了一个数组元素类型的指针来指向数组所在空间（在C语言修炼的指针篇中，我们详细介绍过了数组与指针本质上的联系——传送门）。动态顺序表相较静态顺序表增加了一个变量，用于记录动态开辟出来的数组大小/容量，毕竟调用相关函数开辟空间也是有时间空间上的消耗的，所以不可能存储一个就开辟一个，而是按一定规律提前开辟好空间与扩容。

2.2 接口实现

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

动态顺序表增删查改的实现：

typedef int SLDataType;//根据需要修改数组元素类型
typedef struct SeqList
{SLDataType* arr;size_t size;//有效数据个数size_t capacity;//空间容量
}SL;//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
//数组空间扩容
void SLCheckCapacity(SL* ps);
//顺序表打印
void SLPrint(SL s);
//头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
//删除指定位置的数据
void SLErase(SL* ps, int pos);
//查找顺序表中的数据
SLDataType SLFind(SL s, SLDataType x);

后面需要用到的头文件有：

#include<stdio.h>
#include<assert.h>//提供assert断言函数，帮助判断指针是否为空或数据是否有效
#include<stdlib.h>//提供free，realloc函数

顺序表的初始化与销毁：
当我们定义了顺序表的结构体后，我们就可以定义结构体变量了，一个结构体变量SL s代表一个顺序表。但定义了变量后，还需要进行顺序表的初始化。顺序表不用之后也需要销毁并释放动态开辟的空间。
代码示例如下：

void SLInit(SL* ps)//顺序表初始化
{assert(ps);//对 ps 指针判空//顺序表结构体变量的成员变量初始化ps->arr = NULL;ps->capacity = ps->size = 0;
}
void SLDestroy(SL* ps)//顺序表销毁
{assert(ps);if (ps->arr)//判断arr数组是否开辟了空间{free(ps->arr);//释放所开辟空间，防止内存泄漏}ps->arr = NULL;ps->capacity = ps->size = 0;
}

一定要注意函数的参数问题，首先传递过来的一定是顺序表变量SL s的地址，传值调用是无法改变实参——顺序表变量的，只有传址调用才能改变实参的值。其次是对传递过来的指针参数SL* ps进行判空，空指针是无法解引用访问的。
在顺序表的销毁中，需要注意对程序申请的空间进行释放，程序在关闭时会主动进行内存空间的释放，但如果程序一直不结束，就会造成内存泄漏问题。

数组空间的扩容：
动态顺序表的重点就是动态的空间分配，因此扩容函数的实现非常关键。
代码如下：

void SLCheckCapacity(SL* ps)//检查空间容量与扩容
{assert(ps);//判空if (ps->size == ps->capacity)//判断数组大小是否等于容量{//数组大小等于空间容量，则空间不足，直接扩容int newCapacity = ps->capacity == 0 ? 4: 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//重新申请空间if (!tmp)//判断空间是否申请成功{//申请失败，报错并退出程序perror("realloc fail!");exit(1);//直接退出程序}//空间申请成功ps->arr = tmp;//更新arr指针ps->capacity = newCapacity;//更新空间容量}
}

扩容要注意的是一定不能直接用内存函数realloc对原数组空间进行调整，因为存在空间申请失败的可能，所以需要先判断是否申请空间成功，再将有效的新空间给数组。
在扩容数量的选择上，通常按二倍二倍的扩容，经过数学统计与分析这是最高效且节省资源的扩容方式。但我们不能直接int newCapacity = 2 * ps->capacity;，因为在顺序表的初始化中空间容量的初始值是0，而0乘以任何数为0，所以这里取巧使用了一个三目操作符ps->capacity == 0? 4: 2 * ps->capacity，如果ps->capacity为0则返回4，如果不为0则返回它的2倍，三目操作符的返回值又赋值给了newCapacity。

头删尾删，头插尾插：
数据的头删头插，即删除数组的第一个元素或在所有元素之前插入数据。尾删尾插同理，删除数组的最后一个有效元素或在所有元素之后插入数据。
代码示例如下：

void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);//判空SLCheckCapacity(ps);//检查空间容量ps->arr[ps->size++] = x;//从后面插入数据
}
void SLPushFront(SL* ps, SLDataType x)//头插
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size; i > 0; i--)//当前有效元素整体后移一位{ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;//头插赋值ps->size++;//更新有效数据个数
}
void SLPopBack(SL* ps)//尾删
{assert(ps);assert(ps->size);//判断元素有效个数是否为0，为0报错警告ps->size--;//元素有效个数不为0，直接有效元素个数减1即可
}
void SLPopFront(SL* ps)//头删
{assert(ps);for (int i = 0; i < ps->size - 1; i++){//除了第一个有效元素，后面元素整体前移一位覆盖第一个元素ps->arr[i] = ps->arr[i + 1];}ps->size--;//有效元素个数减1
}

指定位置插入新数据：

void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//确保pos坐标合法SLCheckCapacity(ps);for (int i = ps->size; i > pos; i--){//从下标pos这个位置到最后一个有效元素整体后移一位，空出pos位置ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;//赋值插入数据ps->size++;//有效元素个数加1
}

删除指定位置的数据：

void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);for (int i = pos; i < ps->size - 1; i++){//pos后的元素整体前移一位覆盖pos位置ps->arr[i] = ps->arr[i + 1];}ps->size--;//有效元素个数减1
}

查找指定数据的位置：
查找数据只需要返回数据的位置信息即可，不需要改变顺序表信息，所以顺序表变量的传参为传值调用即可。

SLDataType SLFind(SL s, SLDataType x)
{for (int i = 0; i < s.size; i++)//遍历数组{if (s.arr[i] == x)//找到第一个指定数据直接返回{return i;}}return -1;//遍历完数组未找到指定数据则返回特定值（视情况设置）
}

2.3 一些思考以及顺序表的缺点

缺点：

1. 中间/头部的插入删除操作不方便，需要遍历顺序表，时间复杂度为O(N)。
2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。
3. 增容一般是呈二倍的增长，无法避免会存在一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间，而且这种浪费现象有可能随着扩容次数的增加越来越严重。

思考：如何解决以上问题呢？接下来我们进入链表的学习或许能找到答案。

三、链表

3.1 概念及结构

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

从上图可以看出：

1. 链式结构在逻辑上是连续的，但物理存储上并不一定连续。
2. 链表结点一般都是从堆上申请的空间。
3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。
4. 链表一般分为数据域与指针域两个部分，数据域存储了数据信息，指针域存储了相关结点的地址信息。

3.2 链表的分类

链表分为：带头 / 不带头，循环 / 不循环，单向 / 双向。可以分别构成8种链表结构。
但实际中最常用的还是 无头单向不循环 / 带头双向循环 链表。

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

3.3 链表的实现

3.3.1 无头单向非循环链表

//实现单链表 Single Linked List 的增删查改
typedef int SLTDataType;
typedef struct SListNode//定义链表结点的结构体
{SLTDataType data;struct SListNode* next;//下一个结点为结构体类型，不是SLTDataType
}SLTNode;//输出单链表数据
void SLTPrint(SLTNode* phead);
//动态申请一个结点
SLTNode* SLBuyNode(SLTDataType x);
//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找特定数据
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

需要用到的头文件：

#include<stdio.h>
#include<stdlib.h>//提供free,malloc函数
#include<assert.h>//提供assert函数

头插尾插，头删尾删：

//动态申请一个结点
SLTNode* SLBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//动态申请一块空间if (!newnode)//申请失败则报错并退出{perror("malloc fail!\n");exit(1);}newnode->data = x;//初始化结点数据域的信息newnode->next = NULL;//初始化结点指针域的信息return newnode;//返回新结点
}

需要注意的是单向不带头链表的头结点即有效结点，创建时需要在堆上动态申请空间，所以先实现一个结点申请函数便于后续操作。接着我们就可以借助结点申请函数来创建单链表了。单链表的创建需要创建一个单链表结点结构体类型的指针变量，例如SLTNode* phead = SLBuyNode(x);。需要知道的是像这样的一个指针作为头节点就可以指向一整个链表，这就是单链表的初始化。

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{//要改变指向头节点的指针就需要传递头节点的地址，即&phead，则形参pphead类型为二级指针SLTNode**assert(pphead);//后续需要通过二级指针pphead访问头节点，先检查形参的有无有效性，即判空SLTNode* newnode = SLBuyNode(x);//申请需要尾插的新结点//尾插有两种情况if (!*pphead){//头节点为空*pphead = newnode;}else{//头节点不为空SLTNode* ptmp = *pphead;while (ptmp->next) //找单链表表尾，即最后一个结点ptmp{ptmp = ptmp->next;}ptmp->next = newnode;//将尾结点的next指向新结点}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);newnode->next = *pphead;//直接将新结点的next指向原头节点即可*pphead = newnode;//更新头节点指针信息，指向新头节点
}
//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//删除操作不仅要保证pphead不为空，还要保证链表不为空，即头节点不为空//如果链表有多个结点，尾删需要先找到尾结点以及尾结点的前一结点SLTNode* pcur = *pphead;//找尾结点SLTNode* prev = *pphead;//找尾结点前一结点if (!pcur->next){//一个结点，直接释放头节点，同时头结点置为空free(pcur);*pphead = NULL;}else{//多个结点，遍历链表while (pcur->next){prev = pcur;pcur = pcur->next;}prev->next = NULL;//前结点的next置为空free(pcur);//释放尾结点}
}
//头删
void SLTPopFront(SLTNode** pphead)
{//删除操作需要保证pphead不为空且链表不为空assert(pphead && *pphead);SLTNode* del = *pphead;//保存需要删除的头结点*pphead = (*pphead)->next;//头结点置为原头结点的下一结点free(del);//释放原头结点
}

输出链表数据：

void SLTPrint(SLTNode* phead)
{//一个简单的遍历即可SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

查找特定数据：

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;while (pcur)//简单的遍历比较判断{if (pcur->data == x){//找到第一个符合条件的结点直接返回该结点即可return pcur;}pcur = pcur->next;}return NULL;//遍历链表未找到则返回空指针
}

指定位置插入删除：
需要注意，什么是指定位置呢？它又是如何表示的呢？由于链表不同于顺序表，可以通过下标找到指定位置的数据，因此这个指定位置其实是某个结点——一整个结点，这里可以配合上面的查找接口完成整个操作逻辑。在插入或删除指定位置操作时，我们需要注意保证链表不会断开，仔细斟酌前、后结点与指定结点的next。

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{//在指定位置插入亦需要保证pphead，链表，以及位置有效，不为空assert(pphead && *pphead && pos);SLTNode* newnode = SLBuyNode(x);//结点在指定位置前的插入有两种情况if (*pphead == pos){//头节点为指定位置newnode->next = *pphead;//新结点的next指向头节点*pphead = newnode;//头节点置为新结点}else{//指定位置不为头节点SLTNode* prev = *pphead;//遍历找到指定位置结点的前一结点while (prev->next != pos){prev = prev->next;}newnode->next = pos;//新节点的next指向指定结点prev->next = newnode;//指定结点前一结点的next指向新结点}
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{//修改结点结构体内的信息，传参结构体类型指针变量即可，同时需要确保pos的有效性assert(pos);SLTNode* newnode = SLBuyNode(x);newnode->next = pos->next;//新结点的next指向pos的下一结点pos->next = newnode;//pos的next指向新结点
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{//删除整个结点需要确保结点的地址pphead有效，链表不为空以及pos有效assert(pphead && *pphead && pos);//指定结点的删除有两种情况if (*pphead == pos){//指定结点为头节点*pphead = (*pphead)->next;//新头节点为原头节点的下一结点free(pos);//释放原头节点}else{//指定结点不为头结点SLTNode* prev = *pphead;//找到指定结点前一结点while (prev->next != pos){prev = prev->next;}prev->next = prev->next->next;//指定结点前一结点的next指向pos后一结点free(pos);//释放指定结点}
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;//保存需要删除的结点pos->next = del->next;//pos的next指向删除结点的下一结点free(del);
}

销毁链表：

void SListDesTroy(SLTNode** pphead)
{assert(pphead);SLTNode* pcur = *pphead;while (pcur)//遍历链表{SLTNode* del = pcur;//先保存删除结点pcur = pcur->next;//再找到下一结点free(del);//释放删除结点}*pphead = NULL;//链表置为空
}

3.3.2 带头双向循环链表

带头双向循环链表的“头”即哨兵位，也称头节点，但这里的头节点就没有实际意义了，仅仅作为一个标记，也不会存储数据信息，只会存储前一结点与后一结点的地址信息。

//带头双向循环链表 Linked List 增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//申请结点
LTNode* LTBuyNode(LTDataType x);
//双向循环链表的初始化
LTNode* LTInit();
// 双向链表销毁
void LTDestory(LTNode* phead);
// 双向链表打印
void LTPrint(LTNode* phead);
// 头部插入删除/尾部插入删除
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
// 双向链表查找
LTNode* LTFind(LTNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos);

需要用到的头文件：与单链表相同。

双向循环链表的初始化与销毁：

//申请结点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (!node){perror("malloc fail!\n");exit(1);}node->data = x;node->next = node->prev = node;//只有一个结点的双向循环链表，前后结点都是自己return node;
}
//双向循环链表的初始化
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);//哨兵位取任意值即可return phead;//返回哨兵位结点
}
// 双向链表销毁
void LTDestory(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;//跳过哨兵位找下一有效结点//销毁结点while (pcur != phead)//遍历链表{//先保存下一结点再销毁上一结点LTNode* ptmp = pcur->next;free(pcur);pcur = ptmp;}//销毁哨兵位free(phead);pcur = phead = NULL;
}

双向链表打印：

void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

头部插入删除/尾部插入删除：

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//先修改新尾结点的指针域信息newnode->next = phead;//尾插next指向哨兵位newnode->prev = phead->prev;//尾插prev指向原尾结点//再修改哨兵位与原哨兵位前结点phead->prev->next = newnode;//原哨兵位前结点的next指向新尾结点phead->prev = newnode;//哨兵位的prev指向新尾结点
}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);//确保双向循环链表存在有效结点LTNode* del = phead->prev;//先保存尾结点//修改尾结点前后结点的指向del->prev->next = phead;//尾结点前一结点变为新尾结点，next指向哨兵位phead->prev = del->prev;//哨兵位的prev指向新尾结点free(del);//删除原尾结点del = NULL;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//先修改新结点的指针域信息newnode->prev = phead;//头插prev指向哨兵位newnode->next = phead->next;//头插next指向哨兵位下一结点//再修改哨兵位与原哨兵位下一结点指向phead->next->prev = newnode;//原哨兵位下一结点的prev指向新结点phead->next = newnode;//哨兵位的next指向新结点
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

双向链表查找:

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead)//遍历双向链表{if (pcur->data == x){//找到第一个符合条件的结点直接返回结点return pcur;}pcur = pcur->next;}return NULL;//未找到数据返回空
}

双向链表指定位置插入删除：

// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos && pos->prev);LTNode* newnode = LTBuyNode(x);newnode->prev = pos->prev;newnode->next = pos;pos->prev->next = newnode;pos->prev = newnode;
}
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos)
{assert(pos && pos->prev && pos->next);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

四、顺序表和链表的区别

顺序表的优点有:连续存储，访问方便，高效存储，缓存利用率高等。
链表的优点在于：方便插入删除操作，没有容量限制，动态申请创建结点。
注：缓存利用率参考存储体系结构以及局部原理性。

这里附上一个介绍缓存相关知识的佳文——与程序员相关的CPU缓存知识。

---

本篇到此结束，下一篇将会带来顺序表以及链表相关的OJ题分享，用于学习与巩固，做更深一步的提升。