当前位置：首页 > news >正文

数据结构-线性表-单链表

news 2025/11/25 0:01:21

一、了解单链表

1. 单链表的定义

单链表是一种线性数据结构，由一系列节点构成，每个节点包含两个部分：数据域和指向下一个节点的指针。在单链表中，头指针指向第一个节点，最后一个节点的指针指向 NULL，表示链表的结束。

2. 单链表的优缺点：

优点

动态大小：单链表的大小可以动态变化，根据需要可以随时增加或减少节点，避免了固定大小的限制。
插入和删除效率高：在已知位置的情况下，插入和删除操作只需修改节点的指针，不需要移动其他元素，时间复杂度为 O(1)。
内存利用率高：相较于顺序表，单链表在内存管理上更加灵活，可以减少内存浪费。
无需预分配内存：不需要在创建时分配固定大小的内存，适合处理不确定数量的数据。

缺点

随机访问效率低：单链表不支持通过索引直接访问元素，查找特定元素需要从头遍历，时间复杂度为 O(n)。
额外内存开销：每个节点除了存储数据外，还需要存储指针，增加了内存开销。
复杂性增加：相较于顺序表，单链表的实现和操作更为复杂，尤其在处理指针时容易出现错误。
缓存局部性差：由于节点在内存中不连续存储，可能导致缓存命中率降低，从而影响访问速度。

二、单链表的基础操作（C语言）

1. 单链表节点类型

// 单链表节点类型
typedef struct LNode {			// 定义单链表的类型int data;					// 数据struct LNode* next;			// 指针 - 指向下一个节点
} LNode, * LinkList;

LNode：
- 这是对 struct LNode 的别名。通过 typedef，你可以使用 LNode 来代替 struct LNode，这样在代码中使用时就不需要每次都写 struct 关键字。
- 例如，定义一个节点时，你可以直接写 LNode node; 而不是 struct LNode node;。
* LinkList：
- 这是对指向 LNode 类型的指针的别名。LinkList 代表一个指向 LNode 结构的指针，通常用于表示链表的头指针。
- 例如，定义一个链表时，你可以写 LinkList list;，这实际上是定义了一个指向 LNode 的指针，通常用于指向链表的头节点。

2. 单链表初始化


// 链表初始化
// 带头节点
bool InitList(LinkList* L) {*L = (LNode*)malloc(sizeof(LNode)); // 分配内存if (*L == NULL) return false; // 检查内存分配是否成功(*L)->next = NULL; // 初始化 next 指针为 NULLreturn true;
}
/*
// 不带头结点的单链表初始化
bool InitList(LinkList* L) {*L = NULL; // 将链表指针初始化为 NULLreturn true; // 返回成功
}
*/

2. 求表长的操作

时间复杂度 O(n);


// 求表长（不算头结点）
int Length(LinkList L) { // 参数类型改为 LinkListint i = 0;LNode* p = L ->next; // 直接将 L 赋值给 pwhile (p != NULL) { // 遍历直到 p 为 NULLi++;p = p->next; // 移动到下一个节点}return i;
}

3. 按序号查找节点

时间复杂度 O(n);

// 按序号查找节点
LNode* GetElem(LinkList L, int i) {// 检查索引 i 是否有效，i 必须在 1 到 Length(L) 的范围内if (i < 1 || i > Length(L)) return NULL;// 从头节点的下一个节点开始LNode* p = L->next;int j = 1; // 初始化计数器 j，从 1 开始// 遍历链表，直到找到第 i 个节点或到达链表末尾while (p != NULL && j < i) {p = p->next; // 移动到下一个节点j++; // 计数器自增}// 返回指向第 i 个节点的指针，如果没有找到则返回 NULLreturn p;
}

4. 按值查找表节点

时间复杂度 O(n);

// 按值查找表节点  
// 参数:  
// L - 指向链表头结点的指针（头结点不存储有效数据，仅作为链表的起点）  
// e - 要查找的元素值  
// 返回值:  
// 返回指向第一个数据域等于e的节点的指针；如果链表中不存在这样的节点，则返回NULL  
LNode* LocateElem(LinkList L, int e) {  LNode* p = L->next; // 从头结点的下一个节点（即链表的第一个实际数据节点）开始遍历  // 遍历链表，直到p为NULL（即到达链表末尾）  while (p != NULL) {  if (p->data == e) { // 如果当前节点的数据域等于e  break; // 则找到目标节点，跳出循环  }  p = p->next; // 否则，移动到链表的下一个节点继续查找  }  // 返回找到的节点指针（如果找到）或NULL（如果未找到）  return p;  
}

5. 插入节点操作

// 插入节点操作
bool ListInsert(LinkList L, int i, int e) {// 检查插入位置是否合法// i < 1 表示插入位置在链表前面，i > Length(L) + 1 表示超出链表尾部if (i < 1 || i > Length(L) + 1) return false;LNode* p = L; // 从链表头节点开始int j = 0; // 初始化计数器 j，用于遍历链表// 遍历链表，找到第 i-1 个节点while (j < i - 1) {p = p->next; // 移动到下一个节点j++; // 计数器自增}// 创建新节点并分配内存LNode* newNode = (LNode*)malloc(sizeof(LNode));// 检查内存分配是否成功if (newNode == NULL) return false; newNode->data = e; // 设置新节点的数据newNode->next = p->next; // 新节点的下一个指向 p 的下一个节点p->next = newNode; // 将 p 的下一个节点指向新节点return true; // 插入成功，返回 true
}

6. 删除节点操作

bool ListDelete(LinkList L, int i, int *e) {  if (i < 1 || i > Length(L)) return false; // 检查i是否在有效范围内（不包括头结点）  LNode* p = L; // 从头结点开始，但p实际上会移动到第i-1个数据节点  int j = 0;  while (j < i - 1) { // 循环直到p指向第i-1个数据节点  p = p->next;  j++;  }  LNode* q = p->next; // q指向要删除的节点（即第i个数据节点）  if (q == NULL) {  // 理论上，由于前面的检查，这里不应该执行。但为了代码的健壮性，可以保留或添加错误处理  return false;  }  p->next = q->next; // 绕过q，将p的next指向q的next  *e = q->data; // 保存q的数据到e指向的位置  free(q); // 释放q的内存  return true; // 删除成功  
}

7. 头插法建立单链表


// 头插法建立链表  
// 接收一个已经初始化但可能为空的链表头节点L，并通过用户输入来向链表中插入数据  
// 输入9999时结束插入，并返回更新后的链表头节点L  
LinkList List_HandInsert(LinkList L) {int new_data = 0;LNode* new_Node; // 用于指向新创建的节点的指针  // 循环直到用户输入9999为止  while (new_data != 9999) {printf("请输入需要插入的数据（输入9999结束）：");scanf("%d", &new_data); // 读取用户输入的数据  if (new_data == 9999) break; // 如果输入的是9999，则跳出循环  // 为新节点分配内存  new_Node = (LNode*)malloc(sizeof(LNode));if (new_Node == NULL) {printf("空间不足\r\n"); // 如果内存分配失败，打印错误信息  return L; // 并返回当前的链表头节点L（此时链表可能未被修改）  }// 设置新节点的数据域  new_Node->data = new_data;// 将新节点插入到链表的头部（即头节点之后）  // 首先，将新节点的next指针指向当前的第一个节点（L->next）  new_Node->next = L->next;// 然后，将头节点的next指针指向新节点，这样新节点就变成了链表的第一个有效节点  L->next = new_Node;}// 循环结束后，返回更新后的链表头节点L  return L;
}

8. 尾插法建立链表


// 尾插法向链表中插入节点  
// LinkList 是链表的类型，通常是一个指向链表头节点的指针  
// 返回值为更新后的链表头节点指针  
LinkList List_TailInsert(LinkList L) {// p 用于遍历链表，初始时指向链表头节点  // 注意：如果链表为空，p 也将指向空指针（即链表头节点为空）  LNode* p = L;int new_data = 0; // 用于存储用户输入的数据  LNode* new_Node; // 用于指向新创建的节点  // 循环直到用户输入非零值且非9999的数据  while (1) {printf("请输入需要插入的数据（输入9999结束）：");scanf("%d", &new_data); // 读取用户输入的数据  // 如果用户输入了9999，则跳出循环  if (new_data == 9999) break;// 为新节点分配内存  new_Node = (LNode*)malloc(sizeof(LNode));// 检查内存分配是否成功  if (new_Node == NULL) {printf("空间不足\r\n"); // 如果内存分配失败，打印错误信息  return L; // 并返回当前的链表头节点L（此时链表可能未被修改）  }// 设置新节点的数据域  new_Node->data = new_data;// 将p的next指针指向新节点，实现链表的连接  p->next = new_Node;// 新节点的next指针设为NULL，表示它是链表的最后一个节点  new_Node->next = NULL;// 更新p指针，使其指向链表的最后一个节点，以便下一次插入  p = p->next;}// 循环结束，返回更新后的链表头节点  return L;
}// 注意：  
// 1. 此函数假设L是一个有效的链表头节点指针，即使链表为空（即L为NULL），函数也能正确处理（尽管这通常不是最佳实践，因为空链表通常应由一个哑节点来表示）。  
// 2. 如果L为NULL且链表应包含哑节点，则需要在函数开始时检查L是否为NULL，并相应地初始化L。  
// 3. 此函数通过修改链表头节点的next指针的链接来实现插入，因此不需要传入链表的尾节点指针。  
// 4. 如果链表包含哑节点，则p应初始化为L->next，并且在函数开始时需要确保L不是NULL。

三、总代码（C语言）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// 单链表节点类型
typedef struct LNode {int data; // 数据struct LNode* next; // 指向下一个节点的指针
} LNode, * LinkList;// 链表初始化
// 带头节点
bool InitList(LinkList* L) {*L = (LNode*)malloc(sizeof(LNode)); // 分配内存if (*L == NULL) return false; // 检查内存分配是否成功(*L)->next = NULL; // 初始化 next 指针为 NULLreturn true;
}
/*
// 不带头结点的单链表初始化
bool InitList(LinkList* L) {*L = NULL; // 将链表指针初始化为 NULLreturn true; // 返回成功
}
*/// 求表长
int Length(LinkList L) { // 参数类型改为 LinkListint i = 0;LNode* p = L ->next; // 直接将 L 赋值给 pwhile (p != NULL) { // 遍历直到 p 为 NULLi++;p = p->next; // 移动到下一个节点}return i;
}// 按序号查找节点
LNode* GetElem(LinkList L, int i) {if (i < 1 || i > Length(L)) return NULL;LNode* p = L->next;int j = 1;while (p != NULL && j < i) {p = p->next;j++;}return p;
}// 按值查找表节点  
// 参数:  
// L - 指向链表头结点的指针（头结点不存储有效数据，仅作为链表的起点）  
// e - 要查找的元素值  
// 返回值:  
// 返回指向第一个数据域等于e的节点的指针；如果链表中不存在这样的节点，则返回NULL  
LNode* LocateElem(LinkList L, int e) {LNode* p = L->next; // 从头结点的下一个节点（即链表的第一个实际数据节点）开始遍历  // 遍历链表，直到p为NULL（即到达链表末尾）  while (p != NULL) {if (p->data == e) { // 如果当前节点的数据域等于e  break; // 则找到目标节点，跳出循环  }p = p->next; // 否则，移动到链表的下一个节点继续查找  }// 返回找到的节点指针（如果找到）或NULL（如果未找到）  return p;
}// 插入节点操作
bool ListInsert(LinkList L, int i, int e) {// 检查插入位置是否合法// i < 1 表示插入位置在链表前面，i > Length(L) + 1 表示超出链表尾部if (i < 1 || i > Length(L) + 1) return false;LNode* p = L; // 从链表头节点开始int j = 0; // 初始化计数器 j，用于遍历链表// 遍历链表，找到第 i-1 个节点while (j < i - 1) {p = p->next; // 移动到下一个节点j++; // 计数器自增}// 创建新节点并分配内存LNode* newNode = (LNode*)malloc(sizeof(LNode));// 检查内存分配是否成功if (newNode == NULL) return false;newNode->data = e; // 设置新节点的数据newNode->next = p->next; // 新节点的下一个指向 p 的下一个节点p->next = newNode; // 将 p 的下一个节点指向新节点return true; // 插入成功，返回 true
}// 删除节点操作
bool ListDelete(LinkList L, int i, int* e) {if (i < 1 || i > Length(L)) return false; // 检查i是否在有效范围内（不包括头结点）  LNode* p = L; // 从头结点开始，但p实际上会移动到第i-1个数据节点  int j = 0;while (j < i - 1) { // 循环直到p指向第i-1个数据节点  p = p->next;j++;}LNode* q = p->next; // q指向要删除的节点（即第i个数据节点）  if (q == NULL) {// 理论上，由于前面的检查，这里不应该执行。但为了代码的健壮性，可以保留或添加错误处理  return false;}p->next = q->next; // 绕过q，将p的next指向q的next  *e = q->data; // 保存q的数据到e指向的位置  free(q); // 释放q的内存  return true; // 删除成功  
}// 头插法建立链表  
// 接收一个已经初始化但可能为空的链表头节点L，并通过用户输入来向链表中插入数据  
// 输入9999时结束插入，并返回更新后的链表头节点L  
LinkList List_HandInsert(LinkList L) {int new_data = 0;LNode* new_Node; // 用于指向新创建的节点的指针  // 循环直到用户输入9999为止  while (new_data != 9999) {printf("请输入需要插入的数据（输入9999结束）：");scanf("%d", &new_data); // 读取用户输入的数据  if (new_data == 9999) break; // 如果输入的是9999，则跳出循环  // 为新节点分配内存  new_Node = (LNode*)malloc(sizeof(LNode));if (new_Node == NULL) {printf("空间不足\r\n"); // 如果内存分配失败，打印错误信息  return L; // 并返回当前的链表头节点L（此时链表可能未被修改）  }// 设置新节点的数据域  new_Node->data = new_data;// 将新节点插入到链表的头部（即头节点之后）  // 首先，将新节点的next指针指向当前的第一个节点（L->next）  new_Node->next = L->next;// 然后，将头节点的next指针指向新节点，这样新节点就变成了链表的第一个有效节点  L->next = new_Node;}// 循环结束后，返回更新后的链表头节点L  return L;
}// 尾插法向链表中插入节点  
// LinkList 是链表的类型，通常是一个指向链表头节点的指针  
// 返回值为更新后的链表头节点指针  
LinkList List_TailInsert(LinkList L) {// p 用于遍历链表，初始时指向链表头节点  // 注意：如果链表为空，p 也将指向空指针（即链表头节点为空）  LNode* p = L;int new_data = 0; // 用于存储用户输入的数据  LNode* new_Node; // 用于指向新创建的节点  // 循环直到用户输入非零值且非9999的数据  while (1) {printf("请输入需要插入的数据（输入9999结束）：");scanf("%d", &new_data); // 读取用户输入的数据  // 如果用户输入了9999，则跳出循环  if (new_data == 9999) break;// 为新节点分配内存  new_Node = (LNode*)malloc(sizeof(LNode));// 检查内存分配是否成功  if (new_Node == NULL) {printf("空间不足\r\n"); // 如果内存分配失败，打印错误信息  return L; // 并返回当前的链表头节点L（此时链表可能未被修改）  }// 设置新节点的数据域  new_Node->data = new_data;// 将p的next指针指向新节点，实现链表的连接  p->next = new_Node;// 新节点的next指针设为NULL，表示它是链表的最后一个节点  new_Node->next = NULL;// 更新p指针，使其指向链表的最后一个节点，以便下一次插入  p = p->next;}// 循环结束，返回更新后的链表头节点  return L;
}// 注意：  
// 1. 此函数假设L是一个有效的链表头节点指针，即使链表为空（即L为NULL），函数也能正确处理（尽管这通常不是最佳实践，因为空链表通常应由一个哑节点来表示）。  
// 2. 如果L为NULL且链表应包含哑节点，则需要在函数开始时检查L是否为NULL，并相应地初始化L。  
// 3. 此函数通过修改链表头节点的next指针的链接来实现插入，因此不需要传入链表的尾节点指针。  
// 4. 如果链表包含哑节点，则p应初始化为L->next，并且在函数开始时需要确保L不是NULL。int main() {LinkList myList;if (InitList(&myList)) {printf("链表初始化成功！\n");}else {printf("链表初始化失败！\n");}return 0;
}

四、简单使用案例（C语言）


int main() {LinkList myList;if (!InitList(&myList)) { // 注意：使用!来检查失败情况  printf("链表初始化失败！\n");return 1; // 初始化失败时退出程序  }printf("链表初始化成功！\n");// 使用尾插法向链表中插入数据  List_TailInsert(myList);// 遍历链表并打印数据  LNode* p = myList->next; // 从链表的第一个有效节点开始遍历  while (p != NULL) {printf("%d ", p->data); // 打印当前节点的数据  p = p->next; // 移动到下一个节点  }printf("\n"); // 换行  printf("\r\n插入案例\r\n");ListInsert(myList, 3, 60);p = myList->next; // 从链表的第一个有效节点开始遍历  while (p != NULL) {printf("%d ", p->data); // 打印当前节点的数据  p = p->next; // 移动到下一个节点  }printf("\n"); // 换行  printf("\r\n删除案例\r\n");int data;ListDelete(myList, 1,&data);p = myList->next; // 从链表的第一个有效节点开始遍历  while (p != NULL) {printf("%d ", p->data); // 打印当前节点的数据  p = p->next; // 移动到下一个节点  }printf("\n"); // 换行  // 注意：在实际应用中，你可能还需要释放链表占用的内存，但在这个简单示例中我省略了这一步。  return 0;
}