数据结构--单链表
一、引言
单链表是数据结构中最基础也是最重要的一种链式数据结构。它在内存中的元素不需要连续存储，每个元素通过指针连接到下一个元素。这种结构使得插入和删除操作变得高效，适合动态数据的管理。本文将全面介绍单链表的基本概念、结构、常见操作，并提供完整的实现代码。
二、单链表的基本概念与结构
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;
}六、总结
单链表是一种简单而强大的数据结构，适用于动态数据存储和管理。通过本文，我们介绍了单链表的基本概念、常见操作及其实现。掌握单链表的操作可以帮助我们更好地解决实际编程问题，特别是在需要频繁插入和删除操作的场景中。
希望这篇博客对你理解和使用单链表有所帮助。如果你有任何问题或想进一步了解更多高级用法，请随时留言讨论！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-10-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
