内容导读
?2.12双链表的元素查找，若找到目的值i则返回其地址pos，否则返回NULL
2.13双链表的元素查找修改，若找到目的值i则将i修改成e，并返回其地址，否则返回NULL
1.什么是双链表
1.1 双链表概述
在线性表的链式存储结构中，每个物理结点增加一个指向后继结点的指针域（后指针）和一个指向前驱结点的指针域（前指针） ->双链表。
?举个栗子：带头结点双链表结构
1.2循环链表
循环链表是另一种形式的链式存储结构形式。?
所以说双链表的形式就会有多种啦，比如循环双链表，带头结点的双链表，带头结点的循环双链表，带头结点的双链表等等。不过本质都是一样的，只需要学会任意一种，其他的只要注意一些不同的细节也能轻松实现。
1.3?双链表的优点
- 从任一结点出发可以快速找到其前驱结点和后继结点；
- 从任一结点出发可以访问其他结点。
双链表相比于单链表来说，双链表能够从任何一个结点访问其他任意结点，而单链表只能单方向访问下一个结点。虽然双链表的结构较比与单链表要复杂，但是双链表的操作要相比于单链表简单。
在本文中，双链表所有实现方式以带头结点的循环双链表为基础实现。
2.双链表的定义以及常见功能的实现
2.0双链表定义以及常见功能头文件
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int ListType;
typedef struct ListNode //声明双链表结点结构
{
ListType data; //存储数据：data
struct ListNode* prev; //指向前驱结点：前指针
struct ListNode* next; //指向后继结点：后指针
}ListNode;
//实现双链表增删查改接口
//双链表的初始化
ListNode* ListInit();
//双链表的打印
void ListPrint(ListNode* phead);
//双链表的头插
void ListPushFront(ListNode* phead,ListType x);
//双链表的头删
void ListPopFront(ListNode* phead);
//双链表的尾插
void ListPushBack(ListNode* phead, ListType x);
//双链表的尾删
void ListPopBack(ListNode* phead);
//双链表结点的扩容
ListNode* BuyListNode(ListType x);
//双链表的位置pos（已知）前插入
void ListInsert( ListNode* pos, ListType x);
//双链表的位置pos（已知）删除
void ListErase( ListNode* pos);
//双链表的元素查找，若找到目的值i则返回其地址pos，否则返回NULL
ListNode* ListFind(ListNode* phead, ListType i);
//双链表的元素查找修改，若找到目的值i则将i修改成e，并返回其地址，否则返回NULL
ListNode* ListReplace(ListNode* phead, ListType i, ListType e);2.1双链表定义（声明）
对于双链表，采用类似于单链表的类型定义，其结点类型ListNode声明如下：
typedef int ListType;
typedef struct ListNode //声明双链表结点结构
{
ListType data; //存储数据：data
struct ListNode* prev; //指向前驱结点：前指针
struct ListNode* next; //指向后继结点：后指针
}ListNode;2.2双链表内存申请及扩容
//双链表结点申请及扩容
ListNode* BuyListNode(ListType x)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); //新结点内存申请
if (newNode == NULL) {
printf("申请内存失败！");
return NULL;
}
newNode->next = NULL;
newNode->prev = NULL;
newNode->data = x;
return newNode; //将新申请的结点的前后指针置空，存入数据，返回新结点的地址
}2.3双链表初始化
//双链表的初始化
ListNode* ListInit()
{
ListNode* phead = BuyListNode(0); //申请新结点作为头指针
phead->next = phead; //初始化的双链表前后指针均指向本身
phead->prev = phead;
return phead; //返回指针地址
}2.4双链表的打印
需要打印双链表中的每个数据，就需要遍历整个双链表，需要遍历双链表，那就要找到遍历双链表的条件，由于我是以带头结点的循环双链表为基础，那么遍历终结的条件不是指向NULL，而是指向头结点地址，因为当遍历完一次后，指针就会指向初始结点。
//双链表的打印
void ListPrint(ListNode* phead)
{
assert(phead); //判断传入的地址是否为空，为空强制结束程序
ListNode* cur = phead->next;
while (cur!=phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}2.5双链表的插入与删除操作理论
双链表插入操作
?双链表删除操作
?2.6双链表头插操作代码实现
?双链表的头插相当于在第一个数据前插入
//双链表的头插
void ListPushFront(ListNode* phead, ListType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
ListNode* next = phead->next; //保存第一个数据地址
phead->next = newNode;
newNode->prev = phead;
next->prev = newNode;
newNode->next = next;
}2.7双链表尾插操作代码实现
双链表的尾插相当于在头结点前插入
//双链表的尾插
void ListPushBack(ListNode* phead, ListType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
ListNode* tail = phead->prev; //保存最后一个数据地址
phead->prev = newNode;
newNode->next = phead;
tail->next = newNode;
newNode->prev = tail;
}?2.8双链表的位置pos（已知）前插入操作代码实现
//双链表的位置pos（已知）前插入
void ListInsert(ListNode* pos, ListType x)
{
assert(pos);
ListNode* newNode= BuyListNode(x);
ListNode* posPrev = pos->prev;
pos->prev = newNode;
newNode->next = pos;
posPrev->next = newNode;
newNode->prev = posPrev;
}2.9双链表的头删操作代码实现
双链表头删相当于删除第一个数据?
//双链表的头删
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next != NULL);
ListNode* first = phead->next;
ListNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
}2.10双链表尾删操作代码实现
双链表尾删相当于删除最后一个数据
//双链表的尾删
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(phead->next != NULL);
ListNode* tail = phead->prev;
ListNode* tailPrev = tail->prev;
phead->prev = tailPrev;
tailPrev->next = phead;
free(tail);
}
?2.11双链表的位置pos（已知）删除操作代码实现
//双链表的位置pos（已知）删除
void ListErase( ListNode* pos)
{
assert(pos);
ListNode* posPrev = pos->prev;
ListNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
}?2.12双链表的元素查找，若找到目的值i则返回其地址pos，否则返回NULL
//双链表的元素查找，若找到目的值i则返回其地址pos，否则返回NULL
ListNode* ListFind(ListNode* phead, ListType i)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead) {
if (cur->data == i)
return cur;
cur = cur->next;
}
return NULL;
}2.13双链表的元素查找修改，若找到目的值i则将i修改成e，并返回其地址，否则返回NULL
//双链表的元素查找修改，若找到目的值i则将i修改成e，并返回其地址，否则返回NULL
ListNode* ListReplace(ListNode* phead, ListType i, ListType e)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead) {
if (cur->data == i)
{
cur->data = e;
return cur;
}
cur = cur->next;
}
return NULL;
}终：代码合集
#include "List.h"
//双链表的初始化
ListNode* ListInit()
{
ListNode* phead = BuyListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
//双链表的打印
void ListPrint(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur!=phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
//双链表的头插
void ListPushFront(ListNode* phead, ListType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
ListNode* next = phead->next;
phead->next = newNode;
newNode->prev = phead;
next->prev = newNode;
newNode->next = next;
}
//双链表的头删
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next != NULL);
ListNode* first = phead->next;
ListNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
}
//双链表的尾插
void ListPushBack(ListNode* phead, ListType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
ListNode* tail = phead->prev;
phead->prev = newNode;
newNode->next = phead;
tail->next = newNode;
newNode->prev = tail;
}
//双链表的尾删
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(phead->next != NULL);
ListNode* tail = phead->prev;
ListNode* tailPrev = tail->prev;
phead->prev = tailPrev;
tailPrev->next = phead;
free(tail);
}
//双链表结点的扩容
ListNode* BuyListNode(ListType x)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (newNode == NULL) {
printf("申请内存失败！");
return NULL;
}
newNode->next = NULL;
newNode->prev = NULL;
newNode->data = x;
return newNode;
}
//双链表的位置pos（已知）前插入
void ListInsert(ListNode* pos, ListType x)
{
assert(pos);
ListNode* newNode= BuyListNode(x);
ListNode* posPrev = pos->prev;
pos->prev = newNode;
newNode->next = pos;
posPrev->next = newNode;
newNode->prev = posPrev;
}
//双链表的位置pos（已知）删除
void ListErase( ListNode* pos)
{
assert(pos);
ListNode* posPrev = pos->prev;
ListNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
}
//双链表的元素查找，若找到目的值i则返回其地址pos，否则返回NULL
ListNode* ListFind(ListNode* phead, ListType i)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead) {
if (cur->data == i)
return cur;
cur = cur->next;
}
return NULL;
}
//双链表的元素查找修改，若找到目的值i则将i修改成e，并返回其地址，否则返回NULL
ListNode* ListReplace(ListNode* phead, ListType i, ListType e)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead) {
if (cur->data == i)
{
cur->data = e;
return cur;
}
cur = cur->next;
}
return NULL;
}