目录
1. 线性表
2. 顺序表
2.1 概念及结构
2.1.1 静态顺序表（不常用）
2.1.2 动态顺序表（常用）
编辑
2.2 练习
2.2.1 移除元素
2.2.2 删除有序数组中的重复项
2.2.3 合并两个有序数组
2.3 顺序表存在的问题
3. 链表
3.1 概念及结构
3.2 链表的分类
编辑
3.2.1 常用链表
3.2.1.1 无头单向非循环链表
3.2.1.2 带头双向循环链表
3.3 无头单向非循环链表的实现
3.4 带头双向循环链表的实现
4. 对比顺序表和链表
💬 ：如果你在阅读过程中有任何疑问或想要进一步探讨的内容，欢迎在评论区畅所欲言！我们一起学习、共同成长~！
👍 ：如果你觉得这篇文章还不错，不妨顺手点个赞、加入收藏，并分享给更多的朋友噢~！
1. 线性表
线性表（linear list）是 n 个具有相同特性的数据元素的有限序列。它是一种在实际中广泛使用的数据结构。
常见的线性表包括：顺序表、链表、栈、队列、字符串等。
线性表在逻辑上是线性结构，即一条连续的直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
2. 顺序表
2.1 概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：静态顺序表，动态顺序表。
2.1.1 静态顺序表（不常用）
静态顺序表使用定长数组存储元素。存储数据前，需要预先确定数组的长度，且在程序运行过程中数组长度不能改变。
示例：
#include <stdio.h>
#define N 7// int 类型重命名为 SLDataType
typedef int SLDataType;// 定义静态顺序表结构体
typedef struct SeqList // 此结构体类型起了一个别名 SeqList
{SLDataType array[N]; // 定长数组size_t size; // size_t 用于表示无符号整数类型，通常用于表示数组的索引、对象的大小等// size ：当前有效数据的个数} SeqList;void SeqListInit(SeqList* psl)
{psl->size = 0;
}// 向静态顺序表尾部插入数据
int SeqListPushBack(SeqList* psl, SLDataType x)
{if (psl->size >= N) {printf("顺序表已满，无法插入\n");return 0;}psl->array[psl->size] = x;psl->size++; // 表示成功插入了一个数据return 1;
}// 打印静态顺序表
void SeqListPrint(SeqList* psl)
{for (size_t i = 0; i < psl->size; i++) {printf("%d ", psl->array[i]);}printf("\n");
}int main()
{SeqList sl;// 声明一个SeqList类型的变量sl，用于表示一个静态顺序表SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPrint(&sl);return 0;
}
2.1.2 动态顺序表（常用）
动态顺序表使用动态开辟的数组存储元素。可根据实际需要动态地增减数组的容量，以适应数据量的变化。
示例：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;
// int 类型重命名为 SLDataTypetypedef struct SeqList // 此结构体类型起了一个别名 SeqList
{SLDataType* array; // 指向动态开辟的数组size_t size; // 顺序表中有效数据的个数size_t capacity; // 顺序表当前容量大小
} SeqList;// 顺序表初始化
void SeqListInit(SeqList* psl)
{// 检查传入的顺序表指针是否为空，若为空则终止程序assert(psl);// 初始化时先不分配空间，将数组指针置为 NULLpsl->array = NULL;psl->size = 0;psl->capacity = 0;
}// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl)
{assert(psl);// 当有效数据个数等于容量时，说明顺序表已满，需要增容if (psl->size == psl->capacity){// 若当前容量为 0，先给一个初始容量，这里设为 4size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;// 重新分配内存空间，大小为新容量乘以每个数据元素的大小SLDataType* tmp = (SLDataType*)realloc(psl->array, newCapacity * sizeof(SLDataType));// 检查内存分配是否成功，若失败则终止程序assert(tmp);// 更新数组指针为新分配的内存地址psl->array = tmp;psl->capacity = newCapacity;}
}// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{assert(psl);// 插入元素前先检查是否需要增容CheckCapacity(psl);// 在顺序表的末尾插入新元素psl->array[psl->size] = x;// 有效数据个数加 1，表示插入一个元素psl->size++;
}// 顺序表尾删
void SeqListPopBack(SeqList* psl)
{assert(psl);// 检查顺序表中是否有数据，若没有则终止程序assert(psl->size > 0);// 表示删除一个元素psl->size--;
}// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{assert(psl);// 插入元素前先检查是否需要增容CheckCapacity(psl);// 将顺序表中所有元素依次向后移动一位for (int i = psl->size; i > 0; i--){psl->array[i] = psl->array[i - 1];}psl->array[0] = x;psl->size++;
}// 顺序表头删
void SeqListPopFront(SeqList* psl)
{assert(psl);// 检查顺序表中是否有数据，若没有则终止程序assert(psl->size > 0);// 将顺序表中所有元素依次向前移动一位for (int i = 0; i < psl->size - 1; i++){psl->array[i] = psl->array[i + 1];}psl->size--;
}// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x)
{assert(psl);for (size_t i = 0; i < psl->size; i++){// 若找到与目标元素相等的元素，返回其下标if (psl->array[i] == x){return (int)i;}}return -1;
}// 顺序表在 pos 位置插入 x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{assert(psl);// 检查插入位置是否合法，即不能小于 0 且不能大于当前有效数据个数assert(pos >= 0 && pos <= psl->size);// 插入元素前先检查是否需要增容CheckCapacity(psl);// 将 pos 位置及之后的元素依次向后移动一位for (size_t i = psl->size; i > pos; i--){psl->array[i] = psl->array[i - 1];}psl->array[pos] = x;psl->size++;
}// 顺序表删除 pos 位置的值
void SeqListErase(SeqList* psl, size_t pos)
{assert(psl);assert(pos >= 0 && pos < psl->size);for (size_t i = pos; i < psl->size - 1; i++){psl->array[i] = psl->array[i + 1];}psl->size--;
}// 顺序表销毁
void SeqListDestory(SeqList* psl)
{assert(psl);// 释放动态分配的数组内存free(psl->array);// 将数组指针置为 NULL，防止悬空指针psl->array = NULL;psl->size = 0;psl->capacity = 0;
}void SeqListPrint(SeqList* psl)
{assert(psl);for (size_t i = 0; i < psl->size; i++){printf("%d ", psl->array[i]);}printf("\n");
}int main()
{SeqList sl;// 声明一个SeqList类型的变量sl，用于表示一个动态顺序表// 表尾插SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPrint(&sl);// 表头插SeqListPushFront(&sl, 0);SeqListPrint(&sl);// 查找int index = SeqListFind(&sl, 2);if (index != -1){printf("元素 2 在顺序表中的下标是: %d\n", index);}else{printf("未找到元素 2\n");}// 表尾删SeqListPopBack(&sl);SeqListPrint(&sl);// 表头删SeqListPopFront(&sl);SeqListPrint(&sl);// 指定位置插入值SeqListInsert(&sl, 1, 10);SeqListPrint(&sl);// 指定位置删除值SeqListErase(&sl, 1);SeqListPrint(&sl);// 顺序表销毁SeqListDestory(&sl);return 0;
}
2.2 练习
2.2.1 移除元素
有一个数组和一个值 val，要求：
- 原地移除所有等于
val的元素 - 返回数组中不等于
val（剩余）的元素的数量 k - 新数组前 k 个元素包含不等于 val 的元素
“原地”：仅使用常数级别的额外空间，即空间复杂度为 O(1)。其算法直接在原始数据存储的内存位置上进行修改，而不是创建一个与原始数据规模相当的新数据结构来存储处理后的结果。
#include <stdio.h>int removeElement(int* nums, int numsSize, int val)
{int k = 0;for (int i = 0; i < numsSize; i++) {if (nums[i] != val) {// 如果不等于 val，则将该元素放到数组的前 k 个位置nums[k] = nums[i];k++;}}return k;
}int main()
{int nums[] = {3, 2, 2, 3};int numsSize = sizeof(nums) / sizeof(nums[0]);int val = 3;int newSize = removeElement(nums, numsSize, val);printf("剩余元素的数量: %d\n", newSize);printf("移除指定元素后的数组: ");for (int i = 0; i < newSize; i++) {printf("%d ", nums[i]);}printf("\n");return 0;
}
只遍历数组一次，所以时间复杂度 O(n) ，n 为数组长度。
2.2.2 删除有序数组中的重复项
原地删除一个非严格递增排列的数组 nums 中重复的元素，使每个元素只出现一次，保持元素的相对顺序不变，返回新数组的长度 k ，新数组前 k 个元素包含唯一元素。
#include <stdio.h>int removeDuplicates(int* nums, int numsSize)
{if (numsSize == 0) {return 0;}int slow = 0;for (int fast = 1; fast < numsSize; fast++) {if (nums[fast] != nums[slow]) {slow++;nums[slow] = nums[fast];}}return slow + 1;
}int main()
{int nums[] = {1, 1, 2, 2, 2, 3, 4, 4, 5};int numsSize = sizeof(nums) / sizeof(nums[0]);int newLength = removeDuplicates(nums, numsSize);printf("删除重复元素后数组的新长度: %d\n", newLength);printf("删除重复元素后的数组: ");for (int i = 0; i < newLength; i++) {printf("%d ", nums[i]);}printf("\n");return 0;
}只遍历数组一次，所以时间复杂度 O(n) ，n 为数组长度。
2.2.3 合并两个有序数组
给定两个非递减排序的整数数组 nums1 和 nums2，及整数 m 和 n。
要求：
nums1初始长度是m + n，前m个是待合并元素，后n个为 0 ；nums2初始长度为n；nums2合并到nums1里，合并后数组保持非递减顺序，合并后结果存于nums1中。
#include <stdio.h>void merge(int* nums1, int m, int* nums2, int n)
{int p1 = m - 1; // nums1 中最后一个“有效”元素的索引int p2 = n - 1; // nums2 中最后一个元素的索引int p = m + n - 1; // 合并后数组最后一个元素的索引// 从后往前比较两个数组的元素while (p1 >= 0 && p2 >= 0) {if (nums1[p1] > nums2[p2]) {nums1[p] = nums1[p1];p1--;}else {nums1[p] = nums2[p2];p2--;}p--;}// 其中一个数组遍历完后，若 nums2 还有剩余元素，将其复制到 nums1 前面while (p2 >= 0) {nums1[p] = nums2[p2];p2--;p--;}
}int main()
{int nums1[] = { 1, 2, 3, 0, 0, 0, 0, 0 };int m = 3;int nums2[] = { 0, 2, 5, 6, 7 };int n = 5;merge(nums1, m, nums2, n);for (int i = 0; i < m + n; i++) {printf("%d ", nums1[i]);}printf("\n");return 0;
}
| 对比 | nums1[p] | 每次比较后的数组 |
|---|---|---|
| nums1[7] = 7 | 1，2，3，0，0，0，0，7 | |
| nums1[6] = 6 | 1，2，3，0，0，0，6，7 | |
| nums1[5] = 5 | 1，2，3，0，0，5，6，7 | |
| nums1[4] = 3 | 1，2，3，0，3，5，6，7 | |
| nums1[3] = 2 | 1，2，3，2，3，5，6，7 | |
| nums1[2] = 2 | 1，2，2，2，3，5，6，7 | |
| nums1[1] = 1 | 1，1，2，2，3，5，6，7 |
然后 p1 = -1，p2 = 0，p = 0，执行第二个 while 循环，nums1[0] = nums2[0] = 0 ，得到合并数组{0，1，2，2，3，5，6，7} 。
另外，只遍历数组 nums1 和 nums2 一次，所以时间复杂度为 O(m+n) 。
2.3 顺序表存在的问题
顺序表存在以下问题：
- 进行中间或表头插入、删除操作时，时间复杂度达 O (N)。
- 增容要申请新空间、拷贝数据、释放旧空间，消耗大。
- 扩容一般扩大为原来的 2 倍，若插入数据少，造成空间浪费。
为解决这些问题，下面介绍链表结构。
3. 链表
3.1 概念及结构
链表在逻辑上是连续的，但是——链表节点一般从堆上申请空间，而堆上空间的分配依据一定策略进行，导致两次申请的空间可能连续，也可能不连续——所以链表的物理存储地址不一定连续。
3.2 链表的分类
- 单向/双向
- 带头/不带头
- 循环/非循环
3.2.1 常用链表
3.2.1.1 无头单向非循环链表
结构简单，一般不会单独用来存数据。实际中更多作为其他数据结构的子结构，如哈希桶、图的邻接表等。另外这种结构在笔试面试中较常见。
3.2.1.2 带头双向循环链表
结构最复杂，一般用来单独存储数据。实际中使用的链表数据结构多是带头双向循环链表。
3.3 无头单向非循环链表的实现
#include <stdio.h>
#include <stdlib.h>typedef int SLTDateType;// 定义链表节点结构体
typedef struct SListNode
{SLTDateType data; // 节点存储的数据struct SListNode* next; // 指向下一个节点的指针
}SListNode;// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{// 为新节点分配内存空间SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));if (newNode == NULL) {perror("malloc");return NULL;}// 初始化新节点的数据newNode->data = x;// 新节点的下一个节点初始化为空newNode->next = NULL;return newNode;
}void SListPrint(SListNode* plist)
{SListNode* cur = plist;// plist 是指向链表头节点的指针while (cur != NULL) // 无头单向非循环链表的末尾节点的 next 指针始终被设置为 NULL{// 打印当前节点的数据printf("%d -> ", cur->data);// 移动到下一个节点cur = cur->next;}// 打印链表结束标志printf("NULL\n");
}// 尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{// 创建新节点SListNode* newNode = BuySListNode(x);if (*pplist == NULL) {// 如果链表为空，新节点就是链表的头节点*pplist = newNode;}else {// 找到链表的尾节点SListNode* tail = *pplist;while (tail->next != NULL) {tail = tail->next;}tail->next = newNode;}
}// 头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{SListNode* newNode = BuySListNode(x);// 新节点的下一个节点指向原来的头节点newNode->next = *pplist;*pplist = newNode;
}// 尾删
void SListPopBack(SListNode** pplist)
{if (*pplist == NULL) // 若链表为空 {return; // 函数立即终止执行}if ((*pplist)->next == NULL) {// 如果链表只有一个节点，释放该节点并将头指针置空free(*pplist);*pplist = NULL;}else {SListNode* prev = NULL;SListNode* tail = *pplist;while (tail->next != NULL) {prev = tail;tail = tail->next;}// 最后一次循环中，prev 被赋为 tail 的前一个节点，tail 移到了尾节点free(tail);// 倒数第二个节点的下一个节点置空prev->next = NULL;}
}// 头删
void SListPopFront(SListNode** pplist)
{if (*pplist == NULL) {return;}// 保存原来的头节点SListNode* first = *pplist;// 更新头节点为原来头节点的下一个节点*pplist = first->next;// 释放原来的头节点free(first);
}// 查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{// 遍历链表，查找值为x的节点SListNode* cur = plist;while (cur != NULL) {if (cur->data == x) {return cur;}cur = cur->next;}return NULL;
}// 在pos的后一个位置插入值 x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{if (pos == NULL) {return;}SListNode* newNode = BuySListNode(x);newNode->next = pos->next;pos->next = newNode;
}// 删除pos后一个位置的值
void SListEraseAfter(SListNode* pos)
{if (pos == NULL || pos->next == NULL) // 如果pos为空或者pos是尾节点 {return;}// 保存pos节点的下一个节点SListNode* nextNode = pos->next;// pos节点的下一个节点指向要删除节点的下一个节点pos->next = nextNode->next;free(nextNode);
}int main()
{SListNode* list = NULL; // 声明并初始化一个指向 SListNode 类型结构体的指针 list// 用于表示初始为空的链表// 尾插SListPushBack(&list, 1);SListPushBack(&list, 2);SListPushBack(&list, 3);SListPrint(list);// 头插SListPushFront(&list, 0);SListPrint(list);// 尾删SListPopBack(&list);SListPrint(list);// 头删SListPopFront(&list);SListPrint(list);// 查找SListNode* found = SListFind(list, 2);if (found) {printf("Found: %d\n", found->data);}else {printf("Not found\n");}// 在pos的后一个位置插入值SListInsertAfter(list, 4);SListPrint(list);// 删除pos后一个位置的值SListEraseAfter(list);SListPrint(list);return 0;
}
“无头单向非循环链表的末尾节点的 next 指针始终被设置为 NULL”：
- 节点创建：新节点创建时，
next指针初始化为NULL。 - 尾插操作：尾插新节点时，若链表为空，新节点成头节点，
next为NULL；若不为空，找到尾节点，将其next指向新节点（新节点next已初始化为NULL）。 - 尾删操作：尾删时，若链表仅一个节点，释放后链表为空；若有多个节点，释放尾节点，将倒数第二个节点的
next置为NULL。
思考：为什么在pos的后一个位置插入值，而非前一个位置？为什么不删除 pos 位置节点？
（1）单向链表只能从前向后遍历，没有指向前一节点的指针，无法直接获取 pos 节点的前一个节点，因此只能从头节点开始依次遍历链表，直到找到 pos 节点的前一个节点，时间复杂度达 O(n)；而在 pos 后插入，只改两个指针，时间复杂度为 O(1)。
（2）删除 pos 位置节点需找到其前一节点，时间复杂度达 O(n)；而删除 pos 后节点，只改一个指针，时间复杂度为 O(1)。
3.4 带头双向循环链表的实现
#include <stdio.h>
#include <stdlib.h>typedef int LTDataType;typedef struct ListNode
{LTDataType _data; // 节点存储的数据struct ListNode* next; // 指向下一个节点的指针struct ListNode* prev; // 指向前一个节点的指针
}ListNode;// 创建返回链表的头结点
ListNode* ListCreate()
{// 为头节点分配内存ListNode* phead = (ListNode*)malloc(sizeof(ListNode));if (phead == NULL) {perror("malloc fail");return NULL;}// 头节点的 next 和 prev 都指向自身，形成循环phead->next = phead;phead->prev = phead;return phead;
}// 双向链表销毁
void ListDestory(ListNode* plist)
{// 从头节点的下一个节点开始遍历ListNode* cur = plist->next;while (cur != plist) {// 保存当前节点的下一个节点ListNode* next = cur->next;free(cur);cur = next;}// 最后释放头节点的内存free(plist);
}void ListPrint(ListNode* plist)
{ListNode* cur = plist->next;while (cur != plist) {printf("%d ", cur->_data);cur = cur->next;}printf("\n");
}// 尾插
void ListPushBack(ListNode* plist, LTDataType x)
{// 创建新节点ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL) {perror("malloc fail");return;}newnode->_data = x;// 找到尾节点ListNode* tail = plist->prev;// 插入新节点tail->next = newnode;newnode->prev = tail;newnode->next = plist;plist->prev = newnode;
}// 尾删
void ListPopBack(ListNode* plist)
{// 检查链表是否为空if (plist->next == plist) {return;}// 找到尾节点ListNode* tail = plist->prev;// 找到尾节点的前一个节点ListNode* prev = tail->prev;free(tail);// 更新指针prev->next = plist;plist->prev = prev;
}// 头插
void ListPushFront(ListNode* plist, LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL) {perror("malloc fail");return;}newnode->_data = x;// 保存头节点的下一个节点ListNode* first = plist->next;// 插入新节点plist->next = newnode;newnode->prev = plist;newnode->next = first;first->prev = newnode;
}// 头删
void ListPopFront(ListNode* plist)
{// 检查链表是否为空if (plist->next == plist) {return;}// 保存头节点的下一个节点ListNode* first = plist->next;// 保存头节点的下下一个节点ListNode* second = first->next;// 释放头节点的下一个节点的内存free(first);// 更新指针plist->next = second;second->prev = plist;
}// 查找
ListNode* ListFind(ListNode* plist, LTDataType x)
{// 从头节点的下一个节点开始遍历ListNode* cur = plist->next;while (cur != plist) {if (cur->_data == x) {return cur;}cur = cur->next;}return NULL;
}// 在pos的前一个位置插入
void ListInsert(ListNode* pos, LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL) {perror("malloc fail");return;}newnode->_data = x;// 找到 pos 节点的前一个节点ListNode* prev = pos->prev;// 插入新节点prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}// 删除pos位置的节点
void ListErase(ListNode* pos)
{ListNode* prev = pos->prev;ListNode* next = pos->next;free(pos);// 更新指针prev->next = next;next->prev = prev;
}int main()
{ListNode* plist = ListCreate();// 调用 ListCreate 创建带头双向循环链表，并将返回的头节点指针赋值给 plistListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPrint(plist);ListPushFront(plist, 0);ListPrint(plist);ListPopBack(plist);ListPrint(plist);ListPopFront(plist);ListPrint(plist);ListNode* pos = ListFind(plist, 2);if (pos) {ListInsert(pos, 4);ListPrint(plist);}pos = ListFind(plist, 4);if (pos) {ListErase(pos);ListPrint(plist);}ListDestory(plist);return 0;
}
4. 对比顺序表和链表
| 对比维度 | 顺序表 | 链表 |
|---|---|---|
| 存储空间 | 物理存储上一定连续 | 逻辑上数据元素连续，但物理内存中不一定连续，节点通过指针相互连接 |
| 随机访问 | 支持随机访问，通过下标可直接定位元素，时间复杂度为 O (1) | 需从表头开始，逐个通过指针遍历查找元素，时间复杂度为 O (N) |
| 插入和删除操作 | 在任意位置插入或删除元素时，可能需移动后续元素，效率较低，时间复杂度为 O (N) | 插入或删除元素时，仅需修改相关节点的指针指向，操作相对简便 |
| 插入特性 | 动态顺序表空间不足时，需进行扩容，涉及重新分配内存、数据拷贝等步骤 | 没有容量限制，可随时动态创建和删除节点 |
| 应用场景 | 适合元素高效存储且频繁访问的场景，如数组实现的线性表 | 适用于数据插入和删除操作频繁的场景，如实现队列、栈等数据结构 |
| 缓存利用率 | 物理存储连续，符合局部性原理，读取数据时相邻数据易一同加载到缓存中，缓存利用率高 | 节点物理位置分散，难以充分利用缓存，缓存利用率较低 |
