文章目录
- 一、 双向链表的结构
- 二、循环链表的结构
- 三、单链表和循环单链表
- 四、带头双向循环链表实现
-
- 4.1接口函数定义
- 4.2初始化/销毁/打印/查找
- 4.3插入
- 4.4删除
- 4.5头尾插入删除
一、 双向链表的结构
单链表的结点中保存了指向后继结点的地址，所以单链表中找当前结点的后继结点很容易，但要获取当前结点的前驱结点就很麻烦，就只能从头开始往后遍历获取，时间复杂度为O(n)；所以单链表中只有当前结点的指针pos时(没有头指针)，想要在pos之前插入结点和删除pos位置结点都是无法实现的。
- 双向链表相比单链表最大的特征是每个结点中多了一个前驱指针，一些场景需要获取当前结点前驱结点的场景中就需要用双链表实现，如：倒着遍历、删除当前结点、在当前结点前插入结点等。
- 双向链表的一些不足是找尾结点依旧不是很方便，另外呢，头尾插入删除考虑的边界依旧比较多。后面的带头双向循环链表可以很好的解决这个问题
typedef int DLDataType;
typedef struct DListNode {
DLDataType data; // 存放数据元素
struct DListNode* prev; // 指向前驱结点
struct DListNode* next; // 指向后继结点
}DNode, *DLinkList;
二、循环链表的结构
实践应用中链表最常见的操作并非在第i个位序插入删除数据，而是在头尾插入删除数据，前面的单链表头插头删效率高，可以做到时间复杂度O(1)，但是尾插尾删，需要找到尾结点，复杂度为O(n)，也就是说单链表结构适合头插头删，这个在后面单链表作为复杂数据结构的子结构中可以看到主要就使用它的头插头删。
-
双向链表头插头删效率高，确定某个结点位置以后插入删除效率也很高，均可以做到时间复杂度O(1)，但是同样尾插尾删，需要增加一个尾指针，相对麻烦；所以这里我们引用一个新的结构，循环链表可以解决这里的问题。
-
下图是单向循环链表和双向循环链表，单向循环链表就是让尾结点的next指向头结点；双向循环链表就是尾结点的next指向头结点，同时头结点的prev指向尾结点。
-
实践中双向循环链表非常实用，C++标准库(STL)中list就是使用的这个结构实现，因为它可以通过头结点的prev指针找到尾结点，轻松实现O(1)尾插尾删。也就是说这个结构头尾插入删除效率都是O(1)，确定某个结点位置以后的插入删除也是O(1)。下面我们会重点实现这个结构
三、单链表和循环单链表
- 循环单链表与单链表的结构体定义和大多数操作基本是一样的，需要注意的主要是以下一些不同。
- 初始化不同，循环单链表初始化时要让头结点的next指向自己。
// 单链表
void InitList(LinkList& L){
L = BuyListNode(–1);
L->next = NULL;
}
// 循环单链表
void InitCList(CLinkList& L){
L = BuyCListNode(–1);
L->next = L;
}
- 遍历时判断结束的逻辑不同，循环单链表遍历不能让迭代指针指向空作为结束条件，而是走一圈等于头结点时结束。
// 单链表
int ListSize(LinkList L){
int size = 0;
ListNode* cur = L->next;
while(cur){
size++;
cur = cur->next;
}
return size;
}
// 循环单链表
int CListSize(CLinkList L){
int size = 0;
CListNode* cur = L->next;
while(cur != L){
size++;
cur = cur->next;
}
return size;
}
四、带头双向循环链表实现
4.1接口函数定义
// DCList.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DCLDataType;
typedef struct DCListNode {
DCLDataType data; // 存储数据元素的值
struct DCListNode* prev; // 存放前驱结点的指针
struct DCListNode* next; // 存放后继结点的指针
}DCListNode;
// 链表初始化
DCListNode* DCListInit();
// 销毁链表
void DCListDestroy(DCListNode* L);
// 获取链表的位序i的结点
DCListNode* DCListGetElem(DCListNode* L, int i);
// 在pos位置后插入值为x的结点
void DCListInsert(DCListNode* pos, DCLDataType x);
// 删除pos位置的结点
void DCListDelete(DCListNode* pos);
// 头插
void DCListPushFront(DCListNode* L, DCLDataType x);
// 尾插
void DCListPushBack(DCListNode* L, DCLDataType x);
// 头删
void DCListPopFront(DCListNode* L);
// 尾删
void DCListPopBack(DCListNode* L);
// 打印链表中的元素
void DCListPrint(DCListNode* L);
4.2初始化/销毁/打印/查找
// 链表初始化
DCListNode* DCListInit() {
DCListNode* L = BuyDCListNode(–1);
L->next = L;
L->prev = L;
return L;
}
// 销毁链表
void DCListDestroy(DCListNode* L) {
DCListNode* cur = L->next;
while (cur != L) {
DCListNode* next = cur->next;
free(cur);
cur = next;
}
free(L);
}
// 获取链表的下标i的结点
DCListNode* DCListGetElem(DCListNode* L, int i) {
assert(L);
assert(i >= 0);
// 从链表头结点之后开始，逐个往后找第i个结点
DCListNode* cur = L->next;
int j = 0;
while (cur != L && j < i) {
cur = cur->next;
++j;
}
// j < i说明没第i个结点，参数i非法
assert(j == i);
return cur;
}
void DCListPrint(DCListNode* L) {
// 从前往后打印链表
printf("头结点->");
DCListNode* cur = L->next;
while (cur != L) {
printf("%d->", cur->data);
cur = cur->next;
}
// 从后往前打印链表
DCListNode* cur = L->prev;
while (cur != L) {
printf("%d->", cur->data);
cur = cur->prev;
}
printf("NULL\\n");
}
4.3插入
// 在pos位置后插入值为x的结点
void DCListInsert(DCListNode* pos, DCDataType x) {
assert(pos);
DCListNode* newNode = BuyDCListNode(x);
DCListNode* posNext = pos->next;
// pos newNode posNext
// 注意顺序
newNode->next = pos->next;
pos->next->prev = newNode;
pos->next = newNode;
newNode->prev = pos;
}
4.4删除
// 删除pos位置的结点
void DCListDelete(DCListNode* pos) {
assert(pos);
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
}
4.5头尾插入删除
// 头插
void DCListPushFront(DCListNode* L, DCListDataType x){
assert(L);
DCListInsert(L, x);
}
// 尾插
void DCListPushBack(DCListNode* L, DCListDataType x){
assert(L);
DCListInsert(L->prev, x);
}
//头删
void DCListPopFront(DCListNode* L) {
assert(L);
assert(L->next != L); // 链表非空校验
DCListDelete(L->next);
}
// 尾删
void DCListPopBack(DCListNode* L) {
assert(L);
assert(L->next != L); // 链表非空校验
DCListDelete(L->prev);
}
