当前位置：首页 > news >正文

单链表C语言实现

news 2025/5/22 14:17:21

1. 单链表的核心概念

单链表（Singly Linked List） 是一种线性数据结构，通过节点间的指针链接实现元素存储。
节点结构：

typedef struct SListNode {SLTDataType data;     // 数据域struct SListNode* next; // 指针域
} SLTNode;

核心特性：

内存非连续，通过指针动态连接。
插入/删除操作高效（时间复杂度 O(1)~O(n)）。
不支持随机访问，查找需遍历。

2. 单链表的C语言实现

(1)节点创建与初始化

SLTNode* SLTBuyNode(SLTDataType x) {SLTNode* newnode = malloc(sizeof(SLTNode));newnode->data = x;newnode->next = NULL;return newnode;
}

作用：动态分配节点内存，初始化数据域和指针域。

(2) 插入操作

头部插入：直接修改头指针，时间复杂度 O(1)。

void SLTPushFront(SLTNode** pphead, SLTDataType x) {SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

尾部插入：遍历找到尾节点后插入，时间复杂度 O(n)。

void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL) { *pphead = newnode;}else {SLTNode* ptail = *pphead;while (ptail->next != NULL) { ptail = ptail->next;}ptail->next = newnode; }
}

指定位置插入：需找到前驱节点，时间复杂度 O(n)。

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos == *pphead){SLTPushFront(pphead, x);//如果pos是头节点，执行头插return;}SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos)//寻找pos的前一个节点{prev = prev->next;}newnode->next = pos;//newnode的next指向pos，此时newnode->next和prev->next同时指向posprev->next = newnode;//prev->next指向由原来的pos断开(现在只有一个newnode->next指向原来开的pos)，转向newnode，newnode此时就占据了原来pos的位置，完成插入}

(3) 删除操作

头部删除：直接移动头指针，时间复杂度 O(1)。

void SLTPopFront(SLTNode** pphead) {SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

尾部删除：遍历找到倒数第二个节点，时间复杂度 O(n)。

void SLTPopBack(SLTNode** pphead) {assert(pphead && *pphead); // 链表不能为空if ((*pphead)->next == NULL) { // 只有一个节点free(*pphead);*pphead = NULL;}else {SLTNode* prev = NULL;SLTNode* ptail = *pphead;while (ptail->next != NULL) { // 找到尾节点和前驱节点prev = ptail;ptail = ptail->next;}prev->next = NULL; // 断开尾节点free(ptail);}
}

(4) 链表销毁

void SListDesTroy(SLTNode** pphead) {SLTNode* pcur = *pphead;while (pcur) {SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

关键点：逐个释放节点，避免内存泄漏。

3. 时间复杂度分析

操作	时间复杂度	说明
头部插入/删除	O(1)	直接操作头指针
尾部插入/删除	O(n)	需遍历找到尾节点
指定位置插入/删除	O(n)	需遍历找到前驱节点
查找	O(n)	最坏情况遍历整个链表

4 注意事项

指针操作：

使用双重指针 SLTNode** 修改头指针地址：为了在函数内部能够直接修改外部头指针的地址，确保链表操作（如插入、删除头节点）能正确更新头指针。这是C语言中实现“通过函数修改指针”的标准方法。
插入/删除时需注意前驱节点的链接关系。

场景	是否需要双重指针	原因
修改头指针的值	是	需要直接操作外部头指针的地址
仅修改链表节点内容	否	单指针已能通过地址修改节点数据
插入/删除头节点	是	头指针本身需要被更新
插入/删除中间或尾部节点	否	只需操作节点间的指针，不涉及头指针