C 语言链表数据结构

一、链表概述

链表是 C 语言中一种常用且灵活的数据结构，它通过节点的链接方式存储数据元素。每个节点包含数据域和指向下一个节点的指针域。与数组不同，链表在内存中并非连续分配空间，这种独特的存储方式赋予链表诸多优势，如动态扩展性强、插入删除操作高效等。

二、链表分类

（一）单链表

单链表是最简单的链表形式，每个节点只有一个指向后继节点的指针。在单链表中，从头部节点开始可以访问整个链表。其特点是结构简单，但查找元素需要从头节点依次遍历，时间效率较低。

（二）双链表

双链表在单链表基础上为每个节点增加了一个指向前驱节点的指针。这使得双链表可以从前往后和从后往前双向遍历，插入和删除操作在某些情况下更为高效，但同时也增加了存储空间和部分操作的复杂度。

（三）循环链表

循环链表的特点是表头节点的指针域指向尾节点，尾节点的指针域指向表头节点（对于单循环链表）或前驱节点（对于双循环链表），形成一个环状结构。这种结构在需要循环处理数据或某些特定应用场景下（如多线程任务调度等）具有独特优势。

三、链表的基本操作实现

（一）节点定义

以单链表为例：

typedef struct Node {int data;                 // 数据域，可根据实际需求定义类型struct Node* next;        // 指针域，指向下一个节点
} Node;

双链表节点定义：

typedef struct Node {int data;struct Node* next;        // 指向后继节点struct Node* prev;        // 指向前驱节点
} Node;

（二）链表初始化

初始化单链表：

Node* initSingleLinkedList() {Node* head = (Node*)malloc(sizeof(Node));if (head == NULL) {printf("内存分配失败！\n");exit(1);}head->next = NULL;        // 初始化头节点的指针域为 NULLreturn head;
}

初始化双链表：

Node* initDoubleLinkedList() {Node* head = (Node*)malloc(sizeof(Node));if (head == NULL) {printf("内存分配失败！\n");exit(1);}head->next = NULL;head->prev = NULL;        // 初始化头节点的前后指针域return head;
}

（三）插入操作

单链表尾插法：

void insertAtTailSingle(Node* head, int value) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = NULL;Node* temp = head;while (temp->next != NULL) {    // 找到尾节点temp = temp->next;}temp->next = newNode;           // 将新节点插入尾部
}

1. 双链表头插法：

void insertAtHeadDouble(Node* head, int value) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = head->next;newNode->prev = head;if (head->next != NULL) {       // 若链表非空head->next->prev = newNode; // 更新原头节点后继节点的前驱指针}head->next = newNode;           // 将新节点插入头部
}

（四）删除操作

单链表删除指定值节点：

void deleteNodeSingle(Node* head, int value) {Node* temp = head;while (temp->next != NULL) {if (temp->next->data == value) {    // 找到待删除节点Node* delNode = temp->next;temp->next = delNode->next;     // 跳过待删除节点free(delNode);                  // 释放内存return;}temp = temp->next;}printf("未找到值为 %d 的节点，无法删除。\n", value);
}

1. 双链表删除指定节点（已知节点指针）：

void deleteNodeDouble(Node* node) {if (node == NULL || node == head) {     // 若节点为空或为头节点则不删除printf("无法删除头节点或空节点。\n");return;}node->prev->next = node->next;          // 更新前驱节点的后继指针if (node->next != NULL) {               // 若待删除节点不是尾节点node->next->prev = node->prev;      // 更新后继节点的前驱指针}free(node);                             // 释放内存
}

（五）查找操作

单链表查找指定值节点：

Node* searchNodeSingle(Node* head, int value) {Node* temp = head->next;while (temp != NULL) {if (temp->data == value) {return temp;    // 找到则返回节点指针}temp = temp->next;}return NULL;            // 未找到返回 NULL
}

1. 双链表查找指定值节点：

Node* searchNodeDouble(Node* head, int value) {Node* temp = head->next;while (temp != NULL) {if (temp->data == value) {return temp;}temp = temp->next;}// 也可从尾部向前查找temp = head->prev;while (temp != NULL) {if (temp->data == value) {return temp;}temp = temp->prev;}return NULL;
}