单链表(Singly Linked List)是数据结构中最基础且广泛应用的链式结构之一。与数组不同,单链表在内存中的元素不需要连续存储,每个元素(节点)通过指针连接到下一个节点。这种非连续存储结构,使得单链表在动态内存管理、插入和删除操作上有着明显的优势。它在处理动态数据或需要频繁插入删除的场景中尤为高效,因此在许多算法和应用中扮演着重要角色。
本文将全面介绍单链表的概念、结构和常见操作,提供完整的代码实现,并详细讲解每个操作的核心思想。通过本文的学习,你将能够深入理解单链表的特点及其在编程中的实际应用。
单链表是一种链式存储的数据结构,由一系列节点(Node)组成。每个节点包含两部分:
链表的特点是节点在内存中不需要连续存储,这与数组不同,数组的元素是连续存储在内存中的。由于这一特点,链表的插入和删除操作不涉及大量的元素移动,因此操作非常灵活、高效,尤其适合动态数据的管理。通过指针的连接,链表能够动态扩展,存储任意数量的节点,而不会像数组一样受到固定容量的限制。
链表结构示意图如下:
单链表的基本结构由节点和指针组成。每个节点包含数据部分和指向下一个节点的指针。下面是C语言中单链表节点的定义:
typedef int DataType;
typedef struct ListNode
{
DataType data;//数据域
struct ListNode* next;//指针域,指向下一个节点
}LN;
每个节点通过 next
指针连接到下一个节点,最后一个节点的 next
指针为空(即指向 NULL
),表示链表的终点。整个链表的入口称为头指针(Head Pointer),它指向第一个节点的位置。如果链表为空,头指针为 NULL
。
单链表的常见操作包括节点的插入、删除、查找、遍历和销毁。以下将详细介绍这些操作的实现方法,并提供相应的代码示例。
每个节点是链表的基本组成部分。以下代码用于创建一个新节点,并初始化节点中的数据和指针:
// 创建一个新节点
LN* CreateNode(DataType x) {
// 分配一个新的链表节点内存
LN* newnode = (LN*)malloc(sizeof(LN));
if (newnode == NULL) { // 判断内存分配是否成功
perror("malloc fail"); // 输出错误信息
exit(-1); // 程序退出,表示分配失败
}
newnode->data = x; // 设置节点的数据域
newnode->next = NULL; // 将节点的 next 指针置为 NULL
return newnode; // 返回新创建的节点
}
链表的头节点作为链表的入口,初始化链表时,通常会先创建一个头节点(头节点的数据部分可以存储不使用的数据或空值)。以下代码用于初始化链表并创建头节点:
// 初始化链表,创建一个头节点
LN* ListInit() {
LN* headnode = CreateNode(0); // 创建一个头节点,数据域初始化为 0
return headnode; // 返回头节点
}
在链表的头部插入新节点(即在第一个元素之前插入新节点),时间复杂度为 O(1):
// 在链表的头部添加节点
void ListPushHead(LN* phead, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* newnode = CreateNode(x); // 创建一个新节点
newnode->next = phead->next; // 新节点的 next 指向原头节点的下一个节点
phead->next = newnode; // 头节点的 next 指向新节点
}
在链表的尾部插入新节点,时间复杂度为 O(n):
// 在链表的末尾添加节点
void ListPushBack(LN* phead, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* newnode = CreateNode(x); // 创建一个新节点
LN* pcur = phead;
while (pcur->next != NULL) { // 遍历到链表的末尾
pcur = pcur->next;
}
pcur->next = newnode; // 将新节点添加到链表的末尾
}
删除链表头部的第一个节点,时间复杂度为 O(1):
// 删除链表的头部节点
void ListDelHead(LN* phead) {
assert(phead); // 确保链表头节点不为空
if (phead->next == NULL) { // 判断链表是否为空
printf("链表为空,无法进行删除操作!\n");
return;
}
LN* temp = phead->next; // 保存头部节点
phead->next = phead->next->next; // 头节点的 next 指向原头部节点的下一个节点
free(temp); // 释放原头部节点的内存
}
删除链表尾部的最后一个节点,时间复杂度为 O(n):
// 删除链表的尾部节点
void ListDelBack(LN* phead) {
assert(phead); // 确保链表头节点不为空
if (phead->next == NULL) { // 判断链表是否为空
printf("链表为空,无法进行删除操作!\n");
return;
}
LN* pcur = phead;
while (pcur->next->next != NULL) { // 找到倒数第二个节点
pcur = pcur->next;
}
free(pcur->next); // 释放最后一个节点的内存
pcur->next = NULL; // 将倒数第二个节点的 next 置为 NULL
}
在链表中查找值为 x
的节点:
// 查找链表中值为 x 的节点
LN* ListFind(LN* phead, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* pcur = phead->next;
while (pcur) { // 遍历链表
if (pcur->data == x) { // 如果找到数据域等于 x 的节点
return pcur; // 返回该节点
}
pcur = pcur->next;
}
return NULL; // 没有找到则返回 NULL
}
在指定节点 pos
之前插入新节点:
// 在指定节点前插入新节点
void ListInsertFront(LN* phead, LN* pos, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* pcur = phead;
if (pos == NULL) { // 判断插入位置是否合法
printf("插入位置非法\n");
return;
}
while (pcur->next != pos) { // 找到 pos 的前一个节点
pcur = pcur->next;
}
LN* newnode = CreateNode(x); // 创建新节点
newnode->next = pos; // 新节点的 next 指向 pos
pcur->next = newnode; // 前一个节点的 next 指向新节点
}
在指定节点 pos
之后插入新节点:
// 在指定节点后插入新节点
void ListInsertBack(LN* pos, DataType x) {
if (pos == NULL) { // 判断插入位置是否合法
printf("插入位置非法\n");
return;
}
LN* newnode = CreateNode(x); // 创建新节点
newnode->next = pos->next; // 新节点的 next 指向 pos 的下一个节点
pos->next = newnode; // pos 的 next 指向新节点
}
删除指定位置 pos
处的节点:
// 删除指定位置的节点
void ListErase(LN* phead, LN* pos) {
assert(phead); // 确保链表头节点不为空
if (pos == NULL) { // 判断删除位置是否合法
printf("删除位置非法\n");
return;
}
if (phead->next == NULL) { // 判断链表是否为空
printf("链表为空,无法进行删除操作!\n");
return;
}
LN* pcur = phead;
while (pcur->next != pos) { // 找到 pos 的前一个节点
pcur = pcur->next;
}
pcur->next = pos->next; // 前一个节点的 next 指向 pos 的下一个节点
free(pos); // 释放 pos 的内存
}
遍历并打印链表中的所有元素:
// 打印链表中的所有节点
void ListPrint(LN* phead) {
assert(phead); // 确保链表头节点不为空
LN* pcur = phead->next;
while (pcur) { // 遍历链表中的每个节点
printf("%d->", pcur->data); // 打印当前节点的数据
pcur = pcur->next;
}
printf("NULL\n"); // 链表结束时打印 NULL
}
释放链表中所有节点的内存,防止内存泄漏:
// 销毁链表,释放所有节点的内存
void ListDestroy(LN** pphead) {
LN* pcur = *pphead;
LN* temp = NULL;
while (pcur) { // 遍历链表并释放每个节点
temp = pcur->next;
free(pcur);
pcur = temp;
}
*pphead = NULL; // 将头指针置为 NULL
}
完整代码包括以下三部分:List.h
、List.c
和 test.c
,分别是链表的定义、链表操作函数的实现以及测试用例。
List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;
typedef struct ListNode
{
DataType data;//数据域
struct ListNode* next;//指针域,指向下一个节点
}LN;
//创建节点
LN* CreateNode(DataType x);
// 初始化链表(创建头节点)
LN* ListInit();
//尾插
void ListPushBack(LN* phead, DataType x);
//头插
void ListPushHead(LN* phead, DataType x);
//尾删
void ListDelBack(LN* phead);
//头删
void ListDelHead(LN* phead);
//打印链表
void ListPrint(LN *phead);
//查找
LN* ListFind(LN* phead, DataType x);
//指定位置前插入
void ListInsertFront(LN* phead, LN*pos,DataType x);
//指定位置后插入
void ListInsertBack(LN* pos, DataType x);
//指定位置节点删除
void ListErase(LN*phead,LN*pos);
//销毁
void ListDestroy(LN**pphead);
List.c
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
// 创建一个新节点
LN* CreateNode(DataType x) {
// 分配一个新的链表节点内存
LN* newnode = (LN*)malloc(sizeof(LN));
if (newnode == NULL) { // 判断内存分配是否成功
perror("malloc fail"); // 输出错误信息
exit(-1); // 程序退出,表示分配失败
}
newnode->data = x; // 设置节点的数据域
newnode->next = NULL; // 将节点的 next 指针置为 NULL
return newnode; // 返回新创建的节点
}
// 初始化链表,创建一个头节点
LN* ListInit() {
LN* headnode = CreateNode(0); // 创建一个头节点,数据域初始化为 0
return headnode; // 返回头节点
}
// 在链表的末尾添加节点
void ListPushBack(LN* phead, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* newnode = CreateNode(x); // 创建一个新节点
LN* pcur = phead;
while (pcur->next != NULL) { // 遍历到链表的末尾
pcur = pcur->next;
}
pcur->next = newnode; // 将新节点添加到链表的末尾
}
// 在链表的头部添加节点
void ListPushHead(LN* phead, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* newnode = CreateNode(x); // 创建一个新节点
newnode->next = phead->next; // 新节点的 next 指向原头节点的下一个节点
phead->next = newnode; // 头节点的 next 指向新节点
}
// 删除链表的尾部节点
void ListDelBack(LN* phead) {
assert(phead); // 确保链表头节点不为空
if (phead->next == NULL) { // 判断链表是否为空
printf("链表为空,无法进行删除操作!\n");
return;
}
LN* pcur = phead;
while (pcur->next->next != NULL) { // 找到倒数第二个节点
pcur = pcur->next;
}
free(pcur->next); // 释放最后一个节点的内存
pcur->next = NULL; // 将倒数第二个节点的 next 置为 NULL
}
// 删除链表的头部节点
void ListDelHead(LN* phead) {
assert(phead); // 确保链表头节点不为空
if (phead->next == NULL) { // 判断链表是否为空
printf("链表为空,无法进行删除操作!\n");
return;
}
LN* temp = phead->next; // 保存头部节点
phead->next = phead->next->next; // 头节点的 next 指向原头部节点的下一个节点
free(temp); // 释放原头部节点的内存
}
// 打印链表中的所有节点
void ListPrint(LN* phead) {
assert(phead); // 确保链表头节点不为空
LN* pcur = phead->next;
while (pcur) { // 遍历链表中的每个节点
printf("%d->", pcur->data); // 打印当前节点的数据
pcur = pcur->next;
}
printf("NULL\n"); // 链表结束时打印 NULL
}
// 查找链表中值为 x 的节点
LN* ListFind(LN* phead, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* pcur = phead->next;
while (pcur) { // 遍历链表
if (pcur->data == x) { // 如果找到数据域等于 x 的节点
return pcur; // 返回该节点
}
pcur = pcur->next;
}
return NULL; // 没有找到则返回 NULL
}
// 在指定节点前插入新节点
void ListInsertFront(LN* phead, LN* pos, DataType x) {
assert(phead); // 确保链表头节点不为空
LN* pcur = phead;
if (pos == NULL) { // 判断插入位置是否合法
printf("插入位置非法\n");
return;
}
while (pcur->next != pos) { // 找到 pos 的前一个节点
pcur = pcur->next;
}
LN* newnode = CreateNode(x); // 创建新节点
newnode->next = pos; // 新节点的 next 指向 pos
pcur->next = newnode; // 前一个节点的 next 指向新节点
}
// 在指定节点后插入新节点
void ListInsertBack(LN* pos, DataType x) {
if (pos == NULL) { // 判断插入位置是否合法
printf("插入位置非法\n");
return;
}
LN* newnode = CreateNode(x); // 创建新节点
newnode->next = pos->next; // 新节点的 next 指向 pos 的下一个节点
pos->next = newnode; // pos 的 next 指向新节点
}
// 删除指定位置的节点
void ListErase(LN* phead, LN* pos) {
assert(phead); // 确保链表头节点不为空
if (pos == NULL) { // 判断删除位置是否合法
printf("删除位置非法\n");
return;
}
if (phead->next == NULL) { // 判断链表是否为空
printf("链表为空,无法进行删除操作!\n");
return;
}
LN* pcur = phead;
while (pcur->next != pos) { // 找到 pos 的前一个节点
pcur = pcur->next;
}
pcur->next = pos->next; // 前一个节点的 next 指向 pos 的下一个节点
free(pos); // 释放 pos 的内存
}
// 销毁链表,释放所有节点的内存
void ListDestroy(LN** pphead) {
LN* pcur = *pphead;
LN* temp = NULL;
while (pcur) { // 遍历链表并释放每个节点
temp = pcur->next;
free(pcur);
pcur = temp;
}
*pphead = NULL; // 将头指针置为 NULL
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void test1()
{
LN* phead = ListInit();//创建头节点,头指针指向头节点
ListPushHead(phead, 1);
ListPushHead(phead, 2);
ListPushHead(phead, 3);
//ListDelBack(phead);
//ListDelHead(phead);
//测试查找
LN * find = ListFind(phead,2);
/*if (find == NULL)
{
printf("没有找到!\n");
}
else
{
printf("找到了!\n");
}*/
//ListInsertFront(phead, find, 99);
//ListInsertBack(find,88);
//ListErase(phead, find);
ListPrint(phead);
//ListDestroy(&phead);
}
int main()
{
test1();
return 0;
}
单链表是一种简单而强大的数据结构,适用于动态数据存储和管理。通过本文,我们介绍了单链表的基本概念、常见操作及其实现。掌握单链表的操作可以帮助我们更好地解决实际编程问题,特别是在需要频繁插入和删除操作的场景中。