本文主要介绍一下链表的特点和使用场景，并且用C语言基于链表实现了队列（FIFO）。
链表是一种灵活的数据结构，适合用于需要频繁插入和删除操作的场景，但在需要快速随机访问的情况下，数组或其它数据结构可能更为合适。
特点
动态大小
链表可以根据需要动态增长或缩小，不需要事先定义大小。
非连续存储
链表中的节点在内存中不必连续存储，每个节点通过指针连接。
插入和删除效率高
在链表中插入或删除节点的时间复杂度为 O(1)，只需调整指针即可，而在数组中可能需要移动大量元素，时间复杂度为 O(n)。
访问效率低
链表的随机访问效率较低，要访问某个节点需要从头遍历，时间复杂度为 O(n)。
适用场景
实现队列和栈
链表可以方便地实现队列（FIFO）和栈（LIFO）等数据结构，因为它们需要频繁的插入和删除操作。
动态数据存储
当数据量不确定且需要频繁变化时，链表是一种合适的选择，例如实现动态数组的替代品。
图和树的实现
链表可用于表示图的邻接表和树的节点结构，方便存储和遍历。
内存管理
在需要频繁分配和释放内存的应用中，链表可以有效管理内存，避免内存碎片。
使用示例
下面是使用链表实现队列（FIFO）的 C 语言示例代码。包括基本的队列操作，如入队（enqueue）、出队（dequeue）。
#include
#include
// 定义链表节点
struct Node {
int data;
struct Node* next;
};
// 定义队列结构
struct Queue {
struct Node* front; // 队列前端
struct Node* rear; // 队列后端
};
// 创建新的节点
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 初始化队列
struct Queue* createQueue() {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->front = NULL;
queue->rear = NULL;
return queue;
}
// 入队操作
void enqueue(struct Queue* queue, int data) {
struct Node* newNode = createNode(data);
if (queue->rear == NULL) {
// 如果队列为空，前端和后端都指向新节点
queue->front = newNode;
queue->rear = newNode;
} else {
// 否则，将新节点添加到队列后端
queue->rear->next = newNode;
queue->rear = newNode;
}
printf("%d 入队\n", data);
}
// 出队操作
int dequeue(struct Queue* queue) {
if (queue->front == NULL) {
printf("队列为空，无法出队\n");
return -1; // 表示队列为空
}
struct Node* temp = queue->front;
int data = temp->data;
queue->front = queue->front->next;
// 如果队列变为空，更新后端指针
if (queue->front == NULL) {
queue->rear = NULL;
}
free(temp);
printf("%d 出队\n", data);
return data;
}
// 打印队列内容
void printQueue(struct Queue* queue) {
struct Node* current = queue->front;
if (current == NULL) {
printf("队列为空\n");
return;
}
printf("队列内容: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// 主函数
int main() {
struct Queue* queue = createQueue();
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
printQueue(queue);
dequeue(queue);
printQueue(queue);
dequeue(queue);
printQueue(queue);
dequeue(queue);
printQueue(queue);
dequeue(queue); // 尝试从空队列出队
// 释放队列内存（可选）
free(queue);
return 0;
}
代码逻辑比较清晰，就不做过多解释了。