指针与链表
深入讲解链表的原理、实现（单向链表、双向链表、循环链表）及操作（插入、删除、遍历）。
链表是一种重要的数据结构，它通过指针将一系列不连续的内存空间连接起来，以存储数据元素。链表的每个节点通常包含两部分：数据域和指针域。数据域用于存储数据元素，而指针域则用于指向链表中的下一个节点。下面将深入讲解链表的原理、实现（单向链表、双向链表、循环链表）及操作（插入、删除、遍历）。
一、链表的原理
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的主要优点在于插入和删除操作不需要移动大量数据元素，只需修改指针即可，因此效率较高。然而，链表在访问数据时需要从头节点开始逐个遍历，直到找到所需的数据元素，因此随机访问的效率较低。
二、链表的实现
1. 单向链表
原理：单向链表中的每个节点包含一个数据域和一个指针域（通常称为next），指针域用于指向链表中的下一个节点。链表的末尾节点通常将指针域设置为NULL，表示链表的结束。
实现：
定义节点结构体：
typedef struct ListNode { |
int val; // 数据域 |
struct ListNode* next; // 指针域 |
} ListNode; |
基本操作：包括插入、删除和遍历。
插入：在指定位置插入新节点时，需要找到该位置的前一个节点，然后将新节点的next指针指向原位置节点，同时修改前一个节点的next指针指向新节点。
删除：删除指定节点时，需要找到该节点的前一个节点，然后将前一个节点的next指针指向待删除节点的下一个节点，并释放待删除节点的内存。
遍历：从头节点开始，沿着next指针逐个访问链表中的每个节点，直到next指针为NULL。
2. 双向链表
原理：双向链表中的每个节点除了包含数据域和指向下一个节点的指针域外，还包含一个指向前一个节点的指针域（通常称为prev）。这使得双向链表可以从头到尾或从尾到头进行遍历。
实现：
定义节点结构体：
typedef struct DListNode { |
int val; // 数据域 |
struct DListNode* prev; // 指向前一个节点的指针 |
struct DListNode* next; // 指向下一个节点的指针 |
} DListNode; |
基本操作：插入、删除和遍历与单向链表类似，但需要考虑prev指针的修改。
3. 循环链表
原理：循环链表是单向链表的一种变体，其最后一个节点的next指针不是指向NULL，而是指向链表的头节点，形成一个环状结构。循环链表可以从任意节点开始遍历，最终都会回到头节点。
实现：
定义节点结构体与单向链表相同。
基本操作：插入和删除操作需要特别注意保持链表的循环性，即确保最后一个节点的next指针始终指向头节点（或NULL，在某些实现中）。遍历操作与单向链表类似，但需要注意判断遍历结束的条件（通常是回到头节点）。
三、链表的操作
1. 插入操作
单向链表：在指定位置插入新节点，需要找到该位置的前一个节点，并修改相关指针。
双向链表：与单向链表类似，但需要同时修改prev和next指针。
循环链表：与单向链表类似，但需注意保持链表的循环性。
2. 删除操作
单向链表：找到待删除节点的前一个节点，修改其next指针指向待删除节点的下一个节点，并释放待删除节点的内存。
双向链表：与单向链表类似，但需要同时修改prev和next指针。
循环链表：与单向链表类似，但需注意处理特殊情况（如删除头节点或尾节点时）。
3. 遍历操作
单向链表：从头节点开始，沿着next指针逐个访问链表中的每个节点，直到next指针为NULL。
双向链表：可以从头节点开始沿next指针遍历，也可以从尾节点开始沿prev指针遍历。
循环链表：可以从任意节点开始遍历，最终都会回到头节点（或指定的结束节点）。
综上所述，链表是一种重要的数据结构，它通过指针将
指针与链表（扩展）
指针与链表：深入实现与操作
链表作为数据结构中的基石之一，其重要性不言而喻。本文将深入探讨链表的原理、实现（单向链表、双向链表、循环链表）及关键操作（插入、删除、遍历），并辅以丰富的代码示例，以增强技术深度。
一、链表的原理
链表通过指针将一系列不连续的内存空间连接起来，形成逻辑上连续的数据结构。其核心优势在于插入和删除操作的高效性，以及灵活的内存管理。然而，链表在随机访问时效率较低，需要从头节点开始遍历。
二、链表的实现
1. 单向链表
定义节点结构体：
typedef struct ListNode { |
int val; // 数据域 |
struct ListNode* next; // 指针域，指向下一个节点 |
} ListNode; |
基本操作实现：
插入操作：
在单向链表的第index位置插入新节点，需要处理边界条件（如index为0或链表为空）。
ListNode* insertAtIndex(ListNode* head, int index, int val) { |
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); |
newNode->val = val; |
newNode->next = NULL; |
|
if (index == 0) { |
newNode->next = head; |
return newNode; |
} |
|
ListNode* curr = head; |
for (int i = 0; i < index - 1 && curr != NULL; i++) { |
curr = curr->next; |
} |
|
if (curr == NULL) return head; // 超出链表长度 |
|
newNode->next = curr->next; |
curr->next = newNode; |
return head; |
} |
删除操作：
删除链表中值为val的第一个节点，需要返回新的头节点以处理删除头节点的情况。
ListNode* deleteNode(ListNode* head, int val) { |
ListNode* dummy = (ListNode*)malloc(sizeof(ListNode)); |
dummy->next = head; |
ListNode* curr = dummy; |
|
while (curr->next != NULL && curr->next->val != val) { |
curr = curr->next; |
} |
|
if (curr->next != NULL) { |
ListNode* temp = curr->next; |
curr->next = temp->next; |
free(temp); |
} |
|
head = dummy->next; |
free(dummy); |
return head; |
} |
遍历操作：
遍历链表并打印每个节点的值。
void printList(ListNode* head) { |
ListNode* curr = head; |
while (curr != NULL) { |
printf("%d ", curr->val); |
curr = curr->next; |
} |
printf("\n"); |
} |
2. 双向链表
定义节点结构体：
typedef struct DListNode { |
int val; // 数据域 |
struct DListNode* prev; // 指向前一个节点的指针 |
struct DListNode* next; // 指向下一个节点的指针 |
} DListNode; |
基本操作（以插入为例）：
双向链表的插入操作需要同时更新prev和next指针。
DListNode* insertAtIndexBi(DListNode* head, int index, int val) { |
// 类似单向链表插入，但需处理prev指针 |
// ... 省略详细代码，基本逻辑与单向链表相似 |
} |
3. 循环链表
定义节点结构体与单向链表相同。
基本操作（以遍历为例）：
循环链表的遍历需要特别处理结束条件，通常是判断是否回到头节点。
void printCircularList(DListNode* head) { |
if (head == NULL) return; |
DListNode* curr = head; |
do { |
printf("%d ", curr->val); |
curr = curr->next; |
} while (curr != head); // 回到头节点时结束 |
printf("\n"); |
} |
三、总结
链表作为动态数据结构，其灵活性和高效性在数据处理中尤为重要。通过深入理解和实践链表的原理及操作，能够显著提升编程能力和算法设计水平。本文提供了详细的链表实现代码，包括单向链表、双向链表和循环链表的插入、删除和遍历操作，希望为读者提供坚实的理论基础和实践参考
