双向链表（详解）_双向链表 csdn

在单链表专题中我们提到链表的分类，其中提到了带头双向循环链表，今天小编将详细讲下双向链表。

话不多说，直接上货。

1.双向链表的结构

带头双向循环链表

注意

2.双向链表的实现

1.头文件的建立（函数库引入，所需函数的导入） 

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//#include <stdbool.h>
typedef int Datatype;
//链表节点创建
typedef struct  ListNode {
	Datatype data;
	struct ListNode* next;
	struct ListNode* prev;
}Node;
//相关函数实现
// 链表初始化，双向链表头节点不能为空
//void LTInit(Node** pphead);
Node* LTInit();
//链表销毁
void LTDestroy(Node* phead);
//链表打印
void LTPrint(Node* phead);
//bool LTEmpty(Node* phead);
//尾插和头插
void LTPushBack(Node* phead, Datatype x);
void LTPushFront(Node* phead, Datatype x);
//尾删和头删
void LTPopBack(Node* phead);
void LTPopFront(Node* phead);
//在pos位置之后插⼊数据
void LTInsert(Node* pos, Datatype x);
//删除指定节点
void LTErase(Node* pos);
//节点找寻，方便指定插入和删除
Node* LTFind(Node* phead, Datatype x);

2.相关函数的实现

2.1 新节点建立

Node* Buynode(Datatype x) {
	Node* node = (Node*)malloc(sizeof(Node));
	if (node == NULL) {
		perror("malloc error");
		exit(1);
	}
	node->data = x;
 
	node->next = node->prev=node;
	return node;
}

这里为什么节点前后没有指向空指针，因为在后续中链表初始化时，若指向都是空指针，则创建的链表不是双向链表。

在双向链表中，每个节点都有两个指针，一个指向前一个节点（prev），一个指向后一个节点（next）。这样可以实现双向遍历和操作。 当初始化一个双向链表时，需要创建一个头节点（head node），这个头节点不存储实际的数据，只用于标识链表的起始位置。头节点的prev指针和next指针都应该指向自己，这样可以在链表中任意位置插入和删除节点而不需要特殊处理边界情况。

如果初始化时将prev和next指针都指向空，那么在插入和删除节点时就需要特殊处理头节点和尾节点的情况，增加了代码的复杂性。因此，在初始化时将prev和next指针都指向自己是一种简化设计，方便后续操作的方式。

总结来说，prev和next指针不能指向空，是为了简化双向链表的设计和操作。

2.2 链表初始化

Node* LTInit() {
	Node* pphead = Buynode(-1);
	if (pphead == NULL) {
		printf("初始化失败!");
	}
	return pphead;
}

2.3 链表的打印

//链表打印
void LTPrint(Node* phead) {
	Node* pcur = (Node*)malloc(sizeof(Node));
	pcur = phead->next;
	while (pcur!= phead) {
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

2.4 尾插和头插

/尾插和头插
void LTPushBack(Node* phead, Datatype x) {
	assert(phead);
	//Node* ptail = (Node*)malloc(sizeof(Node));
	Node* newnode = Buynode(x);
	newnode->prev = phead->prev;//新节点指向原来的尾节点
	newnode->next = phead;
	phead->prev->next = newnode; //让原本的尾节点指向新的节点
	phead->prev = newnode;
}
void LTPushFront(Node* phead, Datatype x) {
	assert(phead);
	Node* newnode = Buynode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
 
	phead->next->prev= newnode;//两行不能完全交换，若交换
	phead->next = newnode;//phead->next=newnode;newnode->prev=newnode;
 
}

2.5 尾删和头删

//尾删和头删
void LTPopBack(Node* phead) {
	//链表必须有效且链表不能为空(只有一个哨兵位)
	assert(phead && phead->next!=phead);
	Node* del = phead->prev;
	Node* ptail = del->prev;
	ptail->next = phead;
	phead->prev = ptail;
	free(del);
	del = NULL;
}
 
void LTPopFront(Node* phead) {
	assert(phead && phead->next != phead);
	Node* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	free(del);
	del = NULL;
}

2.6 节点的找寻

方便在指定的节点前后进行相关操作

Node* LTFind(Node* phead, Datatype x) {
	Node* find = phead->next;
	while (find!=phead) {
		if (find->data == x)
			return find;
		else
		find = find->next;
	}
	return NULL;
}

2.7 指定节点处的操作

//在pos位置之后插⼊数据
void LTInsert(Node* pos, Datatype x) {
	assert(pos);
	Node* newnode = Buynode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}
 
//删除指定节点
void LTErase(Node* pos) {
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}

2.8 链表的销毁

void LTDestroy(Node* phead) {
	assert(phead);
	Node* pcur = phead->next;
	while (pcur->next != phead) {
		Node* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}

在实现相关函数时，都是从前后节点入手，改变next和prev的指向。

3. 链表的测试

#define _CRT_SECURE_NO_WARNINGS
#include "List.h"
void test1() {
	Node*plist=LTInit();
	//printf("%d", phead->data);
	//头插
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPrint(plist);
	//尾插
	LTPushBack(plist, 5);
	LTPushBack(plist, 3);
	//LTPrint(plist);
	
	//尾删
	//LTPopBack(plist, 3);
	//LTPopBack(plist, 5);
	//LTPrint(plist);
	//头删
	//LTPopFront(plist, 1);
	//LTPopFront(plist, 2);
	//LTPrint(plist);
	//节点查找
	Node* find = LTFind(plist, 5);
	if (find == NULL)
		printf("Not Found\n");
	else
		printf("找到了\n");
   //指定插入
	LTInsert(find, 66);
	LTPrint(plist);
   //指定节点删除
	LTErase(find);
	LTPrint(plist);
   //链表销毁
	LTDestroy(plist);
	plist = NULL;
}
int main() {
	test1();
	return 0;
}

3.顺序表和链表的优缺点对比（了解）

看完给小编留下点赞，关注加三连吧！！！