目录
一、引言
二、单链表的基本概念与结构
1. 概念
2. 基本结构
三、单链表优缺点
1.优点
2.缺点
四、单链表的常见操作
1.创建节点
2.初始化(创建头节点)
3.头插
4.尾插
5.头删
6.尾删
7.查找
8.指定位置前插入
9.指定位置后插入
10.指定位置删除
11.打印
12.销毁
五、完整代码
1.List.h
2.List.c
3.test.c
六、总结
一、引言
单链表是数据结构中最基础也是最重要的一种链式数据结构。它在内存中的元素不需要连续存储，每个元素通过指针连接到下一个元素。这种结构使得插入和删除操作变得高效，适合动态数据的管理。本文将全面介绍单链表的基本概念、结构、常见操作，并提供完整的实现代码。
二、单链表的基本概念与结构
1. 概念
单链表是一种链式存储的数据结构，由一系列节点（Node）组成。每个节点包含两部分：
- 数据域（Data）：存储实际的数据。
- 指针域（Next）：指向链表中的下一个节点。
链表的特点是节点不需要在内存中连续存储，这允许链表在插入和删除操作时具有更高的灵活性和效率。
2. 基本结构
单链表的基本结构如下：
typedef int DataType;
typedef struct ListNode
{DataType data;//数据域struct ListNode* next;//指针域,指向下一个节点
}LN;三、单链表优缺点
1.优点
动态内存管理：节点在内存中不需要连续存储，支持动态扩展。
高效插入和删除：在链表中插入或删除节点的操作时间复杂度为 O(1)O(1)O(1)。
适应不同数据大小：可以处理动态变化的数据大小，无需事先定义固定大小。
2.缺点
额外空间开销：每个节点需要额外存储一个指针，增加内存开销。
访问效率低：访问链表中的第 nnn 个元素需要逐一遍历，时间复杂度为 O(n)O(n)O(n)。
不支持反向遍历：只能从头到尾遍历，不能直接反向遍历。
四、单链表的常见操作
单链表的操作包括节点的插入、删除、查找以及链表的遍历。下面是这些操作的详细说明及代码实现。
1.创建节点
//创建节点
LN* CreateNode(DataType x)
{LN* newnode = (LN*)malloc(sizeof(LN));if (newnode==NULL) {perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}2.初始化(创建头节点)
// 初始化链表（创建头节点）
LN*ListInit()
{LN* headnode = CreateNode(0); // 头节点值为0（或任何不使用的值）return headnode;
}3.头插
//头插
void ListPushHead(LN* phead, DataType x)
{assert(phead);LN* newnode = CreateNode(x);newnode->next = phead->next;phead->next = newnode;}4.尾插
//尾插
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;
}5.头删
//头删
void ListDelHead(LN* phead)
{assert(phead);if (phead->next == NULL){printf("链表为空，无法进行删除操作！\n");return;}LN* temp = phead->next;phead->next = phead->next->next;free(temp);
}6.尾删
//尾删
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;
}7.查找
//查找
LN* ListFind(LN* phead, DataType x)
{assert(phead);LN* pcur = phead->next;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
8.指定位置前插入
//指定位置前插入
void ListInsertFront(LN* phead, LN*pos,DataType x)
{assert(phead);LN* pcur = phead;if (pos==NULL){printf("插入位置非法\n");return;}while (pcur->next != pos){pcur=pcur->next;}LN* newnode = CreateNode(x);newnode->next = pos;pcur->next = newnode;
}9.指定位置后插入
//指定位置后插入
void ListInsertBack(LN* pos, DataType x)
{if (pos == NULL){printf("插入位置非法\n");return;}LN* newnode = CreateNode(x);newnode->next = pos->next;pos->next = newnode;
}10.指定位置删除
//指定位置节点删除
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){pcur = pcur->next;}pcur->next = pos->next;free(pos);
}11.打印
//打印链表
void ListPrint(LN* phead)
{assert(phead);LN* pcur = phead->next;//注意这里带头节点，所以打印数值从头节点的下一位打印while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}12.销毁
//销毁
void ListDestory(LN** pphead)
{LN* pcur=*pphead;LN* temp = NULL;while (pcur){temp = pcur->next; // 保存下一个节点的指针free(pcur);// 释放当前节点的内存pcur = temp;// 移动到下一个节点}// 将头指针置为 NULL，确保链表被正确销毁*pphead= NULL;
}五、完整代码
1.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 ListDestory(LN**pphead);2.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;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;phead->next = newnode;}
//尾删
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;
}
//头删
void ListDelHead(LN* phead)
{assert(phead);if (phead->next == NULL){printf("链表为空，无法进行删除操作！\n");return;}LN* temp = phead->next;phead->next = phead->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");
}
//查找
LN* ListFind(LN* phead, DataType x)
{assert(phead);LN* pcur = phead->next;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
//指定位置前插入
void ListInsertFront(LN* phead, LN*pos,DataType x)
{assert(phead);LN* pcur = phead;if (pos==NULL){printf("插入位置非法\n");return;}while (pcur->next != pos){pcur=pcur->next;}LN* newnode = CreateNode(x);newnode->next = pos;pcur->next = newnode;
}
//指定位置后插入
void ListInsertBack(LN* pos, DataType x)
{if (pos == NULL){printf("插入位置非法\n");return;}LN* newnode = CreateNode(x);newnode->next = pos->next;pos->next = newnode;
}
//指定位置节点删除
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){pcur = pcur->next;}pcur->next = pos->next;free(pos);
}
//销毁
void ListDestory(LN** pphead)
{LN* pcur=*pphead;LN* temp = NULL;while (pcur){temp = pcur->next; // 保存下一个节点的指针free(pcur);// 释放当前节点的内存pcur = temp;// 移动到下一个节点}// 将头指针置为 NULL，确保链表被正确销毁*pphead= NULL;
}3.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);//ListDestory(&phead);
}
int main()
{test1();return 0;
}六、总结
单链表是一种简单而强大的数据结构，适用于动态数据存储和管理。通过本文，我们介绍了单链表的基本概念、常见操作及其实现。掌握单链表的操作可以帮助我们更好地解决实际编程问题，特别是在需要频繁插入和删除操作的场景中。
希望这篇博客对你理解和使用单链表有所帮助。如果你有任何问题或想进一步了解更多高级用法，请随时留言讨论！
