单向链表的概念

对于顺序存储的结构，最大的缺点就是：插入 和 删除 的时候需要移动大量的元素。

而链表是有一个一个节点组成，每个节点通过链接关系串联，每个节点都有一个后继节点，最后的后继节点为空节点。

节点在内存中的地址不是连续的而是离散的，仅通过指针将每个节点串联起来。

由链接关系 A -> B 组织起来的两个结点，B 被称为 A 的后继结点，A 被称为 B 的前驱结点。链表分为 单向链表、双向链表、循环链表等等。本文只介绍单向链表。

一个链表结点由两部分组成：数据域 和 指针域。数据可以是任意类型，由编码的人自行指定。指针域 指向 后继结点 的地址。一个结点包含的两部分如下图所示：

以下是单向链表的定义创建及销毁的C语言实现

                
#include <stdio.h>
#include <stdlib.h>
 
#define ele_type int
 
// 单向链表节点定义
typedef struct LinkedNode {
ele_type data;
struct LinkedNode* next;
}LinkedNode;
 
// 单向链表定义
typedef struct LinkedList {
struct LinkedNode* head;
size_t size;
}LinkedList;
 
// 单向链表的创建
void LinkedList_Init(LinkedList* list) {
list->head = NULL;
list->size = 0;
return;
}
 
// 单向链表的销毁
void LinkedList_Destroy(LinkedList* list) {
while (list->head) {
LinkedNode* tmp = list->head;
list->head = list->head->next;
free(tmp);
}
list->size = 0;
return;
}
                
c
                

                    
                    
                
                

单向链表的元素插入

单向链表的元素插入就是给定索引和元素，将元素插入对应索引中。

假设要在索引为4的位置上插入元素5，就需要使新节点的指针指向原先位置4的节点，并且令原先位置3的节点的指针指向新节点，这样新节点就取代了位置4的节点，如图。

元素插入的步骤

1. 判断插入位置是否合法（比如索引小于0或者大于链表目前大小）。
2. 对给定元素，生成新链表节点。
3. 如果插入位置为0，则直接让新节点指向头节点，并且设置新节点为头节点。
4. 如果插入位置不是0，则遍历到插入位置前一个位置，并且插入新节点。
5. 更新链表大小。

                
// 单向链表的插入
void LinkedList_Insert(LinkedList* list, int index, ele_type value) {
if (index < 0 || index > list->size) {
printf("非法索引\n");
return;
}
 
// 创建新节点
LinkedNode* new_node = (LinkedNode*)malloc(sizeof(LinkedNode));
new_node->data = value;
 
if (index == 0) {
new_node->next = list->head;
list->head = new_node;
}
else {
// 找到第i-1个节点
LinkedNode* current = list->head;
for (int i = 0; i < index - 1; i++) {
current = current->next;
}
LinkedNode* next = current->next;
 
// 更新节点
current->next = new_node;
new_node->next = next;
}
list->size++;
return;
}
                
c
                

                    
                    
                
                

单向链表的删除

单向链表的删除，就是给定一个索引并且删除对应索引的节点。

例如要删除索引为4的节点，则从前往后遍历链表，当遍历到索引为3节点，将其指针指向索引为5的节点，然后将索引为4的节点释放掉，这样索引为5的节点索引就会变成4。

元素删除的步骤

1. 判断删除位置是否合法，如果不合法则抛出异常。
2. 如果删除位置为首个结点，直接把链表头更新为它的后继结点。
3. 如果删除位置非首个结点，则遍历到要删除位置的前一个结点，并且把前一个结点的后继结点设置为它后继的后继。
4. 更新链表的大小。

                
// 单向链表的元素删除
void LinkedList_Delete(LinkedList* list, int index) {
if (index < 0 || index > list->size) {
printf("非法索引\n");
return;
}
 
if (index == 0) {
LinkedNode* tmp = list->head;
list->head = list->head->next;
free(tmp);
}
else {
LinkedNode* current = list->head;
for (int i = 0; i < index - 1; i++) {
current = current->next;
}
LinkedNode* tmp = current->next;
current->next = tmp->next;
free(tmp);
}
list->size--;
return;
}
                
c
                

                    
                    
                
                

单向链表的查找

单向链表的元素查找，就是查找指定元素x是否存在，如果存在则返回该节点，不存在则返回NULL。因为需要遍历整个链表对比，时间复杂度为O(n)。

例如我们要求查找值为8的节点，则从链表头开始遍历，直到遍历到值为8的节点后返回。

元素查找的步骤

1. 遍历整个链表对比查找元素，相等则返回当前遍历到的节点。
2. 遍历完链表没有找到，返回NULL。

                
// 单向链表的元素查找
LinkedNode* LinkedList_Find(LinkedList* list, ele_type value) {
LinkedNode* current = list->head;
while (current) {
if (current->data == value) {
return current;
}
current = current->next;
}
return NULL;
}
                
c
                

                    
                    
                
                

单向链表元素索引

单向链表元素索引指的是给定索引值i，找到其位置并返回节点，时间复杂度为O(n)。

例如给定索引值5查找元素，如图。

元素索引的步骤

1. 判断索引是否合法。
2. 通过索引遍历访问获取元素。

                
// 单向链表的元素索引
LinkedNode* LinkedList_Get(LinkedList* list, int index) {
if (index < 0 || index > list->size) {
printf("非法索引\n");
return NULL;
}
 
LinkedNode* current = list->head;
for (int i = 0; i < index; i++) {
current = current->next;
}
return current;
}
                
c
                

                    
                    
                
                

单向链表元素修改

元素修改即修改对应节点为新的值。

例如给定索引5并修改成指定值，如图，和单向链表的元素索引很类似只不过修改了值。

元素修改的步骤

1. 通过元素索引获得对应节点，并修改为新值。

                
// 单向链表的元素修改
void LinkedList_Update(LinkedList* list, int index, ele_type value) {
LinkedNode* node = LinkedList_Get(list, index);
if (node != NULL) {
node->data = value;
}
return;
}
                
c
                

                    
                    
                
                

单向链表的打印

单向链表打印即为遍历所有节点打印出所有节点的数据，打印完最后的节点再打印NULL表示结束。

                
// 单向链表的打印
void LinkedList_Printf(LinkedList* list) {
LinkedNode* current = list->head;
while (current) {
printf("%d->", current->data);
current = current->next;
}
printf("NULL\n");
return;
}
                
c
                

                    
                    
                
                

实验

实验代码的正确性。

                
// 实验
int main() {
// 创建一个单向链表
LinkedList list;
LinkedList_Init(&list);
 
// 插入元素
for (int i = 0; i < 5; i++) {
LinkedList_Insert(&list, i, i);
}
 
// 打印原始链表
printf("原始链表:\n");
LinkedList_Printf(&list);
 
// 删除第2个节点
printf("删除第2个节点\n");
LinkedList_Delete(&list, 2);
 
// 更新第1个节点
printf("更新第1个节点的值为10\n");
LinkedList_Update(&list, 1, 10);
 
// 查找值为10和值为30的节点
printf("查找值为10和30的节点\n");
ele_type Find_List[] = { 10, 30 };
int len = sizeof(Find_List) / sizeof(Find_List[0]);
for (int i = 0; i < len; i++) {
LinkedNode* node = LinkedList_Find(&list, Find_List[i]);
if (node != NULL)
{
printf("找到值为%d的节点\n", Find_List[i]);
}
else {
printf("没有找到值为%d的节点\n", Find_List[i]);
}
}
 
// 获取第2个节点(&list, 2)
printf("获取索引为2的节点\n");
LinkedNode* node = LinkedList_Get(&list, 2);
if (node != NULL) {
printf("找到索引为2的节点:%d\n", node->data);
}
 
// 打印更新后的链表
printf("更新后的链表:");
LinkedList_Printf(&list);
 
return 0;
}
                
c
                

                    
                    
                
                

References

1. 整理于英雄哪里出来知识星球内容