顺序表与链表·续

引言

本文承接上文（顺序表与链表-CSDN博客），开始对链表的要点提炼。前文提到顺序表适合需要频繁随机访问且数据量固定的场景，而链表适合需要频繁插入和删除且数据量动态变化的场景。链表的引入弥补了顺序表在动态性和操作效率上的不足，是线性表的重要实现方式之一。

链表

概念

链表是一种 物理存储结构上非连续 、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表

中的 指针链接 实现的 。

链表结构

容易发现链表结构在逻辑上连续，但物理上不一定连续，一般链表的节点从堆上申请的，每次申请的空间是否连续是不确定的。

分类

链表的分类可以根据以下维度进行：

1. 单向或双向：决定节点的指针数量和遍历方向。

2. 带头或不带头：决定是否有额外的头节点简化操作。

3. 循环或不循环：决定链表是否形成环。

通过组合这些维度，可以设计出适合不同场景的链表结构。例如：

• 带头单向循环链表：适合实现队列。

• 带头双向循环链表：适合需要双向遍历且操作简化的场景。

  而我们常遇到的主要是不带头单向非循环链表和带头双向循环链表（以下图例分别对应这两种链表）

不带头单向非循环链表

带头双向循环链表

 

实现

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

//"slist.h"
#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) 
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}// 单链表打印
void SListPrint(SListNode* plist)
{SListNode* cur = plist;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{SListNode* newnode = BuySListNode(x);if (*pplist == NULL) {*pplist = newnode;}else{SListNode* tail = *pplist;while (tail->next!=NULL){tail = tail->next;}tail->next = newnode;}}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{SListNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist = newnode;}// 单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(pplist);assert(*pplist);//一个节点if ((*pplist)->next == NULL) {free(*pplist);*pplist = NULL;}//多个节点SListNode* tail = *pplist;while (tail->next->next!=NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
void SListPopFront(SListNode** pplist) {// 防御性检查：拦截非法输入if (pplist == NULL) {fprintf(stderr, "Error: Invalid pointer in SListPopFront\n");return;}// 业务逻辑检查：空链表直接返回if (*pplist == NULL) {return;}SListNode* tmp = *pplist;*pplist = tmp->next;free(tmp);
}// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur = plist;while (cur) {if (cur->data == x) {return cur;}cur = cur->next;}return NULL;
}
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？  // 因为没有前置指针
// 若要在 pos 之前插入，必须从头节点开始遍历链表找到 pos 的前驱节点，时间复杂度为 O(n)
void SListInsertAfter(SListNode* pos, SLTDateType x)
{if (pos == NULL) return;SListNode* newNode = BuySListNode(x);newNode->next = pos->next;pos->next = newNode;
}
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？ //删除 pos 节点需要知道其前驱节点，而单链表无法直接获取前驱节点
// 必须从头遍历链表，时间复杂度为O(n)，删除 pos 之后的节点只需修改 pos->next，时间复杂度为O(1)。void SListEraseAfter(SListNode* pos)
{if (pos == NULL || pos->next == NULL) return;SListNode* tmp = pos->next;pos->next = tmp->next;free(tmp);
}// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{assert(pphead);assert(pos);assert(*pphead);if (*pphead == pos) SListPushFront(pphead,x);else{SListNode* prev = *pphead;while (prev->next!=pos){prev = prev->next;}SListNode* newnode=BuySListNode(x);prev->next = newnode;newnode->next = pos;}
}// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos){// 头删SListPopFront(pphead);}else{SListNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}void SLTDestroy(SListNode** pphead)
{assert(pphead);SListNode* cur = *pphead;while (cur) {SListNode* tmp = cur;cur = cur->next;free(tmp);}*pphead = NULL;
}

关键点说明

1. 二级指针的使用：

   • 修改头指针时（如插入/删除头节点），需通过二级指针 pplist 修改一级指针 *pplist。

   • 示例：SListPushFront 和 SListPopFront 直接修改头指针。

2. 边界条件处理：

   • 空链表、单节点链表、尾节点/头节点操作需特殊处理。

   • 例如 SListPopBack 中需处理链表只有一个节点的情况。

3. 时间复杂度：

   • 头插/头删：O(1)/O(1)

   • 尾插/尾删：O(n)/O(n)

   • 插入/删除指定位置：平均 O(n)/O(n)（需遍历找到位置）

4. 内存管理：

   • 每次 malloc 后需检查内存分配是否成功。

   • 删除节点后需及时 free 防止内存泄漏。

  若需要频繁在任意位置前插入或删除，最好使用双向链表，它可以通过前驱指针直接操作，时间复杂度为 O(1)/O(1)。