快速通关双链表秘籍

1. 链表的分类

在前面我们已经讲过单链表，但是链表只有这一种形式吗？当然不是，链表有许多种类，如下图：

详细说明：

 注意这里的带头链表中的head中是无效数据，只是占位置，也就是哨兵位！第一个有效节点是d1!

虽然有这么多的链表的结构，但是我们实际中最常用法还是两种结构：单链表和双向带头循环链表

2. 双向链表

2.1 概念与结构

双链表全称：双向带头循环链表

注意：这里的头结点指的是第一个有效结点即d1，head在这里占位置，作为哨兵位！

3. 双链表的实现

3.1 尾插

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

 3.2 头插

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

3.3 判断链表是否为空

//判断链表是否为空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

3.4 尾删

//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

 3.5 头删

//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//phead del del->nextLTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;
}

3.6 指定位置插入数据

//指定位置插入数据
void LTInset(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyNode(x);//pos newnode pos->nextnewnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}

3.7 指定位置删除数据

//删除指定位置数据
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

 3.8 销毁

//销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = NULL;pcur = next;}free(phead);phead = NULL;
}

 4. 整体代码

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;//初始化
LTNode* LTInit();
//void LTInit(LTNode** pphead);//这里形参的改变要影响实参
//尾插
void LTPushBack(LTNode* phead,LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//打印
void LTPrint(LTNode* phead);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//查找指定位置数据
LTNode* LTFind(LTNode* phead,LTDataType x);
//指定位置插入数据
void LTInset(LTNode* pos, LTDataType x);
//删除指定位置数据
void LTErase(LTNode* pos);
//销毁
void LTDestroy(LTNode* phead);

List.c 文件

#include "List.h"LTNode* LTInit()
{LTNode* phead = (LTNode*)malloc(sizeof(LTNode));phead->data = -1;phead->prev = phead->next = phead;}
//void LTInit(LTNode** pphead)
//{
//	(*pphead)->data = -1;
//	(*pphead)->next = (*pphead)->prev = *pphead;
//
// }LTNode* BuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);//phead newnode phead->nextnewnode->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->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}
//打印双链表
void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d - > ", pcur->data);pcur = pcur->next;}
}
//判断链表是否为空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//phead del del->nextLTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;
}
//查找指定位置数据
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;
}
//指定位置插入数据
void LTInset(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyNode(x);//pos newnode pos->nextnewnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}
//删除指定位置数据
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}
//销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = NULL;pcur = next;}free(phead);phead = NULL;
}

test.c 文件

#include "List.h"void test()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);// //LTPushFront(plist, 1);//LTPrint(plist);//LTPushFront(plist, 2);//LTPushFront(plist, 3);//LTPushFront(plist, 4);//LTPushFront(plist, 5);//LTPrint(plist);//LTPopBack(plist);//LTPopBack(plist);//LTPopBack(plist);//LTPopBack(plist);//LTPopBack(plist);//LTPopBack(plist);//LTPopFront(plist);//LTPopFront(plist);//LTPopFront(plist);//LTPopFront(plist);//LTPopFront(plist);//LTNode* ret = LTFind(plist, 1);//if (ret)//	printf("找到了");//else//	printf("没找到");//LTNode* find = LTFind(plist, 5);LTInset(find, 2);LTPrint(plist);//LTErase(find);//LTPrint(plist);
}int main()
{test();return 0;
}