一、链表
1.线性链表：
链表是一组存储线性表的数据元素存储单元;
由若干个节点组成，结点包括两个域:
其中存储数据元素信息的称为数据域;存储直接后继存储位置有域称为指针域。
2.链表的基本操作：
（1）链表存储结构
typedef int ElemType;
typedef struct node
{ElemType data; //数据域struct node *next; //指针域
} Node;
（2）单链表-初始化
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}
int main ()
{Node *list = initList();return 1;
}
（3）单链表-头插法
int insertHead (Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;
}
int main ()
{Node *list = initList();insertHead(list, 10);insertHead(list, 20);
}
（4）单链表-遍历
void listNode (Node* L)
{Node *p = L->next;while (p != NULL){printf ("%dn", p->data) ;p = p->next;}printf("\n");
}
（5）单链表-获取链表长度
int listLength (Node *L)
{Node *p = L;int len = 0;while (p != NULL){p = p->next;len++;}return len;
}
（6）单链表-尾插法
Node* get_tail (Node *L)
{Node *p = L;while (p->next != NULL){p = p->next;}return p;
}
（7）单链表-在指定位置插入数据
int insertNode(Node *L, int pos, ElemType e)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL)return 0;}Node *q = (Node*)malloc(sizeof(Node));q->data = e;q->next = p->next;p->next = q;return 1;
}
（8）单链表-删除节点
int deleteNode(Node *L, int pos)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next;p->next = q->next;free(q);return 1;
}
（9）单链表-释放链表
void freeList (Node *L)
{Node *p = L->next;Node *q;while (p != NULL){q = p->next;free (p) ;p = q;}L->next = NULL;
}
3.双向链表：
链式存储结构的节点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针向后寻查其他节点。若要寻查结点的直接前驱、则必须从表头指针出发。换句话说,在单链表中,查找直接后继的执行时间为O(1),而查找直接前驱的执行时间为O(n)。为克服单链表这种单向性的缺点,可利用双向链表。在双向链表的节点中有两个指针域,一个指向直接后继,另一个指向直接前驱。
双向链表的结构
typedef int ElemType;typedef struct node
{ElemType data;struct node *prev, *next; //prev为前驱结点，next为后继结点
} Node;
二、栈
1.栈(stack)是限定仅在表尾进行插入或删除操作的线性表。
因此对栈来说,表尾端有其特殊含义,称为栈顶(top),相应地,表头端称为栈底(bottom)。不含元素的空表称为空栈。
假设S=(a1,a2,…,an),则称a1为栈底元素,an为栈顶元素。栈中元素按a1,a2,…,an的次序进栈,退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按照后进先出的原则进行的。
因此,栈又称为后进先出(Last In First Out,LIFO)的线性表。
栈是限制插入和删除操作只能在一个位置进行的表,该位置是表的末端,叫作栈顶(top)。对栈的基本操作有进栈(push)和出栈(Pop),前者相当于插入,后者则是删除最后插入的元素。
2.栈的基本操作：
（1）栈的链式结构实现：
typedef int ElemType;
typedef struct stack
{ElemType data;struct stack *next;
} Stack;
（2）栈的链式结构实现-初始化：
typedef int ElemType;
typedef struct stack
{ElemType data;struct stack *next;
} Stack;
Stack* initStack ()
{Stack *s = (Stack*)malloc(sizeof(Stack));s->data = 0;s->next = NULL;return s;
}
（3）栈的链式结构实现-判断栈是否为空
int isEmpty (Stack *s)
{if (s->next == NULL){printf("空的\n");return 1;}else{return 0;}
}
（4）栈的链式结构实现-进栈/压栈
int push (Stack *s, ElemType e)
{Stack *p = (Stack*)malloc(sizeof(Stack));p->data = e;p->next = s->next;s->next = p;return 1;
}
（5）栈的链式结构实现-出栈
int pop(Stack *s, ElemType *e)
{if (s->next == NULL){printf("空的\n");return 0;}*e = s->next->data;Stack *q = s->next;s->next = q->next;free (q) ;return 1;
}
（6）栈的链式结构实现-获取栈顶元素
int getTop(Stack *s, ElemType *e)
{if (s->next == NULL){printf("空的\n");return 0;}*e = s->next->data;return 1;
}
三、队列
1.队列(queue)是一种先进先出的线性表。
它只允许在表的一端进行插入,而在另一端删除元素。在队列中,允许插入的一端称为队尾,允许删除的一端则称为队头。假设队列为q=(a1,a2,…,an),那么,a1就是队头元素,an就是队尾元素。
队列中的元素是按照a1,a2,…,an的顺序进入的,退出队列也只能按照这个次序依次退出,也就是说,只有在a1,a2,…,an-1都离开队列之后,an才能退出队列。
2.队列的基本操作：
（1）队列的链式结构-初始化
Queue* initQueue ()
{Queue *q = (Queue*) malloc(sizeof (Queue));QueueNode *node = (QueueNode*)malloc(sizeof (QueueNode)) ;node->data = 0;node->next = NULL;q->front = node;q->rear = node;return q;
}
（2）队列的链式结构
typedef struct QueueNode
{ElemType data;struct QueueNode *next;
} QueueNode;
typedef struct
{QueueNode *front;QueueNode *rear;
} Queue;
（3）队列的链式结构-初始化
Queue* initQueue ()
{Queue *q = (Queue*)malloc(sizeof (Queue));QueueNode *node = (QueueNode*)malloc(sizeof (QueueNode));node->data = 0;node->next = NULL;q->front = node;q->rear = node;return q;
}
（4）队列的链式结构-判断队列是否为空
int isEmpty (Queue *q)
{if (q->front == q->rear){return 1;}else{return 0;}
}
（5）队列的链式结构-入队
void equeue (Queue *q, ElemType e)
{QueueNode *node = (QueueNode*) malloc(sizeof (QueueNode)) ;node->data = e;node->next = NULL;q->rear->next = node;q->rear = node;
}
（6）队列的链式结构-出队
int dequeue(Queue *q, ElemType *e)
{QueueNode *node = q->front->next;*e = node->data;q->front->next = node->next;if (q->rear == node){q->rear = q->front;}free (node) ;return 1;
}
（7）队列的链式结构-获取队头元素
ElemType getFront (Queue *q)
{if (isEmpty (q)){printf("空的\n");return 0;}return q->front->next->data;
}
四、总结
1.基本操作的实现共性与差异
（1）共性
1.存储基础：链表、栈（链式）、队列（链式）均基于节点 + 指针的链式存储结构，通过动态内存分配（malloc）创建节点，借助指针维护元素间的逻辑关系，最终都需通过free释放内存以避免泄漏。
2.初始化逻辑：三者初始化均需创建头节点（或头指针），并将指针域置空（NULL），为后续操作建立初始的空结构。
3.遍历 / 访问逻辑：都需通过指针遍历节点实现元素访问，且访问过程中需判断指针是否为空以防止越界。
（2）差异
| 结构 | 核心操作位置 | 核心操作 | 时间复杂度（核心操作） | 典型应用场景 |
|---|---|---|---|---|
| 单链表 | 任意位置 | 头插、尾插、指定位置插入 / 删除 | 插入 / 删除 O (1)（已知位置）、遍历 O (n) | 动态数据存储、不定长数据管理 |
| 双向链表 | 任意位置 | 前驱 / 后继节点的查找与操作 | 查找前驱 O (1)、其他同单链表 | 需频繁查找前驱的场景（如链表排序） |
| 栈（链式） | 栈顶 | 压栈、出栈 | 压栈 / 出栈 O (1) | 表达式求值、函数调用栈、回溯算法 |
| 队列（链式） | 队尾（插入）、队头（删除） | 入队、出队 | 入队 / 出队 O (1) | 任务排队、消息队列、广度优先搜索 |
2.实现中的注意事项与易错点
(1)内存管理：链式结构中每次创建节点都需通过malloc分配内存，操作完成后必须通过free释放节点，否则会导致内存泄漏；同时需避免野指针。
(2)边界条件判断：
1.链表：插入 / 删除时需判断位置是否合法、遍历到链表尾部时需判断p->next是否为空；
2.栈：出栈和获取栈顶元素时需先判断栈是否为空；
3.队列：出队时需判断队列是否为空，且当最后一个节点出队时需将队尾指针重置为队头指针，避免野指针。
(3)指针操作顺序：插入节点时需先维护后继节点的指针关系，再修改前驱节点的指针，否则会导致链表断裂。