目录
一、链表的概念
链表是一种顺序表,它由一个一个的节点组成,该节点中存储着该节点的数据 val 和下一个结点的位置 next。最后一个节点的 next 指向NULL。
1. 链表的结构
链表的逻辑结构是连续的,但是物理结构通常是不连续的。因为在逻辑上,好像每个节点都是链接在一起的。
但是实际上,只是 next 存储了下一个结点的地址。
2. 链表的分类
链表通过是否带哨兵位头节点、是否循环还有单向和双向三个标准分为 8 种。
哨兵位头节点:不用来存储数据,仅占位,相当于一个站岗的士兵。有了它就不用判断是不是第一次插入数据。
循环:尾节点的 next 指向头节点,形成一个环。
双向:当前节点既有下一个节点的地址,也有上一个节点的地址。
3. 链表的优势
相比于顺序表,链表具有以下优势:
(1)不需要扩容,不会造成空间的浪费
因为链表插入数据时就申请一个节点,容量刚好。
(2)插入删除数据时不需要移动数据,只需要把新的节点链接进去或者把旧的节点解开释放即可。
二、链表的实现
不管是什么类型的链表,它的基本结构都是一个节点,该节点至少需要数据的值和下一个节点的地址两个成员。
不管是顺序表也好,链表也罢,无非就是增删查改。实现的功能都是一样的,只是使用的方法不同。
下面先实现一个最基本的无头单项非循环链表,然后再实现一个带头双向循环链表。当你完成第一个链表的实现再去看第二个链表时,你会觉得非常简单。等你这两个链表都能实现的时候,你会发现链表也就这样。
1. 无头单项非循环链表的实现
老样子,分成三个文件:头文件、方法实现文件和测试文件。
头文件:ListNode.h
// 头文件
#include <stdio.h>
// 无头单向非循环链表
// 类型声明
typedef int DataType;
// 节点结构声明
typedef struct ListNode
{
DataType val; // 数据
struct ListNode* next; // 下一个结点的位置
}ListNode;
// 方法
// 获得节点
ListNode* BuyNode(DataType data);
// 头插
void ListPushFront(ListNode** pphead, DataType data);
// 头删
void ListPopFront(ListNode** pphead);
// 尾插
void ListPushBack(ListNode** pphead, DataType data);
// 尾删
void ListPopBack(ListNode** pphead);
// 查找
ListNode* ListFind(ListNode** pphead, DataType data);
// 插入
void ListInsert(ListNode* pos, DataType data);
// 删除
void ListErase(ListNode* pos);
// 打印链表
void ListPrint(const ListNode** pphead);
// 销毁链表
void ListDestory(ListNode** pphead);
方法实现文件:ListNode.c
// 头文件
#include "ListNode.h"
#include <assert.h>
#include <stdlib.h>
// 方法
// 获得节点
ListNode* BuyNode(DataType data)
{
// 申请节点
ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
if (NULL == new_node)
{
perror("BuyNode::malloc: ");
exit(-1);
}
// 赋值
new_node->val = data;
new_node->next = NULL;
// 返回
return new_node;
}
// 头插
void ListPushFront(ListNode** pphead, DataType data)
{
assert(pphead);
// 获得新节点
ListNode* new_node = BuyNode(data);
// 链接
new_node->next = *pphead;
*pphead = new_node;
}
// 头删
void ListPopFront(ListNode** pphead)
{
assert(pphead);
// 空表
if (NULL == *pphead)
{
printf("Empty List!\n");
exit(-1);
}
// 删除
ListNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
// 尾插
void ListPushBack(ListNode** pphead, DataType data)
{
assert(pphead);
// 获得新节点
ListNode* new_node = BuyNode(data);
// 头插判断
if (NULL == *pphead)
{
*pphead = new_node;
}
else
{
// 找尾
ListNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
// 链接
tail->next = new_node;
}
}
// 尾删
void ListPopBack(ListNode** pphead)
{
assert(pphead);
// 空表
if (NULL == *pphead)
{
printf("Empty List!\n");
exit(-1);
}
// 头删判断
if (NULL == (*pphead)->next)
{
free(*pphead);
*pphead = NULL;
}
else
{
// 找尾前节点
ListNode* pre_tail = *pphead;
while (pre_tail->next->next)
{
pre_tail = pre_tail->next;
}
// 释放尾
free(pre_tail->next);
// 新尾后置空
pre_tail->next = NULL;
}
}
// 查找
ListNode* ListFind(ListNode** pphead, DataType data)
{
assert(pphead);
ListNode* cur = *pphead;
while (cur)
{
// 找到了
if (cur->val == data)
return cur;
// 下一个
cur = cur->next;
}
// 没找到
return NULL;
}
// 插入
void ListInsert(ListNode* pos, DataType data)
{
assert(pos);
// 申请新节点
ListNode* new_node = BuyNode(data);
// 链接
new_node->next = pos->next;
pos->next = new_node;
}
// 删除
void ListErase(ListNode* pos)
{
assert(pos);
// 记录删除位
ListNode* del = pos->next;
// 链接
pos->next = pos->next->next;
// 删除
free(del);
}
// 打印链表
void ListPrint(const ListNode** pphead)
{
assert(pphead);
// 打印
const ListNode* cur = *pphead;
while (cur)
{
printf("%d ", cur->val);
// 下一个节点
cur = cur->next;
}
printf("\n");
}
// 销毁链表
void ListDestory(ListNode** pphead)
{
assert(pphead);
// 销毁
ListNode* cur = *pphead;
while (cur)
{
// 存储下一个节点
ListNode* next = cur->next;
// 删除当前节点
free(cur);
// 下一个节点
cur = next;
}
// 置空
*pphead = NULL;
}
测试文件:test.c
// 头文件
#include "ListNode.h"
// 头插头删测试
void test1()
{
ListNode* phead = NULL;
// 头插
int i = 0;
for (i = 0; i < 5; ++i)
{
ListPushFront(&phead, i);
}
ListPrint(&phead);
// 头删
for (i = 0; i < 5; ++i)
{
ListPopFront(&phead);
printf("头删 %d 次: ", i+1);
ListPrint(&phead);
}
// 销毁链表
ListDestory(&phead);
}
// 尾插尾删测试
void test2()
{
ListNode* phead = NULL;
// 尾插
int i = 0;
for (i = 0; i < 5; ++i)
{
ListPushBack(&phead, i);
}
ListPrint(&phead);
// 尾删
for (i = 0; i < 5; ++i)
{
ListPopBack(&phead);
printf("尾删 %d 次: ", i+1);
ListPrint(&phead);
}
// 销毁
ListDestory(&phead);
}
// 插入删除查找测试
void test3()
{
ListNode* phead = NULL;
// 尾插
int i;
for (i = 1; i <= 5; ++i)
{
ListPushBack(&phead, i);
}
ListPrint(&phead);
// 在每个数据后面插入 9
for (i = 1; i <= 5; ++i)
{
// 找位置
ListNode* pos = ListFind(&phead, i);
// 在后面插入 9
ListInsert(pos, 9);
}
ListPrint(&phead);
// 删除 9
for (i = 1; i <= 5; ++i)
{
// 找位置
ListNode* pos = ListFind(&phead, i);
// 在后面插入 9
ListErase(pos);
}
ListPrint(&phead);
// 销毁
ListDestory(&phead);
}
int main()
{
// 头插头删测试
printf("头插头删测试:\n");
test1();
// 尾插尾删测试
printf("\n\n尾插尾删测试:\n");
test2();
// 插入删除查找测试
printf("\n\n插入删除查找测试:\n");
test3();
return 0;
}
程序测试结果:
1.1 代码说明
1. 为什么使用二级指针?
首先,只要是插入操作,当插入第一个节点的时候需要改变头节点的指向,那么只有传入头节点的指针才能改变它的值。删除也是一个道理,当删除最后一个节点时,需要把头节点置空,也需要二级指针。所以这里已经有六个函数需要传递二级指针了,那么干脆把所有函数都设计成传递二级指针,这样既方便又统一。
2. 为什么需要对 pphead 断言?
这里要知道 pphead 是什么,它是头节点指针的地址。这个头节点指针是一定存在的,所以它的地址一定不是 NULL。
3. 为什么 ListInsert() 和 ListErase() 都是在给定位置之后插入删除?
如果在给定位置之前进行插入删除,需要遍历链表,找到前一个位置,这样就消耗了时间。而在给定位置之后插入删除,只需要链接上或者断开链接释放即可。
4. 尾插尾删需要进行判断
尾插需要判断是否是第一次插入,因为第一次插入需要改变头节点的位置。若不是第一次插入就需要寻找尾节点,然后再进行插入。
尾删需要判断是否是最后一个节点,因为删除完最后一个节点需要把头节点置空。若不是最后一个节点,需要找到尾节点的前一个节点,然后进行删除。
2. 带头双向循环链表的实现
有了前面无头单项不循环链表的基础,现在来实现这个带头双向循环链表那就是 so easy!这个新链表的节点在原来的基础上增加了一个 pre 指针,指向前一个节点。由于哨兵位头节点初始状态 pre 和 next 都指向自己,所以该链表的头节点需要使用一个函数来初始化并返回。令人最兴奋的是,该表的尾插和尾删都不要判断,而且所有函数都可以只传一级指针。
头文件:ListNode.h
// 头文件
#include <stdio.h>
// 带头双向循环链表
// 类型声明
typedef int DataType;
// 链表节点声明
typedef struct ListNode
{
DataType val; // 数据
struct ListNode* pre; // 前一个节点的地址
struct ListNode* next; // 下一个节点的地址
}ListNode;
// 方法
// 获得哨兵位头节点
ListNode* ListCreate();
// 获得新节点
ListNode* BuyNode(DataType data);
// 头插
void ListPushFront(ListNode* phead, DataType data);
// 头删
void ListPopFront(ListNode* phead);
// 尾插
void ListPushBack(ListNode* phead, DataType data);
// 尾删
void ListPopBack(ListNode* phead);
// 插入
void ListInsert(ListNode* pos, DataType data);
// 删除
void ListErase(ListNode* pos);
// 打印
void ListPrint(const ListNode* phead);
// 查找
ListNode* ListFind(const ListNode* phead, DataType data);
// 销毁
void ListDestory(ListNode* phead);
方法实现文件:ListNode.c
// 头文件
#include "ListNode.h"
#include <stdlib.h>
#include <assert.h>
// 方法
// 获得哨兵位头节点
ListNode* ListCreate()
{
// 申请新节点
ListNode* phead = BuyNode(0);
// 初始化
phead->next = phead->pre = phead;
phead->val = 0;
// 返回
return phead;
}
// 获得新节点
ListNode* BuyNode(DataType data)
{
// 申请新节点
ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
if (NULL == new_node)
{
perror("ListCreate::malloc: ");
exit(-1);
}
// 初始化
new_node->next = new_node->pre = NULL;
new_node->val = data;
// 返回
return new_node;
}
// 头插
void ListPushFront(ListNode* phead, DataType data)
{
assert(phead);
// 获得新节点
ListNode* new_node = BuyNode(data);
// 前后链接
ListNode* next = phead->next;
new_node->next = next;
next->pre = new_node;
new_node->pre = phead;
phead->next = new_node;
}
// 头删
void ListPopFront(ListNode* phead)
{
assert(phead);
// 空表
if (phead->next == phead)
{
printf("Empty List!\n");
exit(-1);
}
// 存储下一个节点
ListNode* next = phead->next->next;
// 删除头节点
free(phead->next);
next->pre = phead;
phead->next = next;
}
// 尾插
void ListPushBack(ListNode* phead, DataType data)
{
assert(phead);
// 申请新节点
ListNode* new_node = BuyNode(data);
// 链接
ListNode* tail = phead->pre;
tail->next = new_node;
new_node->pre = tail;
new_node->next = phead;
phead->pre = new_node;
}
// 尾删
void ListPopBack(ListNode* phead)
{
assert(phead);
// 空表
if (phead->next == phead)
{
printf("Empty List!\n");
exit(-1);
}
// 存储尾前节点
ListNode* new_tail = phead->pre->pre;
free(phead->pre);
new_tail->next = phead;
phead->pre = new_tail;
}
// 插入
void ListInsert(ListNode* pos, DataType data)
{
// 申请新节点
ListNode* new_node = BuyNode(data);
// 链接
ListNode* pre = pos->pre;
pre->next = new_node;
new_node->pre = pre;
new_node->next = pos;
pos->pre = new_node;
}
// 删除
void ListErase(ListNode* pos)
{
// 链接前后
ListNode* pre = pos->pre;
pre->next = pos->next;
pos->next->pre = pre;
// 释放当前结点
free(pos);
}
// 打印
void ListPrint(const ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->val);
// 下一个节点
cur = cur->next;
}
printf("\n");
}
// 查找
ListNode* ListFind(const ListNode* phead, DataType data)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
// 找到了
if (cur->val == data)
return cur;
// 下一个节点
cur = cur->next;
}
// 没找到
return NULL;
}
// 销毁
void ListDestory(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
// 存储下一个节点
ListNode* next = cur->next;
// 删除当前节点
free(cur);
// 下一个节点
cur = next;
}
// 释放哨兵位头节点
free(phead);
}
测试文件:test.c
// 头文件
#include "ListNode.h"
// 头插头删测试
void test1()
{
// 创建链表
ListNode* phead = ListCreate();
// 头插
int i = 0;
for (i = 0; i < 5; ++i)
{
ListPushFront(phead, i);
}
ListPrint(phead);
// 头删
for (i = 0; i < 5; ++i)
{
ListPopFront(phead);
printf("头删 %d 次: ", i + 1);
ListPrint(phead);
}
// 销毁
ListDestory(phead);
phead = NULL;
}
// 尾插尾删测试
void test2()
{
ListNode* phead = ListCreate();
// 尾插
int i;
for (i = 0; i < 5; ++i)
{
ListPushBack(phead, i);
}
ListPrint(phead);
// 尾删
for (i = 0; i < 5; ++i)
{
ListPopBack(phead);
printf("尾删 %d 次: ", i+1);
ListPrint(phead);
}
// 销毁
ListDestory(phead);
phead = NULL;
}
// 插入删除查找测试
void test3()
{
// 创建链表
ListNode* phead = ListCreate();
// 尾插
int i;
for (i = 0; i < 5; ++i)
{
ListPushBack(phead, i);
}
ListPrint(phead);
// 插入
for (i = 0; i < 5; ++i)
{
ListNode* pos = ListFind(phead, i);
ListInsert(pos, 9);
}
ListPrint(phead);
// 删除
for (i = 0; i < 5; ++i)
{
ListNode* pos = ListFind(phead, i);
ListErase(pos);
}
ListPrint(phead);
// 销毁
ListDestory(phead);
phead = NULL;
}
int main()
{
头插头删测试
//test1();
尾插尾删测试
//test2();
// 插入删除查找测试
test3();
return 0;
}
程序测试结果:
2.1 代码说明
1. 所有函数都只传一级指针
因为有哨兵位头节点的存在,不管是增删查改哪个功能都只需要一级指针。只是销毁链表需要在外头置空。
2. 尾插和尾删不需要检查和找尾
即使表中没有数据节点,但是还存在哨兵位头节点。且它的前一个就是尾节点,不需要寻找。
3. ListInsert() 和 ListErase() 函数可以在当前位置之前进行操作
由于该链表是双向的,不需要遍历寻找前一个节点。所以可以删除当前位置的节点和在当前节点的前面插入节点。
三、链表和顺序表的区别
上面的图片是偷课件的,下面作者用自己的理解来说明一下:
(1)顺序表是使用数组实现的,在内存中的存储是连续的。而链表是通过申请一个个节点链接在一起的,物理上是不连续的(极低概率的就不要来抬杠了)。
(2)顺序表支持随机访问,时间复杂度为O(1);而链表不支持随机访问,需要从头节点开始寻找,时间复杂度为O(N)。
(3)顺序表在插入元素的时候可能会触发增容,可能会造成空间浪费;链表没有增容这个说法,每次插入都申请一个新的节点,需要多少就申请多少,不存在浪费。
(4)顺序表在插入和删除元素时,时间复杂度最高为O(N),最低为O(1),分别对应头插头删和尾插尾删,平均时间复杂度为O(N)。而链表其实也和顺序表差不多,头插头删为O(1),尾插尾删为O(N),平均时间复杂度也是O(N)。但是由于顺序表存在增容,所以链表还是优于顺序表。
(5)顺序表的缓存利用率远高于链表。
关于缓存利用率这个概念,大家就只能自己下去了解一下了,我只能偷张图来帮助大家。
四、链表总结
其实在写完带头双向循环链表的时候,大家心中肯定在想,这个 3 层 buff 的表这么牛逼,为什么还要使用无头单项非循环链表。这是因为出面试题的时候使用的链表基本上是后者,如果给你前者,那么题目就会变得很简单。再者,无头单项非循环链表是一些复杂数据结构的子结构,一般不单独使用。
而带头双向循环链表可以根据使用场景来使用。
标签:pphead,ListNode,语言,next,链表,phead,节点 From: https://blog.csdn.net/weixin_70742989/article/details/143493747