【C语言数据结构】线性表：链表、栈、队列

1. 数据结构

数据结构是计算机存储、组织数据的方式，它研究的是数据元素之间的逻辑关系、物理存储结构以及在此基础上定义的相关操作。简单来说，数据结构就是“数据 + 关系 + 操作”三者的统一体。

数据结构通常分为逻辑结构和物理结构两大类：

• 逻辑结构：描述数据元素之间的抽象关系，与存储无关，包括集合结构、线性结构、树形结构和图形结构。
• 物理结构：指数据在计算机内存中的实际存储形式，常见的有顺序存储结构和链式存储结构。

本文重点讨论线性结构中的线性表，以及由线性表演化而来的链表、栈和队列。

2. 线性表

线性表是最基本、最常用的一种线性结构，它是由 n（n≥0）个相同类型的数据元素组成的有限序列。当 n=0 时称为空表。

线性表具有以下特点：

• 存在唯一的一个“第一个”数据元素和“最后一个”数据元素。
• 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。
• 元素之间是一对一的线性关系。

例如，一个学生成绩表 (85, 92, 78, 96) 就是一个线性表，其中 85 是第一个元素，96 是最后一个元素。

2.1 线性表的物理实现

线性表在计算机中主要有两种物理存储方式：顺序存储和链式存储。

2.1.1 顺序存储

顺序存储是用一组地址连续的存储单元依次存放线性表中的数据元素，通常借助数组来实现。它的特点是逻辑上相邻的元素在物理地址上也相邻，支持随机访问，但插入和删除操作需要移动大量元素。

#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int length; // 当前长度
} SeqList;

2.1.2 链式存储

链式存储不要求物理地址连续，通过指针将各个结点串联起来。每个结点包含数据域和指针域。它的特点是插入和删除操作灵活，不需要移动元素，但无法随机访问，需要从头遍历。

typedef struct Node {
int data;
struct Node *next;
} Node;

2.2 线性表的常规操作

线性表常见的操作包括：

• 初始化：创建一个空的线性表。
• 判空：判断线性表是否为空。
• 求长度：返回线性表中元素的个数。
• 查找：按值查找或按位置查找元素。
• 插入：在指定位置插入一个新元素。
• 删除：删除指定位置的元素。
• 遍历：依次访问线性表中的每个元素。

下面以顺序表为例，演示插入和删除操作的实现：

// 在顺序表 L 的第 i 个位置插入元素 e
int Insert(SeqList *L, int i, int e) {
if (i < 1 || i > L->length + 1 || L->length >= MAXSIZE) {
return 0; // 插入失败
}
for (int j = L->length; j >= i; j–) {
L->data[j] = L->data[j – 1]; // 元素后移
}
L->data[i – 1] = e;
L->length++;
return 1;
}

// 删除顺序表 L 中第 i 个位置的元素
int Delete(SeqList *L, int i) {
if (i < 1 || i > L->length) {
return 0; // 删除失败
}
for (int j = i; j < L->length; j++) {
L->data[j – 1] = L->data[j]; // 元素前移
}
L->length–;
return 1;
}

3. 链表

链表是线性表的链式存储实现，它通过指针将一组不连续的内存结点串联起来。每个结点由数据域和指针域组成，指针域指向下一个结点。

链表按结构和指针方向可分为以下四类：

• 单链表：每个结点只有一个指向后继的指针，最后一个结点的指针域为空。
• 双链表：每个结点有两个指针，分别指向前驱和后继。
• 单向循环链表：在单链表基础上，将最后一个结点的指针指向头结点，形成环。
• 双向循环链表：在双链表基础上，头结点的前驱指向尾结点，尾结点的后继指向头结点。

3.1 单链表

3.1.1 单链表的定义

单链表是最简单的链表结构，每个结点只包含一个指向后继结点的指针。它的特点是只能从头到尾单向遍历。

typedef struct Node {
int data; // 数据域
struct Node *next; // 指针域，指向下一个结点
} Node, *LinkList;

3.1.2 单链表的操作

单链表常见的操作包括：初始化、头插法建表、尾插法建表、查找、插入、删除和遍历。

// 初始化单链表
LinkList InitList() {
LinkList L = (LinkList)malloc(sizeof(Node));
L->next = NULL;
return L;
}

// 头插法建立单链表
void HeadInsert(LinkList L, int e) {
Node *s = (Node*)malloc(sizeof(Node));
s->data = e;
s->next = L->next;
L->next = s;
}

// 尾插法建立单链表
void TailInsert(LinkList L, int e) {
Node *p = L;
while (p->next != NULL) {
p = p->next;
}
Node *s = (Node*)malloc(sizeof(Node));
s->data = e;
s->next = NULL;
p->next = s;
}

// 按值查找结点
Node* FindByValue(LinkList L, int e) {
Node *p = L->next;
while (p != NULL && p->data != e) {
p = p->next;
}
return p;
}

// 在第 i 个位置插入结点
int InsertNode(LinkList L, int i, int e) {
Node *p = L;
int j = 0;
while (p != NULL && j < i – 1) {
p = p->next;
j++;
}
if (p == NULL) return 0;
Node *s = (Node*)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return 1;
}

// 删除第 i 个结点
int DeleteNode(LinkList L, int i) {
Node *p = L;
int j = 0;
while (p->next != NULL && j < i – 1) {
p = p->next;
j++;
}
if (p->next == NULL) return 0;
Node *q = p->next;
p->next = q->next;
free(q);
return 1;
}

// 遍历单链表
void PrintList(LinkList L) {
Node *p = L->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\\n");
}

3.1.3 单链表示例

int main() {
LinkList L = InitList();
TailInsert(L, 10);
TailInsert(L, 20);
TailInsert(L, 30);
PrintList(L); // 输出：10 20 30

InsertNode(L, 2, 15);
PrintList(L); // 输出：10 15 20 30

DeleteNode(L, 3);
PrintList(L); // 输出：10 15 30
return 0;
}

3.2 双链表

3.2.1 双链表的定义

双链表在单链表的基础上增加了一个指向前驱结点的指针，使得结点既可以向后遍历，也可以向前遍历。

typedef struct DNode {
int data;
struct DNode *prior; // 指向前驱
struct DNode *next; // 指向后继
} DNode, *DLinkList;

3.2.2 双链表的操作

双链表的核心操作是插入和删除，由于多了一个前驱指针，操作时需要同时修改两个方向的指针。

// 初始化双链表
DLinkList InitDList() {
DLinkList L = (DLinkList)malloc(sizeof(DNode));
L->prior = NULL;
L->next = NULL;
return L;
}

// 在结点 p 之后插入结点 s
void InsertAfter(DNode *p, DNode *s) {
s->next = p->next;
s->prior = p;
if (p->next != NULL) {
p->next->prior = s;
}
p->next = s;
}

// 删除结点 p 的后继结点
int DeleteNext(DNode *p) {
if (p->next == NULL) return 0;
DNode *q = p->next;
p->next = q->next;
if (q->next != NULL) {
q->next->prior = p;
}
free(q);
return 1;
}

// 遍历双链表（正向）
void PrintDList(DLinkList L) {
DNode *p = L->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\\n");
}

3.2.3 双链表示例

int main() {
DLinkList L = InitDList();
DNode *s1 = (DNode*)malloc(sizeof(DNode));
s1->data = 5;
InsertAfter(L, s1);

DNode *s2 = (DNode*)malloc(sizeof(DNode));
s2->data = 8;
InsertAfter(s1, s2);

PrintDList(L); // 输出：5 8

DeleteNext(s1);
PrintDList(L); // 输出：5
return 0;
}

3.3 单向循环链表

3.3.1 单向循环链表的定义

单向循环链表是在单链表的基础上，将最后一个结点的 next 指针指向头结点，从而形成一个环。这样从任意一个结点出发都可以遍历整个链表。

typedef struct Node {
int data;
struct Node *next;
} Node, *CircularList;

3.3.2 单向循环链表的操作

单向循环链表的操作与单链表类似，区别在于遍历的终止条件从 p == NULL 变为 p == L（回到头结点）。

// 初始化单向循环链表
CircularList InitCircularList() {
CircularList L = (CircularList)malloc(sizeof(Node));
L->next = L; // 头结点指向自身
return L;
}

// 尾插法
void TailInsertC(CircularList L, int e) {
Node *p = L;
while (p->next != L) {
p = p->next;
}
Node *s = (Node*)malloc(sizeof(Node));
s->data = e;
s->next = L;
p->next = s;
}

// 遍历单向循环链表
void PrintCircularList(CircularList L) {
Node *p = L->next;
while (p != L) {
printf("%d ", p->data);
p = p->next;
}
printf("\\n");
}

3.3.3 单向循环链表示例

int main() {
CircularList L = InitCircularList();
TailInsertC(L, 1);
TailInsertC(L, 2);
TailInsertC(L, 3);
PrintCircularList(L); // 输出：1 2 3
return 0;
}

3.4 双向循环链表

3.4.1 双向循环链表的定义

双向循环链表是双链表和循环链表的结合：头结点的 prior 指向尾结点，尾结点的 next 指向头结点。它既支持双向遍历，又支持循环访问。

typedef struct DNode {
int data;
struct DNode *prior;
struct DNode *next;
} DNode, *DCircularList;

3.4.2 双向循环链表的操作

// 初始化双向循环链表
DCircularList InitDCircularList() {
DCircularList L = (DCircularList)malloc(sizeof(DNode));
L->prior = L;
L->next = L;
return L;
}

// 尾插法
void TailInsertDC(DCircularList L, int e) {
DNode *s = (DNode*)malloc(sizeof(DNode));
s->data = e;
s->next = L;
s->prior = L->prior;
L->prior->next = s;
L->prior = s;
}

// 正向遍历
void PrintDCForward(DCircularList L) {
DNode *p = L->next;
while (p != L) {
printf("%d ", p->data);
p = p->next;
}
printf("\\n");
}

// 反向遍历
void PrintDCBackward(DCircularList L) {
DNode *p = L->prior;
while (p != L) {
printf("%d ", p->data);
p = p->prior;
}
printf("\\n");
}

3.4.3 双向循环链表示例

int main() {
DCircularList L = InitDCircularList();
TailInsertDC(L, 100);
TailInsertDC(L, 200);
TailInsertDC(L, 300);
PrintDCForward(L); // 输出：100 200 300
PrintDCBackward(L); // 输出：300 200 100
return 0;
}

4. 栈

栈是一种只允许在一端（栈顶）进行插入和删除操作的线性表，遵循“后进先出”（LIFO，Last In First Out）的原则。允许插入和删除的一端称为栈顶，另一端称为栈底。

栈的基本操作包括：

• 初始化：创建一个空栈。
• 入栈（Push）：在栈顶插入一个元素。
• 出栈（Pop）：删除栈顶元素并返回其值。
• 取栈顶元素（GetTop）：读取栈顶元素但不删除。
• 判空（IsEmpty）：判断栈是否为空。

4.1 顺序栈的实现

顺序栈使用数组作为底层存储，通过一个 top 指针（或下标）指示栈顶位置。top 初始为 -1 表示空栈，入栈时先自增再赋值，出栈时先取值再自减。

#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int top; // 栈顶指针，初始为 -1
} SeqStack;

// 初始化空栈
void InitStack(SeqStack *S) {
S->top = -1;
}

// 判空
int IsEmpty(SeqStack *S) {
return S->top == -1;
}

// 判满
int IsFull(SeqStack *S) {
return S->top == MAXSIZE – 1;
}

// 入栈
int Push(SeqStack *S, int e) {
if (IsFull(S)) return 0; // 栈满，入栈失败
S->data[++S->top] = e;
return 1;
}

// 出栈
int Pop(SeqStack *S, int *e) {
if (IsEmpty(S)) return 0; // 栈空，出栈失败
*e = S->data[S->top–];
return 1;
}

// 取栈顶元素
int GetTop(SeqStack *S, int *e) {
if (IsEmpty(S)) return 0;
*e = S->data[S->top];
return 1;
}

4.1.1 顺序栈示例

int main() {
SeqStack S;
InitStack(&S);
int e;

Push(&S, 10);
Push(&S, 20);
Push(&S, 30);

GetTop(&S, &e);
printf("栈顶元素：%d\\n", e); // 输出：30

Pop(&S, &e);
printf("出栈元素：%d\\n", e); // 输出：30
Pop(&S, &e);
printf("出栈元素：%d\\n", e); // 输出：20
return 0;
}

4.2 链式栈的实现

链式栈以单链表为底层结构，将链表头部作为栈顶，入栈和出栈都在头部进行，时间复杂度均为 O(1)，且不受固定容量限制。

typedef struct StackNode {
int data;
struct StackNode *next;
} StackNode, *LinkStack;

// 初始化链式栈
void InitLinkStack(LinkStack *S) {
*S = NULL;
}

// 判空
int IsLinkEmpty(LinkStack S) {
return S == NULL;
}

// 入栈（头插）
void PushLink(LinkStack *S, int e) {
StackNode *s = (StackNode*)malloc(sizeof(StackNode));
s->data = e;
s->next = *S;
*S = s;
}

// 出栈（删除头结点）
int PopLink(LinkStack *S, int *e) {
if (IsLinkEmpty(*S)) return 0;
StackNode *p = *S;
*e = p->data;
*S = p->next;
free(p);
return 1;
}

// 取栈顶元素
int GetLinkTop(LinkStack S, int *e) {
if (IsLinkEmpty(S)) return 0;
*e = S->data;
return 1;
}

4.2.1 链式栈示例

int main() {
LinkStack S;
InitLinkStack(&S);
int e;

PushLink(&S, 1);
PushLink(&S, 2);
PushLink(&S, 3);

GetLinkTop(S, &e);
printf("栈顶元素：%d\\n", e); // 输出：3

PopLink(&S, &e);
printf("出栈元素：%d\\n", e); // 输出：3
PopLink(&S, &e);
printf("出栈元素：%d\\n", e); // 输出：2
return 0;
}

4.3 栈的典型应用

栈的“后进先出”特性在程序设计中应用广泛，常见场景包括：

• 函数调用：系统用调用栈保存函数返回地址和局部变量，函数嵌套调用时后调用的先返回。
• 括号匹配：编译器借助栈检查表达式中的括号是否成对匹配。
• 表达式求值：中缀表达式转后缀表达式，以及后缀表达式的求值都依赖栈。
• 浏览器的前进后退：用两个栈分别记录访问历史，实现前进和后退。

下面以括号匹配为例，演示栈的实际应用：

// 判断括号是否匹配
int MatchBrackets(char *expr) {
SeqStack S;
InitStack(&S);
for (int i = 0; expr[i] != '\\0'; i++) {
if (expr[i] == '(' || expr[i] == '[' || expr[i] == '{') {
Push(&S, expr[i]);
} else if (expr[i] == ')' || expr[i] == ']' || expr[i] == '}') {
if (IsEmpty(&S)) return 0; // 右括号多余
int top;
Pop(&S, &top);
if ((expr[i] == ')' && top != '(') ||
(expr[i] == ']' && top != '[') ||
(expr[i] == '}' && top != '{')) {
return 0; // 括号不匹配
}
}
}
return IsEmpty(&S); // 栈空则全部匹配
}

5. 队列

队列是一种只允许在一端（队尾）进行插入、在另一端（队头）进行删除操作的线性表，遵循“先进先出”（FIFO，First In First Out）的原则。允许插入的一端称为队尾，允许删除的一端称为队头。

队列的基本操作包括：

• 初始化：创建一个空队列。
• 入队（EnQueue）：在队尾插入一个元素。
• 出队（DeQueue）：删除队头元素并返回其值。
• 取队头元素（GetHead）：读取队头元素但不删除。
• 判空（IsEmpty）：判断队列是否为空。

5.1 顺序队列的实现

顺序队列使用数组作为底层存储，通过 front 和 rear 两个下标分别指示队头和队尾。入队时 rear 自增，出队时 front 自增。为避免“假溢出”，通常采用循环队列，让 rear 和 front 在数组范围内循环移动。

#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int front; // 队头下标
int rear; // 队尾下标
} SeqQueue;

// 初始化空队列
void InitQueue(SeqQueue *Q) {
Q->front = 0;
Q->rear = 0;
}

// 判空
int IsQueueEmpty(SeqQueue *Q) {
return Q->front == Q->rear;
}

// 判满
int IsQueueFull(SeqQueue *Q) {
return (Q->rear + 1) % MAXSIZE == Q->front;
}

// 入队
int EnQueue(SeqQueue *Q, int e) {
if (IsQueueFull(Q)) return 0; // 队满，入队失败
Q->data[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAXSIZE;
return 1;
}

// 出队
int DeQueue(SeqQueue *Q, int *e) {
if (IsQueueEmpty(Q)) return 0; // 队空，出队失败
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZE;
return 1;
}

// 取队头元素
int GetQueueHead(SeqQueue *Q, int *e) {
if (IsQueueEmpty(Q)) return 0;
*e = Q->data[Q->front];
return 1;
}

5.1.1 顺序队列示例

int main() {
SeqQueue Q;
InitQueue(&Q);
int e;

EnQueue(&Q, 10);
EnQueue(&Q, 20);
EnQueue(&Q, 30);

GetQueueHead(&Q, &e);
printf("队头元素：%d\\n", e); // 输出：10

DeQueue(&Q, &e);
printf("出队元素：%d\\n", e); // 输出：10
DeQueue(&Q, &e);
printf("出队元素：%d\\n", e); // 输出：20
return 0;
}

5.2 链式队列的实现

链式队列以单链表为底层结构，队头指向链表头结点，队尾指向链表尾结点。入队在队尾进行，出队在队头进行，时间复杂度均为 O(1)，且不受固定容量限制。

typedef struct QNode {
int data;
struct QNode *next;
} QNode;

typedef struct {
QNode *front; // 队头指针
QNode *rear; // 队尾指针
} LinkQueue;

// 初始化链式队列
void InitLinkQueue(LinkQueue *Q) {
Q->front = (QNode*)malloc(sizeof(QNode));
Q->front->next = NULL;
Q->rear = Q->front;
}

// 判空
int IsLinkQueueEmpty(LinkQueue *Q) {
return Q->front == Q->rear;
}

// 入队（尾插）
void EnLinkQueue(LinkQueue *Q, int e) {
QNode *s = (QNode*)malloc(sizeof(QNode));
s->data = e;
s->next = NULL;
Q->rear->next = s;
Q->rear = s;
}

// 出队（删除头结点）
int DeLinkQueue(LinkQueue *Q, int *e) {
if (IsLinkQueueEmpty(Q)) return 0; // 队空，出队失败
QNode *p = Q->front->next;
*e = p->data;
Q->front->next = p->next;
if (Q->rear == p) {
Q->rear = Q->front; // 队列为空时重置队尾
}
free(p);
return 1;
}

// 取队头元素
int GetLinkQueueHead(LinkQueue *Q, int *e) {
if (IsLinkQueueEmpty(Q)) return 0;
*e = Q->front->next->data;
return 1;
}

5.2.1 链式队列示例

int main() {
LinkQueue Q;
InitLinkQueue(&Q);
int e;

EnLinkQueue(&Q, 1);
EnLinkQueue(&Q, 2);
EnLinkQueue(&Q, 3);

GetLinkQueueHead(&Q, &e);
printf("队头元素：%d\\n", e); // 输出：1

DeLinkQueue(&Q, &e);
printf("出队元素：%d\\n", e); // 输出：1
DeLinkQueue(&Q, &e);
printf("出队元素：%d\\n", e); // 输出：2
return 0;
}

5.3 队列的典型应用

队列的“先进先出”特性在程序设计中应用广泛，常见场景包括：

• 任务调度：操作系统按到达顺序调度进程或任务，先到达的先执行，保证公平性。
• 消息队列：生产者将消息放入队尾，消费者从队头取出消息，实现生产者和消费者的解耦。
• 打印机缓冲：多个打印任务按提交顺序排队，先提交的先打印。
• 广度优先搜索（BFS）：借助队列逐层访问图中的结点，先访问的结点先扩展。

下面以任务调度为例，演示队列的实际应用。假设系统中有若干任务按到达顺序排队，每个任务包含编号和所需执行时间，系统依次取出队头任务执行：

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100

// 任务结构体
typedef struct {
int id; // 任务编号
int time; // 所需执行时间
} Task;

// 顺序队列（循环队列）
typedef struct {
Task data[MAXSIZE];
int front; // 队头下标
int rear; // 队尾下标
} TaskQueue;

// 初始化空队列
void InitQueue(TaskQueue *Q) {
Q->front = 0;
Q->rear = 0;
}

// 判空
int IsEmpty(TaskQueue *Q) {
return Q->front == Q->rear;
}

// 判满
int IsFull(TaskQueue *Q) {
return (Q->rear + 1) % MAXSIZE == Q->front;
}

// 入队（任务到达，放入队尾）
int EnQueue(TaskQueue *Q, Task t) {
if (IsFull(Q)) return 0; // 队满，入队失败
Q->data[Q->rear] = t;
Q->rear = (Q->rear + 1) % MAXSIZE;
return 1;
}

// 出队（取出队头任务执行）
int DeQueue(TaskQueue *Q, Task *t) {
if (IsEmpty(Q)) return 0; // 队空，出队失败
*t = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZE;
return 1;
}

int main() {
TaskQueue Q;
InitQueue(&Q);

// 三个任务依次到达
Task t1 = {1, 5};
Task t2 = {2, 3};
Task t3 = {3, 8};
EnQueue(&Q, t1);
EnQueue(&Q, t2);
EnQueue(&Q, t3);

// 依次取出队头任务执行
Task cur;
while (!IsEmpty(&Q)) {
DeQueue(&Q, &cur);
printf("执行任务 %d，耗时 %d 秒\\n", cur.id, cur.time);
}
return 0;
}

运行结果如下：

执行任务 1，耗时 5 秒
执行任务 2，耗时 3 秒
执行任务 3，耗时 8 秒

从输出可以看出，任务严格按照“先到达先执行”的顺序被处理，这正是队列“先进先出”特性的体现。在实际的消息队列系统中，生产者不断将消息入队，消费者不断从队头取出消息处理，两者通过队列解耦，互不阻塞。

6. 栈与队列的对比

栈和队列都是操作受限的线性表，但它们的操作规则截然相反：栈遵循“后进先出”（LIFO），队列遵循“先进先出”（FIFO）。下面从逻辑结构、操作规则、典型应用、底层实现和优缺点五个维度进行对比。

在实际开发中，选择栈还是队列，核心依据是数据的处理顺序：

• 需要“后进先出”处理：选择栈。例如函数调用、括号匹配、表达式求值、撤销操作等场景。
• 需要“先进先出”处理：选择队列。例如任务调度、打印机缓冲、消息队列、广度优先搜索等场景。
• 元素规模可预估：优先选择顺序实现（顺序栈、循环队列），访问效率更高。
• 元素规模动态变化、不确定：优先选择链式实现（链式栈、链式队列），不受固定容量限制。

7. 各数据结构操作的时间复杂度对比

为了更直观地比较顺序表、链表、栈和队列的性能差异，下面从插入、删除、查找和访问四个维度，列出它们在不同情况下的平均和最坏时间复杂度。其中 n 表示当前结构中元素的个数。

从上面的对比可以看出：

• 顺序表：适合需要频繁按下标随机访问、插入和删除较少的场景，例如学生成绩表、通讯录等。
• 链表：适合插入和删除频繁、元素数量动态变化的场景，例如内存管理中的空闲块链表、LRU 缓存淘汰等。
• 栈：适合需要“后进先出”处理的场景，例如函数调用、括号匹配、表达式求值、浏览器的前进后退。
• 队列：适合需要“先进先出”处理的场景，例如任务调度、打印机缓冲、消息队列、广度优先搜索。

8. 总结

本文围绕线性结构，系统介绍了线性表、链表、栈和队列四种基础数据结构。它们都建立在“数据 + 关系 + 操作”的统一框架之上，区别在于逻辑约束、物理实现和适用场景各不相同。

8.1 核心概念回顾

• 线性表：由 n 个相同类型元素组成的有限序列，元素之间是一对一的线性关系，是最基本的线性结构。
• 链表：线性表的链式存储实现，通过指针串联结点，支持单链表、双链表、单向循环链表和双向循环链表四种形态。
• 栈：只允许在栈顶插入和删除的线性表，遵循“后进先出”（LIFO）原则。
• 队列：只允许在队尾插入、在队头删除的线性表，遵循“先进先出”（FIFO）原则。

8.2 主要操作对比

8.3 典型应用场景

• 线性表：适合需要频繁按位置随机访问、且插入删除较少的场景，如学生成绩表、通讯录等。
• 链表：适合插入和删除频繁、元素数量动态变化的场景，如内存管理中的空闲块链表、LRU 缓存淘汰等。
• 栈：适合需要“后进先出”处理的场景，如函数调用、括号匹配、表达式求值、浏览器的前进后退。
• 队列：适合需要“先进先出”处理的场景，如任务调度、打印机缓冲、消息队列、广度优先搜索。

8.4 数据结构选择建议

在实际开发中，选择哪种数据结构应结合访问模式、操作频率和存储规模综合判断：

• 需要随机访问、插入删除少：优先选择顺序存储的线性表（数组），支持 O(1) 下标访问。
• 插入删除频繁、元素数量不确定：优先选择链表，避免移动大量元素，且不受固定容量限制。
• 需要双向遍历：选择双链表；需要循环访问时选择单向循环链表或双向循环链表。
• 数据满足“后进先出”特性：使用栈；若元素规模可预估，用顺序栈更高效，否则用链式栈更灵活。
• 数据满足“先进先出”特性：使用队列；顺序队列注意采用循环队列避免“假溢出”，链式队列则不受容量限制。

掌握这四种基础数据结构，是理解更复杂数据结构（如树、图）和算法设计的重要前提。建议在理解原理的基础上，多动手编写代码验证，逐步培养根据实际问题选择合适数据结构的能力。