4.双向链表
4.1 概念与结构
在带头链表中,除了
Head
哨兵位节点,其他节点都存储有效数据。之前在单链表里面写的
phead
表述的头节点,只是为了表示这是链表的第一个结点,并不是真的哨兵位,因为里面是存储数据的。哨兵位节点才是真正的头节点。
注意:这里的“带头”跟前面我们说的“头结点”是两个概念,实际前面的在单链表阶段称呼不严谨,但是为了同学们更好的理解就直接称为单链表的头结点。
带头链表里的头结点,实际为“哨兵位”,哨兵位结点不存储任何有效元素,只是站在这里“放哨的”,也就是占位子的。
4.2 实现双向链表
双向链表结构相较于单链表来说要复杂一些,但是接口的实现上要比单链表简单很多。
双向链表的节点结构:数据+指向后一个节点的指针+指向前一个结点的指针
struct ListNode{
int data;//数据
struct ListNode* next;//指向后一个节点的指针
struct ListNode* prev;//指向前一个结点的指针
}
List.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
//定义双向链表结点结构
typedef int LTDataType;
typedef struct ListNode {
LTDataType data;//数据
struct ListNode* next;//指向后一个节点的指针
struct ListNode* prev;//指向前一个结点的指针
}LTNode;
//为了保持接口一致性,优化接口都为一级指针
//双向链表的初始化
//void LTInit(LTNode** pphead);//类似于拿一个空瓶子让商家给我装饮料
LTNode* LTInit();//商家直接给一个瓶装的饮料
//双向链表的销毁
void LTDesTroy(LTNode** pphead);
void LTDesTroy2(LTNode* phead);//传一级指针需要手动将plist置为NULL
//打印链表
void LTPrint(LTNode* phead);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//插入
//第一个参数传一级指针还是二级指针,要看pphead指向的结点会不会发生改变
//如果发生改变,那么pphead的改变要影响实参,传二级指针
//如果不发生改变,pphead不会影响实参,传一级指针
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//删除
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//在双链表中查找特定数据x
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除指定位置的结点
void LTErase(LTNode* pos);
List.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
LTNode* LTBuyNode(LTDataType x) {
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL) {
perror("malloc fail!");
exit(1);
}
newnode->data = x;
//prev next
newnode->next = newnode->prev = newnode;
return newnode;
}
//双向链表的初始化
/*
void LTInit(LTNode** pphead) {
//创建一个头节点(哨兵位)
*pphead = LTBuyNode(-1);
}
*/
LTNode* LTInit() {
LTNode* phead = LTBuyNode(-1);
return phead;
}
//双向链表的销毁
void LTDesTroy(LTNode** pphead) {
assert(pphead && *pphead);//*pphead哨兵位不为空
LTNode* pcur = (*pphead)->next;
while (pcur != pphead) {
LTNode* Next = pcur->next;
free(pcur);
pcur = Next;
}
pcur = NULL;
free(*pphead);//释放哨兵位
*pphead = NULL;
}
void LTDesTroy2(LTNode* phead) {
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead) {
LTNode* Next = pcur->next;
free(pcur);
pcur = Next;
}
free(phead);//释放哨兵位
phead = pcur = NULL;
}
//打印链表
void LTPrint(LTNode* phead) {
LTNode* pcur = phead->next;
while (pcur != phead) {
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
//判断链表是否为空
bool LTEmpty(LTNode* phead) {
assert(phead);
return phead->next == phead;
}
//插入
//第一个参数传一级指针还是二级指针,要看pphead指向的结点会不会发生改变
//如果发生改变,那么pphead的改变要影响实参,传二级指针
//如果不发生改变,pphead不会影响实参,传一级指针
//第一个结点:第一个有效的结点
//哨兵位:头节点
//尾插
void LTPushBack(LTNode* phead, LTDataType x) {
assert(phead);
LTNode* newnode = LTBuyNode(x);
//newnode->prev指向前一个结点
//newnode->next指向哨兵位
//phead->prev指向newnode
newnode->next = phead;//将新结点的 next 指针指向哨兵位,即链表的头部。
newnode->prev = phead->prev;//将新结点的 prev 指针指向链表的最后一个有效结点,即链表的尾部。
phead->prev->next = newnode;//更新链表最后一个有效节点的 next 指针,这样就完成了新节点与链表尾部的链接。
phead->prev = newnode;//更新哨兵位的 prev 指针,使其指向新结点,这样新结点就成为了链表的新尾部。
}
//头插
//指的不是插到哨兵结点之前,而是指的插到哨兵结点和第一个有效结点之间
void LTPushFront(LTNode* phead, LTDataType x) {
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
//删除
//尾删
void LTPopBack(LTNode* phead) {
assert(phead);
assert(!LTEmpty(phead));//判断链表不为空
LTNode* del = phead->prev;//del指向要删除的尾结点
LTNode* prev = del->prev;//prev指向删完后的新的尾结点
prev->next = phead;//删完后的新的尾结点指向头节点
phead->prev = prev;//phead->prev指向删完后的新的尾结点
free(del);
del = NULL;
}
//头删
//指的不是插到哨兵结点之前,而是指的插到哨兵结点和第一个有效结点之间
void LTPopFront(LTNode* phead) {
assert(phead);
assert(!LTEmpty(phead));
LTNode* del = phead->next;//del指向要删除的第一个有效结点
del->next->prev = phead;//让要删除的后面那个节点指向head头节点
phead->next = del->next;//让head头节点指向要删除的后面那个节点
free(del);
del = NULL;
}
//在双链表中查找特定数据x
LTNode* LTFind(LTNode* phead, LTDataType x) {
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead) {
if (pcur->data == x) {
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x) {
assert(pos);
LTNode* newnode = LTBuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
//删除指定位置的结点
void LTErase(LTNode* pos) {
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
void ListTest01() {
//创建双向链表变量
//LTNode* plist = NULL;
LTNode* plist = LTInit();
LTInit(&plist);
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
/*LTDesTroy2(plist);
plist = NULL;*/
/*LTDesTroy(&plist);*/
/*LTNode* pos = LTFind(plist, 4);
LTErase(pos);
LTPrint(plist);*/
/*LTNode* pos = LTFind(plist, 4);
LTInsert(pos, 44);
LTPrint(plist);*/
/*LTNode* pos = LTFind(plist, 7);
if (pos == NULL) {
printf("没有找到!\n");
}
else {
printf("找到了!\n");
}*/
/*LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);*/
/*LTPopBack(plist);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);*/
/*LTPushFront(plist, 1);
LTPrint(plist);
LTPushFront(plist, 2);
LTPrint(plist);
LTPushFront(plist, 3);
LTPrint(plist);
LTPushFront(plist, 4);
LTPrint(plist);*/
}
int main() {
ListTest01();
return 0;
}