本文主要是介绍【数据结构初阶】链表分类与双向带头循环链表接口实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 1. 链表的分类
- 2. 双向带头循环链表接口实现
- 2. 1 结点声明
- 2. 2 创建链表节点
- 2. 3 初始化链表
- 2. 4 打印链表
- 2. 5 尾插
- 2. 6 判空
- 2. 7 尾删
- 2. 8 头插
- 2. 9 头删
- 2. 10 查找
- 2. 11 在指定位置删除与插入
- 2. 12 销毁
- 3. 链表接口测试
- 4. 单链表与双链表
- 5. 顺序表与链表
1. 链表的分类
链表的结构非常多样,以下情况组合起来就有8种(2x2x2)链表结构:
虽然有这么多的链表的结构,但是我们实际中最常用只有两种结构:单链表和双向带头循环链表。
- 无头单向非循环链表:也就是上一篇博客中的单链表,结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在题目中出现很多。
- 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。这个结构虽然结构复杂,但是使用代码实现以后会发现复杂的结构会带来很多优势,接口的实现反而简单了。
这篇博客将主要介绍双向带头循环链表(以下简称双链表)的接口实现。
我们不可能将以上8种链表的接口全部实现一遍,因为这没有意义,我们只需要将最简单和最复杂的链表实现一下,就可以很容易类推出其他链表的接口该怎么写了。
2. 双向带头循环链表接口实现
2. 1 结点声明
和单链表结点是相似的,只是除了指向下一个节点的指针之外,还要加上指向上一个节点的指针。
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next; //指向上一个节点struct ListNode* prev; //指向下一个节点
}ListNode;
2. 2 创建链表节点
ListNode* BuyListNode(LTDataType x);
和单链表一样,创建节点的操作也是经常需要进行的,所以我们先实现一下。
操作基本和单链表中的创建节点一样,只是要注意双链表中有两个指针需要进行初始化。
ListNode* BuyListNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL)return NULL;newnode->next = newnode->prev = NULL;newnode->data = x;return newnode;
}
2. 3 初始化链表
ListNode* ListCreate();
双链表是需要初始化的,因为它和单链表不同,它有一个不存储数据的头结点(哨兵位),那么这个初始化就是创建这个头结点。
另外需要注意,双链表还是一个循环链表,那么头结点中的prev
和next
指针都不能置为空,应该指向它本身,这样才能循环起来。
ListNode* ListCreate()
{ListNode* phead = BuyListNode(-1); //头结点不存储值,但是还是需要传递一个if (phead == NULL){perror("ListCreate()::malloc");exit(1);}phead->next = phead->prev = phead; //让这两个指针都指向它本身return phead;
}
2. 4 打印链表
void ListPrint(ListNode* phead);
打印链表也很简单,遍历链表,打印data
,但是问题在于:循环应该什么时候停下来?
我们在创建链表的时候给头结点存储了数据-1
,难道要通过判断结点数据是不是-1
吗?如果这样的话,如果链表中其他节点存储了-1
该怎么办呢?
正确的处理办法是,当cur
在遍历链表时,判断cur->next!=phead
是否成立就可以了。
void ListPrint(ListNode* phead)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n"); //打印完换行,方便连续打印
}
2. 5 尾插
void ListPushBack(ListNode* phead, LTDataType x);
我们先来看尾插,想要尾插,我们有这几个步骤:
- 创建新节点存储数据
- 新节点的下一个指向头结点
- 新节点的上一个指向原来的尾节点
- 原来的尾节点指向新节点
- 头节点的上一个指向新节点
我们该怎么找到尾节点呢?遍历链表吗?
并不需要,phead->prev
不就是尾节点了吗?
void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = BuyListNode(x);if (newnode == NULL){perror("ListPushBack()::malloc");exit(1);}//由于是通过phead->prev找到的尾节点,所以在对尾节点的操作完成之前,不能修改phead->prevnewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode; //这一步必须是最后一步,其他的顺序可以调换
}
可以发现,相对单链表,双链表的尾插的时间复杂度明显降低了。
单链表由于要遍历链表寻找尾节点,所以时间复杂度是O(N)
,但是双链表不需要,时间复杂度是O(1)
,这对于链表这样需要大量存储数据的数据结构来说是非常有优势的。
2. 6 判空
bool ListEmpty(ListNode* phead);
判断双链表中除了头节点是否还有其他节点,为后续的删除操作做准备。
逻辑很简单,判断头结点的下一个节点是不是头节点就可以了。
bool ListEmpty(ListNode* phead)
{assert(phead);return phead->next == phead;
}
2. 7 尾删
void ListPopBack(ListNode* phead);
尾删有这么几个步骤:
- 尾节点的上一个节点的
next
指针指向phead
- 头节点的
prev
指向尾节点的上一个节点 - 释放原本的尾节点
但是有一点需要注意,如果链表中只有一个头节点的话,我们就不能再删除了,否则结果无法预测。
void ListPopBack(ListNode* phead)
{assert(phead); //形参不为空指针assert(!ListEmpty(phead)); //链表不为空ListNode* del = phead->prev;//把原来的尾节点存储起来,方便使用del->prev->next = phead; //步骤1phead->prev = del->prev; //步骤2free(del); //步骤3del = NULL;
}
2. 8 头插
void ListPushFront(ListNode* phead, LTDataType x);
注意头插是在头结点后面插入,否则就成了尾插。
头插有这么几个步骤:
- 创建新节点存储数据
- 新节点的
prrev
指向phead
- 新节点的
next
指向phead->next
phead->next
的prev
指向新节点phead
的next
指向新节点(同样地,这一步也必须是最后一步)
void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = BuyListNode(x); //1newnode->prev = phead; //2phead->next->prev = newnode; //3newnode->next = phead->next; //4phead->next = newnode; //5
}
2. 9 头删
void ListPopFront(ListNode* phead);
注意头删是删除头节点后面的节点,而不是删除头结点。
头删有这么几个步骤:
- 判空,将要被删除的节点存储为
del
(和尾删一样,方便使用) phead
的next
指向del->next
del->next
的prev
指向phead
- 释放
del
2,3步没有顺序限制。
void ListPopFront(ListNode* phead)
{assert(phead);assert(!ListEmpty(phead));ListNode* del = phead->next;//1phead->next = del->next; //2del->next->prev = phead; //3free(del);del = NULL; //4
}
2. 10 查找
ListNode* ListFind(ListNode* phead, LTDataType x);
查找双链表中存储了数据x
的第一个节点,并返回节点,如果没有找到,就返回NULL
。
思路就是遍历链表,对比数据,而遍历链表已经在打印函数中解释过,这里便不再赘述。
这个函数为后续两个函数做准备。
ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x)return pcur;pcur = pcur->next;}return NULL;
}
2. 11 在指定位置删除与插入
删除
void ListErase(ListNode* pos);
删除是将pos
节点删除,pos
节点一般来自上面的查找函数。
但是查找函数可能会返回NULL
,所以要注意对pos
判空。
删除函数有这么几个步骤:
pos
判空- 将
pos
的上一个节点的next
置为pos
的下一个节点 - 将
pos
的下一个节点的prev
置为pos
的上一节点 - 释放
pos
2,3步没有固定顺序。
void ListErase(ListNode* pos)
{assert(pos); //1pos->prev->next = pos->next; //2pos->next->prev = pos->prev; //3free(pos);pos = NULL; //4
}
插入
void ListInsert(ListNode* pos, LTDataType x);
插入函数用于在pos
前插入节点。
插入有这几个步骤:
- 创建新节点
- 新节点的
next
指向pos
- 新节点的
prev
指向pos->prev
pos
的上一个节点的next
指向新节点pos
的prev
指向新节点
第5步必须在3,4步后面(建议直接放最后)。
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = BuyListNode(x); //1if (!newnode){perror("ListInsert()::malloc");exit(1);}newnode->next = pos; //2newnode->prev = pos->prev; //3pos->prev->next = newnode; //4pos->prev = newnode; //5
}
2. 12 销毁
void ListDestory(ListNode* phead);
双链表的节点也都是动态开辟出来的,所以也要记得释放,防止内存泄漏。
遍历链表逐个释放节点就可以了,注意为了顺利地遍历链表,要把头节点放到最后释放。
void ListDestory(ListNode* phead)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){ListNode* Next = pcur->next;free(pcur);pcur = Next;}free(phead);
}
3. 链表接口测试
事实上,我们本应该在实现一个接口后就对其进行测试,但是在博客中不方便频繁插入测试代码,所以我们在最后统一进行测试。
测试时,要注意要使用到所有的接口,并且在每一次接口调用之后,都对链表进行打印,观察是否符合预期。
#include"List.h"
void test1()
{ListNode* plist = ListCreate();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPrint(plist);ListPopBack(plist);ListPrint(plist);ListPopBack(plist);ListPrint(plist);ListPopBack(plist);ListPrint(plist);ListPopBack(plist);ListPrint(plist);//ListPopBack(plist); //用来测试当链表中只有一个头结点时,是否会按照预期报错ListPushFront(plist, 1);ListPushFront(plist, 2);ListPushFront(plist, 3);ListPushFront(plist, 4);ListPrint(plist);ListNode* pos = ListFind(plist, 4); //在这里多测试几个数,特别是特殊情况if (!pos)printf("没找到");elseListInsert(pos, 11); //在4前面加上一个11ListPrint(plist);ListErase(pos);ListPrint(plist);ListDestory(plist);plist = NULL;
}int main()
{test1();return 0;
}
测试结果:
4. 单链表与双链表
相比起单链表,由于双链表能够直接找到上一个节点,所以很多函数的实现不需要再遍历链表去找上一个节点,时间复杂度大大降低,这便是双链表的最大优势。
当然,头结点与循环结构同样带来了一些优势,可以自己体会一下。
5. 顺序表与链表
不同点 | 顺序表 | 链表 |
---|---|---|
存储空间 | 物理上连续 | 逻辑上连续,但物理上不一定连续 |
随机访问 | 支持:O(1) | 不支持:O(N) |
任意位置插入或删除 | 需要移动元素,效率低 | 只需改变指针指向,效率高 |
插入 | 动态顺序表,空间不够时需要扩容,会有空间浪费。静态顺序表空间不够便无法再插入 | 没有容量的概念,按需申请释放,没有空间浪费 |
应用场景 | 元素高速存储,频繁访问 | 任意位置高效插入删除 |
谢谢你的阅读,喜欢的话来个点赞收藏评论关注吧!
我会持续更新更多优质文章
这篇关于【数据结构初阶】链表分类与双向带头循环链表接口实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!