admin管理员组

文章数量:1033654

【初探数据结构】线性表————链表（一）（单链表的实现）

何为链表？

链表是一种物理存储结构非连续、非顺序的线性数据结构。与数组不同，链表的元素通过指针链接形成逻辑上的顺序关系。每个节点包含两部分：

  • 数据域：存储实际数据。
  • 指针域：指向下一个节点的地址（单链表）或同时指向前后节点（双链表）。

链表的优势：

  • 动态内存分配，无需预先确定数据规模。
  • 插入和删除操作时间复杂度为 O(1)（已知位置时）。

每个节点都是一个结构体，这个结构体包含2个（单链表）或者3个成员（双链表）。

代码语言：javascript代码运行次数：0运行复制
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LT;
  • 指针域
    • next：指向下一个节点的指针
    • prev：指向上一个节点的指针
  • 数据域
    • data：存储数据

各个节点通过指针相互链接，构成了链表

链表的分类

链表一共有8种

  1. 单向或者双向：单链表节点只有指向后继的指针；双链表节点同时包含前驱和后继指针。
  1. 带头或者不带头（有无哨兵位）：带头链表包含一个不存储数据的“哨兵节点”，简化边界操作。
  1. 循环或者非循环：循环链表的尾节点指向头节点，形成闭环

这三个特性自由组合，就组成了8种链表

我们主要研究这两种链表：

这两种链表吃透后，剩余的也就自然而然的学会了。

单链表（无头单向非循环链表）的实现

头文件编写： SList.h

代码语言：javascript代码运行次数：0运行复制
#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;//存储数据
	struct SListNode* next;//指向下一节点指针
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);

// 在pos的前面插入
void SLTInsertBehind(SListNode** pplist, SListNode* pos, SLTDateType x);

// 删除pos位置
void SLTErase(SListNode** pplist, SListNode* pos);

// 销毁链表
void SLTDstory(SListNode** pplist);
插入节点
尾插

要实现尾插，就得找到链表的尾部，再对其尾部进行操，如图：

不难写出操作代码：

代码语言：javascript代码运行次数：0运行复制
tail->next = newnode;
newnode->next = NULL;
动态申请节点
代码语言：javascript代码运行次数：0运行复制
SListNode* BuySListNode(SLTDateType x) {
    SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
    if (newNode == NULL) {
        perror("malloc fail");
        return NULL;
    }
    newNode->data = x;
    newNode->next = NULL;
    return newNode;
}
代码语言：javascript代码运行次数：0运行复制
void SListPushBack(SListNode** pplist, SLTDateType x) {
    assert(pplist); // 断言二级指针非空
    SListNode* newNode = BuySListNode(x);
    
    if (*pplist == NULL) {  // 空链表直接插入
        *pplist = newNode;
    } else {
        SListNode* tail = *pplist;
        while (tail->next != NULL) { // 遍历找到尾节点
            tail = tail->next;
        }
        tail->next = newNode; // 链接新节点
    }
}
头插

逻辑：新节点的 next 指向原头节点，更新头指针。

代码语言：javascript代码运行次数：0运行复制
void SListPushFront(SListNode** pplist, SLTDateType x) {
    assert(pplist);
    SListNode* newNode = BuySListNode(x);
    newNode->next = *pplist;
    *pplist = newNode; // 更新头指针
}

注意：操作顺序不可颠倒，否则会丢失原头节点地址。

在pos位置之后（前）插入x

注意在pos前插入需要遍历找到pos前的节点

代码语言：javascript代码运行次数：0运行复制
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* NewNote = BuySListNode(x);
	NewNote->next = pos->next;
	pos->next = NewNote;
}

void SListInsertBehind(SListNode** pplist, SListNode* pos, SLTDateType x)
{
	assert(pos);
	assert(pplist);
	if (*pplist == pos) {
		SListPushFront(*pplist, x);
	}
	else {
		SListNode* NewNote = BuySListNode(x);
		SListNode* src = *pplist;
		while (src->next != pos) {
			src = src->next;
		}
		NewNote->next = pos;
		src->next = NewNote;
	}
}
删除节点
尾删

将尾部的前一个节点next指向空NULL，再将尾部free释放

代码语言：javascript代码运行次数：0运行复制
void SListPopBack(SListNode** pplist) {
    assert(pplist && *pplist); // 链表不能为空
    
    if ((*pplist)->next == NULL) { // 仅一个节点
        free(*pplist);
        *pplist = NULL;
    } else {
        SListNode* prev = NULL;
        SListNode* tail = *pplist;
        while (tail->next != NULL) { // 找尾节点及其前驱
            prev = tail;
            tail = tail->next;
        }
        prev->next = NULL; // 断开尾节点
        free(tail);
    }
}
头删

将头指向下一个节点，再将其free释放

代码语言：javascript代码运行次数：0运行复制
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SListNode* phead = *pplist;
	*pplist = phead->next;
	free(phead);
	phead = NULL;
}
单链表删除pos位置之后的节点
代码语言：javascript代码运行次数：0运行复制
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	SListNode* del = pos->next;
	pos->next = del->next;
	free(del);
}
删除pos位

找到pos节点前的节点

代码语言：javascript代码运行次数：0运行复制
void SLTErase(SListNode** pplist, SListNode* pos)
{
	assert(pos);
	assert(*pplist);
	assert(pplist);
	if (pos == *pplist) {
		SListPopFront(*pplist);
	}
	else {
		SListNode* src = *pplist;
		while (src->next != pos) {
			src = src->next;
		}
		src->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
关键细节解析
二级指针的使用
  • 为什么需要二级指针？ 当需要修改头指针本身（如头插、头删）时，需通过二级指针传递头指针的地址，否则函数内的修改无法影响外部。
assert的使用原则
  • 何时断言？ 若某个条件不满足会导致程序崩溃（如空指针解引用），则必须使用 assert。例如：
    • 删除操作前断言链表非空。
    • 插入节点时断言二级指针非空。 当我们思考是否需要断言时，我们就从代码逻辑是否允许的方面来考虑

总结

单链表是链表家族中最基础的形式，理解其实现原理后，双链表、循环链表等衍生物只需稍加扩展即可掌握。 重点注意：

  • 指针操作的顺序，避免内存泄漏或野指针。
  • 边界条件处理（如空链表、头尾节点操作）。

通过本文的代码示例和解析，读者可以系统地掌握单链表的实现与核心操作，为学习更复杂的链表结构打下坚实基础。

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-04，如有侵权请联系 cloudcommunity@tencent 删除数据指针存储数据结构链表

【初探数据结构】线性表————链表（一）（单链表的实现）

何为链表？

链表是一种物理存储结构非连续、非顺序的线性数据结构。与数组不同，链表的元素通过指针链接形成逻辑上的顺序关系。每个节点包含两部分：

  • 数据域：存储实际数据。
  • 指针域：指向下一个节点的地址（单链表）或同时指向前后节点（双链表）。

链表的优势：

  • 动态内存分配，无需预先确定数据规模。
  • 插入和删除操作时间复杂度为 O(1)（已知位置时）。

每个节点都是一个结构体，这个结构体包含2个（单链表）或者3个成员（双链表）。

代码语言：javascript代码运行次数：0运行复制
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LT;
  • 指针域
    • next：指向下一个节点的指针
    • prev：指向上一个节点的指针
  • 数据域
    • data：存储数据

各个节点通过指针相互链接，构成了链表

链表的分类

链表一共有8种

  1. 单向或者双向：单链表节点只有指向后继的指针；双链表节点同时包含前驱和后继指针。
  1. 带头或者不带头（有无哨兵位）：带头链表包含一个不存储数据的“哨兵节点”，简化边界操作。
  1. 循环或者非循环：循环链表的尾节点指向头节点，形成闭环

这三个特性自由组合，就组成了8种链表

我们主要研究这两种链表：

这两种链表吃透后，剩余的也就自然而然的学会了。

单链表（无头单向非循环链表）的实现

头文件编写： SList.h

代码语言：javascript代码运行次数：0运行复制
#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;//存储数据
	struct SListNode* next;//指向下一节点指针
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);

// 在pos的前面插入
void SLTInsertBehind(SListNode** pplist, SListNode* pos, SLTDateType x);

// 删除pos位置
void SLTErase(SListNode** pplist, SListNode* pos);

// 销毁链表
void SLTDstory(SListNode** pplist);
插入节点
尾插

要实现尾插，就得找到链表的尾部，再对其尾部进行操，如图：

不难写出操作代码：

代码语言：javascript代码运行次数：0运行复制
tail->next = newnode;
newnode->next = NULL;
动态申请节点
代码语言：javascript代码运行次数：0运行复制
SListNode* BuySListNode(SLTDateType x) {
    SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
    if (newNode == NULL) {
        perror("malloc fail");
        return NULL;
    }
    newNode->data = x;
    newNode->next = NULL;
    return newNode;
}
代码语言：javascript代码运行次数：0运行复制
void SListPushBack(SListNode** pplist, SLTDateType x) {
    assert(pplist); // 断言二级指针非空
    SListNode* newNode = BuySListNode(x);
    
    if (*pplist == NULL) {  // 空链表直接插入
        *pplist = newNode;
    } else {
        SListNode* tail = *pplist;
        while (tail->next != NULL) { // 遍历找到尾节点
            tail = tail->next;
        }
        tail->next = newNode; // 链接新节点
    }
}
头插

逻辑：新节点的 next 指向原头节点，更新头指针。

代码语言：javascript代码运行次数：0运行复制
void SListPushFront(SListNode** pplist, SLTDateType x) {
    assert(pplist);
    SListNode* newNode = BuySListNode(x);
    newNode->next = *pplist;
    *pplist = newNode; // 更新头指针
}

注意：操作顺序不可颠倒，否则会丢失原头节点地址。

在pos位置之后（前）插入x

注意在pos前插入需要遍历找到pos前的节点

代码语言：javascript代码运行次数：0运行复制
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* NewNote = BuySListNode(x);
	NewNote->next = pos->next;
	pos->next = NewNote;
}

void SListInsertBehind(SListNode** pplist, SListNode* pos, SLTDateType x)
{
	assert(pos);
	assert(pplist);
	if (*pplist == pos) {
		SListPushFront(*pplist, x);
	}
	else {
		SListNode* NewNote = BuySListNode(x);
		SListNode* src = *pplist;
		while (src->next != pos) {
			src = src->next;
		}
		NewNote->next = pos;
		src->next = NewNote;
	}
}
删除节点
尾删

将尾部的前一个节点next指向空NULL，再将尾部free释放

代码语言：javascript代码运行次数：0运行复制
void SListPopBack(SListNode** pplist) {
    assert(pplist && *pplist); // 链表不能为空
    
    if ((*pplist)->next == NULL) { // 仅一个节点
        free(*pplist);
        *pplist = NULL;
    } else {
        SListNode* prev = NULL;
        SListNode* tail = *pplist;
        while (tail->next != NULL) { // 找尾节点及其前驱
            prev = tail;
            tail = tail->next;
        }
        prev->next = NULL; // 断开尾节点
        free(tail);
    }
}
头删

将头指向下一个节点，再将其free释放

代码语言：javascript代码运行次数：0运行复制
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SListNode* phead = *pplist;
	*pplist = phead->next;
	free(phead);
	phead = NULL;
}
单链表删除pos位置之后的节点
代码语言：javascript代码运行次数：0运行复制
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	SListNode* del = pos->next;
	pos->next = del->next;
	free(del);
}
删除pos位

找到pos节点前的节点

代码语言：javascript代码运行次数：0运行复制
void SLTErase(SListNode** pplist, SListNode* pos)
{
	assert(pos);
	assert(*pplist);
	assert(pplist);
	if (pos == *pplist) {
		SListPopFront(*pplist);
	}
	else {
		SListNode* src = *pplist;
		while (src->next != pos) {
			src = src->next;
		}
		src->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
关键细节解析
二级指针的使用
  • 为什么需要二级指针？ 当需要修改头指针本身（如头插、头删）时，需通过二级指针传递头指针的地址，否则函数内的修改无法影响外部。
assert的使用原则
  • 何时断言？ 若某个条件不满足会导致程序崩溃（如空指针解引用），则必须使用 assert。例如：
    • 删除操作前断言链表非空。
    • 插入节点时断言二级指针非空。 当我们思考是否需要断言时，我们就从代码逻辑是否允许的方面来考虑

总结

单链表是链表家族中最基础的形式，理解其实现原理后，双链表、循环链表等衍生物只需稍加扩展即可掌握。 重点注意：

  • 指针操作的顺序，避免内存泄漏或野指针。
  • 边界条件处理（如空链表、头尾节点操作）。

通过本文的代码示例和解析，读者可以系统地掌握单链表的实现与核心操作，为学习更复杂的链表结构打下坚实基础。

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-04，如有侵权请联系 cloudcommunity@tencent 删除数据指针存储数据结构链表

本文标签： 初探数据结构线性表链表（一）（单链表的实现）

版权声明：本文标题：【初探数据结构】线性表————链表（一）（单链表的实现） 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1748070655a2249065.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。