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

数据结构之单链表

ds 2025/7/16 7:52:08

链表

之前我们在谈论顺序表时，我们可以看出顺序表的缺点：

·插入和删除操作需要移动大量元素

·当线性表长度变化较大时,难以确定存储空间的容量

·造成存储空间的“碎片”

接下来我们介绍一种数据结构叫做链表，它解决了上述顺序表的这些问题

链表是一种常见的线性数据结构，它解决了顺序表（如数组）在插入和删除操作时的效率问题。与顺序表不同，链表的存储单元可以是不连续的，通过指针将各个节点连接起来，形成一个链式结构。

链表的特点：用一组任意的存储单元存储线性表的数据元素，这个存储单元可以是连续的，也可以是不连续的，在这个结构中，不但要存储数据元素信息，还要存储后继元素的存储地址

单链表的结构

单链表由一系列节点组成，每个节点包含两个部分：

数据域：存储实际的数据元素
指针域：指向下一个节点的地址

在C语言中，可以使用结构体和指针来实现单链表：

typedef int SLTDataType;  // 定义数据类型typedef struct SListNode {SLTDataType data;         // 数据域struct SListNode* next;   // 指针域（指向下一个节点）
} SLTNode;

链表的遍历

void SLTPrint(SLTNode* phead) {SLTNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;  // 指针后移}printf("NULL\n");  // 链表末尾为NULL
}

对链表的所有操作我们都是通过指针来进行的，那么我们想要遍历链表的数据，让指针动起来即可，cur=cur->next;这条语句就实现了让指针动起来，直到cur==NULL;的时候完成了链表的遍历

单链表的基本操作

链表的核心操作包括插入、删除、查找等。以下是具体实现及思路分析：

1. 节点创建

在进行插入操作前，需要创建新节点并分配内存：

SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode = (SLTDataType*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;return newnode;
}

2. 插入操作

插入操作分为头插和尾插：

// 头插：在链表头部插入新节点
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}// 尾插：在链表尾部插入新节点
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找尾SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

头插 vs 尾插：

头插时间复杂度为 O(1)，无需遍历链表
尾插需要遍历链表找到尾节点，时间复杂度为 O(n)

3. 删除操作

删除操作分为头删和尾删：

// 头删：删除链表的第一个节点
void SLTPopFront(SLTNode** pphead) {assert(*pphead != NULL);  // 确保链表不为空SLTNode* first = *pphead;*pphead = first->next;  // 更新头指针free(first);            // 释放原头节点内存
}// 尾删：删除链表的最后一个节点
void SLTPopBack(SLTNode** pphead) {assert(*pphead != NULL);  // 确保链表不为空if ((*pphead)->next == NULL) {free(*pphead);      // 只有一个节点，直接释放*pphead = NULL;} else {SLTNode* tail = *pphead;while (tail->next->next != NULL) {tail = tail->next;  // 找到倒数第二个节点}free(tail->next);  // 释放尾节点tail->next = NULL; // 倒数第二个节点的next置为NULL}
}

注意事项：

删除节点前必须保存其地址，否则会导致内存泄漏
尾删需要遍历链表，时间复杂度为 O(n)

4. 查找操作

查找指定值的节点，返回其地址：

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {SLTNode* ptr = phead;while (ptr != NULL) {if (ptr->data == x) {return ptr;  // 找到目标节点}ptr = ptr->next; // 继续查找}return NULL;  // 未找到
}

5. 指定位置插入与删除

在指定位置pos前后插入或删除节点：

// 在pos之前插入新节点
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pos != NULL);  // 确保pos有效if (pos == *pphead) {SLTPushFront(pphead, x);  // pos是头节点，直接头插} else {SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;  // 找到pos的前驱节点}SLTNode* newnode = BuySLTNode(x);prev->next = newnode;  // 插入新节点newnode->next = pos;}
}// 删除pos位置的节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pos != NULL && *pphead != NULL);  // 确保pos和链表有效if (pos == *pphead) {SLTPopFront(pphead);  // pos是头节点，直接头删} else {SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;  // 找到pos的前驱节点}prev->next = pos->next;  // 跳过pos节点free(pos);  // 释放pos节点内存}
}

6. 指定位置后插入与删除

在指定位置pos后插入或删除节点（效率更高）：

// 在pos之后插入新节点（时间复杂度O(1)）
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos != NULL);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;  // 新节点指向pos的后继pos->next = newnode;        // pos指向新节点
}// 删除pos之后的节点（时间复杂度O(1)）
void SLTEraseAfter(SLTNode* pos) {assert(pos != NULL && pos->next != NULL);  // 确保pos和其后继存在SLTNode* tmp = pos->next;pos->next = tmp->next;  // 跳过待删除节点free(tmp);  // 释放待删除节点内存
}