一、链表概述
链表是一种常见的线性数据结构,它通过指针将一系列动态分配的节点(Node)串联起来。每个节点通常包含两部分:数据域(Data Field)和指针域(Pointer Field)。数据域存储实际数据,而指针域存储指向下一个节点的指针(对于双向链表,还会有一个指向前一个节点的指针)。相比数组,链表在插入、删除元素时具有更好的灵活性,因为不需要移动元素,只需更改相应节点的指针即可。
二、链表类型
单链表(Singly Linked List) 每个节点只有一个指针,指向下一个节点。最后一个节点的指针通常设置为NULL,表示链表的结尾。
双链表(Doubly Linked List) 每个节点有两个指针,一个指向前一个节点(前驱指针),一个指向后一个节点(后继指针)。双链表在双向遍历、插入和删除操作中更为方便。
循环链表(Circular Linked List) 单链表或双链表的一种变体,其特点是最后一个节点的指针不再指向NULL,而是指向链表的头节点,形成一个环形结构。循环链表适用于需要循环遍历的场景。
三、链表操作
创建链表 初始化链表头节点(通常包含一个空指针),然后通过动态内存分配(如malloc)创建新节点,并将新节点插入到链表中。
插入节点
头插法:在链表头部创建新节点,更新头节点指针。
尾插法:找到链表尾部,创建新节点并更新尾节点的指针。
指定位置插入:找到指定位置的前一个节点,创建新节点并更新前后节点的指针。
删除节点
删除头节点:更新头节点指针,释放头节点内存。
删除指定节点:找到指定节点的前一个节点,更新其指针以跳过待删除节点,然后释放待删除节点内存。
删除尾节点:找到倒数第二个节点,更新其指针为NULL,释放尾节点内存。
遍历链表 从头节点开始,沿着指针逐个访问节点。对于单链表,只能向前遍历;对于双链表,可以向前或向后遍历。
查找节点 从头节点开始,按照一定的查找条件(如根据节点数据或索引)遍历链表,找到满足条件的节点。
合并链表 将两个已排序的链表合并为一个有序链表。
反转链表 改变节点指针方向,使得链表的遍历顺序反转。
四、链表优缺点
优点:
动态分配内存,空间利用率高。
插入、删除操作(除头节点外)时间复杂度为O(1),优于数组。
适用于频繁插入、删除的场景。
缺点:
需要额外的内存空间存储指针。
遍历效率相对数组较低,无法随机访问。
易于产生内存泄漏,需要仔细管理内存。
五、编程实践要点
内存管理:使用
malloc
动态分配节点内存,操作完成后使用free
释放。避免内存泄漏和悬挂指针。空指针检查:对链表操作中涉及的指针进行非空检查,防止空指针解引用引发程序崩溃。
边界条件处理:在插入、删除、查找等操作中,考虑链表为空、只有一个节点等边界情况。
typedef
定义节点结构体:使用typedef
定义节点结构体类型,提高代码可读性。函数封装:将链表的创建、插入、删除、遍历等操作封装为函数,提高代码复用性。
六、示例
单链表
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建链表
Node* create_list() {
return NULL;
}
// 插入节点(尾插法)
void insert(Node** head, int value) {
Node* new_node = (Node*) malloc(sizeof(Node));
new_node->data = value;
new_node->next = NULL;
if (*head == NULL) {
*head = new_node;
} else {
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = new_node;
}
}
// 遍历链表
void traverse(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
puts("NULL");
}
int main() {
Node* list = create_list();
insert(&list, 1);
insert(&list, 2);
insert(&list, 3);
printf("Traversing the list:\n");
traverse(list);
return 0;
}
双链表
#include <stdio.h>
#include <stdlib.h>
// 双链表节点结构定义
typedef struct DNode {
int data;
struct DNode* prev;
struct DNode* next;
} DNode;
// 创建空双链表
DNode* create_dlist() {
return NULL;
}
// 创建新节点
DNode* create_node(int value) {
DNode* new_node = (DNode*) malloc(sizeof(DNode));
new_node->data = value;
new_node->prev = NULL;
new_node->next = NULL;
return new_node;
}
// 头部插入节点
void insert_front(DNode** head, int value) {
DNode* new_node = create_node(value);
if (*head == NULL) {
*head = new_node;
} else {
new_node->next = *head;
(*head)->prev = new_node;
*head = new_node;
}
}
// 尾部插入节点
void insert_back(DNode** head, int value) {
DNode* new_node = create_node(value);
if (*head == NULL) {
*head = new_node;
} else {
DNode* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = new_node;
new_node->prev = temp;
}
}
// 遍历双链表(正向)
void traverse_forward(DNode* head) {
DNode* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
puts("NULL");
}
// 遍历双链表(反向)
void traverse_backward(DNode* head) {
DNode* temp = head;
if (temp != NULL) {
while (temp->next != NULL) {
temp = temp->next;
}
}
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->prev;
}
puts("NULL");
}
int main() {
DNode* dlist = create_dlist();
insert_back(&dlist, 1);
insert_back(&dlist, 2);
insert_back(&dlist, 3);
insert_front(&dlist, 4);
insert_front(&dlist, 5);
insert_front(&dlist, 6);
printf("Forward traversal:\n");
traverse_forward(dlist);
printf("\nBackward traversal:\n");
traverse_backward(dlist);
return 0;
}
循环链表
#include <stdio.h>
#include <stdlib.h>
// 双链表节点结构定义
typedef struct DNode
{
int data;
struct DNode *prev;
struct DNode *next;
} DNode;
// 创建空循环双链表
DNode *create_circular_dlist()
{
return NULL;
}
// 创建新节点
DNode *create_node(int value)
{
DNode *new_node = (DNode *)malloc(sizeof(DNode));
new_node->data = value;
new_node->prev = NULL;
new_node->next = NULL;
return new_node;
}
// 头部插入节点
void insert_front(DNode **head, int value)
{
DNode *new_node = create_node(value);
if (*head == NULL)
{
*head = new_node;
new_node->next = new_node; // 创建单节点循环链表
new_node->prev = new_node; // 更新新节点的prev指针,指向自身
}
else
{
new_node->next = *head;
new_node->prev = (*head)->prev; // 更新新节点的prev指针,指向原头节点的前一个节点
(*head)->prev->next = new_node; // 更新原头节点前一个节点的next指针,指向新节点
(*head)->prev = new_node; // 更新原头节点的prev指针,指向新节点
*head = new_node; // 更新头指针为新节点
}
}
// 尾部插入节点
void insert_back(DNode **head, int value)
{
DNode *new_node = create_node(value);
if (*head == NULL)
{
*head = new_node;
new_node->next = new_node; // 创建单节点循环链表
}
else
{
DNode *temp = *head;
while (temp->next != *head)
{
temp = temp->next;
}
temp->next = new_node;
new_node->prev = temp;
new_node->next = *head;
(*head)->prev = new_node;
}
}
// 遍历循环双链表(正向)
void traverse_forward(DNode *head)
{
if (head == NULL)
{
return;
}
DNode *temp = head;
do
{
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
puts("");
}
// 遍历循环双链表(反向)
void traverse_backward(DNode *head)
{
if (head == NULL)
{
return;
}
DNode *temp = head->prev; // 从头节点的前一个节点开始反向遍历
do
{
printf("%d -> ", temp->data);
temp = temp->prev;
} while (temp != head->prev);
puts("");
}
int main()
{
DNode *cdlst = create_circular_dlist();
insert_front(&cdlst, 1); // 头部插入节点
insert_front(&cdlst, 2); // 头部插入节点
insert_front(&cdlst, 3); // 头部插入节点
insert_back(&cdlst, 4); // 尾部插入节点
insert_back(&cdlst, 5); // 尾部插入节点
insert_back(&cdlst, 6); // 尾部插入节点
printf("Forward traversal:\n");
traverse_forward(cdlst);
printf("\nBackward traversal:\n");
traverse_backward(cdlst);
return 0;
}
评论区