一、什么是双向链表
双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
二、双向链表的实现
List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}LTNode;
LTNode* LTInit();
void LTDestory(LTNode* phead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode * phead);
void LTPushBack(LTNode* phead,LTDataType x);
void LTPopBack(LTNode * phead);
void LTPushFront(LTNode *phead,LTDataType x);
void LTPopFront(LTNode* phead);
void LTInsert(LTNode* pos,LTDataType x);
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDataType x);
List.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
LTNode* BuyListNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("fail:malloc");
exit(-1);
}
node->next = NULL;
node->prev = NULL;
node->data = x;
return node;
}
LTNode* LTInit()
{
LTNode* phead = BuyListNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}
void LTPrint(LTNode* phead)
{
assert(phead);
printf("<=phead=>");
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d<=>",cur->data);
cur = cur->next;
}
printf("\n");
}
void LTPushBack(LTNode* phead,LTDataType x)
{
assert(phead);
LTInsert(phead,x);
}
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTErase(phead->prev);
}
void LTPushFront(LTNode* phead,LTDataType x)
{
assert(phead);
LTInsert(phead->next,x);
}
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTErase(phead->next);
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//在Pos前一个位置添加节点
void LTInsert(LTNode* pos,LTDataType x)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* p = pos->prev;
LTNode* n = pos->next;
p->next = n;
n->prev = p;
free(pos);
pos = NULL;
}
思路:
BuyListNode函数
BuyListNode的实现,我们在实现头插尾插时,为了更加遍历的实现功能，我们创建了BuyListNode函数，malloc一块新的空间，并且对其进行初始化，返回其类型
LTNode* BuyListNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("fail:malloc");
exit(-1);
}
node->next = NULL;
node->prev = NULL;
node->data = x;
return node;
}
LTInit函数
在实现该链表前，我们对其进行初始化，对其哨兵位的头节点，进行循环指向
哨兵位头节点的出现，使得链表添加与删除效率大大提高
LTNode* LTInit()
{
LTNode* phead = BuyListNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
LTInsert和LTErase函数
LTInsert函数的实现:
我们找到pos的前一个节点位置，进行操作，首先我们找到pos的前一个位置，保存该节点，创建新的节点，将pos前一个位置的节点next指向新节点，新节点的prev指向pos前一个位置，新节点的next指向pos，pos的前一个位置指向新节点
LTErase函数的实现：
删除pos位置的节点，先暴力检查是否为空，其中只有哨兵位的头节点，如果只有头节点则直接报错，保存pos位置节点的前一个节点和后一个节点，让pos的prev和next分别指向前一个位置和后一个位置的节点
void LTInsert(LTNode* pos,LTDataType x)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* p = pos->prev;
LTNode* n = pos->next;
p->next = n;
n->prev = p;
free(pos);
pos = NULL;
}
LTPushBack与LTPopBack函数
尾插与尾删功能，我们先对其进行暴力检查，通过LTInsert和LTErase函数进行实现该功能
void LTPushBack(LTNode* phead,LTDataType x)
{
assert(phead);
LTInsert(phead,x);
}
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTErase(phead->prev);
}
LTPushFront和LTPopFront函数
头插与头删功能，我们先对其进行暴力检查，通过LTInsert和LTErase函数进行实现该功能
void LTPushFront(LTNode* phead,LTDataType x)
{
assert(phead);
LTInsert(phead->next,x);
}
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTErase(phead->next);
}
LTDestory和LTPrint函数的实现
LTPrint: 当我们功能实现时，LTPrint函数可在控制台进行打印和输出，优先找到哨兵位头节点的下一位，我们对其进行循环，当循环节点等于哨兵位时，停止循环
LTDestory:当我们退出链表时，对其进行销毁
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}
void LTPrint(LTNode* phead)
{
assert(phead);
printf("<=phead=>");
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d<=>",cur->data);
cur = cur->next;
}
printf("\n");
}
ListTest.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
void ListTest()
{
LTNode* phead = LTInit();
LTPushBack(phead, 1);
LTPushBack(phead, 2);
LTPushBack(phead, 3);
LTPrint(phead);
LTPopBack(phead);
LTPrint(phead);
LTPushFront(phead,10);
LTPrint(phead);
LTPopFront(phead);
LTPrint(phead);
}
int main()
{
ListTest();
return 0;
}