用C语言实现双向链表

目录

一.双向链表的结构

二. 双向链表的实现

1. 在List.h中结构体的定义和各函数的声明 

1.1 结构体（节点）的定义 

1.2 各函数的声明

2. 在List.c中各函数的实现

2.1 初始化 LTInit

2.2 尾插 LTPushBack

2.3 打印 LTPrint

2.4 头插 LTPushFront

2.5 尾删 LTPopBack

2.6 头删 LTPopFront

2.7 在指定位置后插入数据 LTInsert

2.8 查找 LTFind

2.9 删除指定位置节点 LTErase

2.10 销毁 LTDestroy

三. 顺序表和双向链表的优缺点分析

四. 参考代码

 1. List.h

2. List.c

3. test.c

一.双向链表的结构

注意：这里的“带头”跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严谨，但是为了更好的理解就直接称为单链表的头节点。

带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”

“哨兵位”存在的意义：

遍历循环链表避免死循环。

二. 双向链表的实现

注：本次我们将实现一个双向带头循环链表。 

1. 在List.h中结构体的定义和各函数的声明 

1.1 结构体（节点）的定义 

//重命名数据类型
typedef int LTDataType;
 
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;//指向前一个节点
	struct ListNode* next;//指向后一个节点
}LTNode;

//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit(void);
 
//尾插 -- 不改变哨兵位 -- 传一级指针
void LTPushBack(LTNode* phead, LTDataType x);
 
//打印
void LTPrint(LTNode* phead);
 
//头插
void LTPushFront(LTNode* phead, LTDataType x);
 
//尾删
void LTPopBack(LTNode* phead);
 
//头删
void LTPopFront(LTNode* phead);
 
//在指定位置后插入数据
void LTInsert(LTNode* pos, LTDataType x);
 
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
 
//删除指定位置节点
void LTErase(LTNode* pos);
 
//销毁
void LTDestroy(LTNode* phead);

LTNode* LTBuyNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc failed");
		exit(1);
	}
	node->data = x;
	node->prev = node->next = node;
 
	return node;
}

LTNode* LTInit(void)
{
	LTNode* node = LTBuyNode(EOF);
	return node;
}

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

void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
 
	//phead newnode phead->next ......
	newnode->next = phead->next;
	newnode->prev = phead;
 
	phead->next->prev = newnode;
	phead->next = newnode;
}

void LTPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead);//链表有效且不为空（只有一个哨兵位）
 
	//phead  ......  del->prev(phead->prev->prev)  del(phead->prev)
	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
 
	//删除del节点
	free(del);
	del = NULL;
}

void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
 
	LTNode* del = phead->next;
 
	//phead  del(phead->next)  del->next(phead->next->next) ......
	phead->next = del->next;
	del->next->prev = phead;
 
	//删除del节点
	free(del);
	del = NULL;
}

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
 
	LTNode* newnode = LTBuyNode(x);
 
	//... pos newnode pos->next ...
	newnode->next = pos->next;
	newnode->prev = pos;
 
	pos->next->prev = newnode;
	pos->next = newnode;
}

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

void LTErase(LTNode* pos)
{
	//pos理论上不能为phead，但是参数有限，无法校验
	assert(pos);
 
	//... pos->prev pos pos->next ...
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
 
	free(pos);
	pos = NULL;
}

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

我们可以发现，由于双向链表具有指向前后节点的指针，代码量大大减少，但是也需要处理好指针之间的关系。

三. 顺序表和双向链表的优缺点分析

四. 参考代码

 1. List.h

#pragma once
 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
//重命名数据类型
typedef int LTDataType;
 
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;//指向前一个节点
	struct ListNode* next;//指向后一个节点
}LTNode;
 
//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit(void);
 
//尾插 -- 不改变哨兵位 -- 传一级指针
void LTPushBack(LTNode* phead, LTDataType x);
 
//打印
void LTPrint(LTNode* phead);
 
//头插
void LTPushFront(LTNode* phead, LTDataType x);
 
//尾删
void LTPopBack(LTNode* phead);
 
//头删
void LTPopFront(LTNode* phead);
 
//在指定位置后插入数据
void LTInsert(LTNode* pos, LTDataType x);
 
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
 
//删除指定位置节点
void LTErase(LTNode* pos);
 
//销毁
void LTDestroy(LTNode* phead);

2. List.c

#include "List.h"
 
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc failed");
		exit(1);
	}
	node->data = x;
	node->prev = node->next = node;
 
	return node;
}
 
//void LTInit(LTNode** pphead)
//{
//	//给双向链表创建一个哨兵位
//	*pphead = LTBuyNode(-1);
//}
LTNode* LTInit(void)
{
	LTNode* node = LTBuyNode(EOF);
	return node;
}
 
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
 
	//phead ..... phead->prev newnode
	newnode->prev = phead->prev;
	newnode->next = phead;
 
	phead->prev->next = newnode;
	phead->prev = newnode;
}
 
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
 
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
 
	//phead newnode phead->next ......
	newnode->next = phead->next;
	newnode->prev = phead;
 
	phead->next->prev = newnode;
	phead->next = newnode;
}
 
void LTPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead);//链表有效且不为空（只有一个哨兵位）
 
	//phead  ......  del->prev(phead->prev->prev)  del(phead->prev)
	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
 
	//删除del节点
	free(del);
	del = NULL;
}
 
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
 
	LTNode* del = phead->next;
 
	//phead  del(phead->next)  del->next(phead->next->next) ......
	phead->next = del->next;
	del->next->prev = phead;
 
	//删除del节点
	free(del);
	del = NULL;
}
 
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
 
void LTErase(LTNode* pos)
{
	//pos理论上不能为phead，但是参数有限，无法校验
	assert(pos);
 
	//... pos->prev pos pos->next ...
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
 
	free(pos);
	pos = NULL;
}
 
void LTDestroy(LTNode* phead)
{
	assert(phead);
 
	LTNode* pcur = phead->next;
	while(pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
 
	//销毁phead
	free(phead);
	phead = NULL;
	pcur = NULL;
}
 
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
 
	LTNode* newnode = LTBuyNode(x);
 
	//... pos newnode pos->next ...
	newnode->next = pos->next;
	newnode->prev = pos;
 
	pos->next->prev = newnode;
	pos->next = newnode;
}

3. test.c

#include "List.h"
 
void ListTest01()
{
	LTNode* plist = NULL;
	plist = LTInit();
 
	//LTPushBack(plist, 1);
	//LTPushBack(plist, 2);
	//LTPushBack(plist, 3);
	//LTPushBack(plist, 4);
	//LTPushBack(plist, 5);
	//LTPrint(plist);
 
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPushFront(plist, 5);
	LTPrint(plist);
 
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
 
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
 
	//LTNode* find = NULL;
	//find = LTFind(plist, 2);
	//if (find)
	//{
	//	printf("找到了！\n");
	//}
	//else
	//{
	//	printf("找不到！\n");
	//}
	//find = LTFind(plist, 7);
	//if (find)
	//{
	//	printf("找到了！\n");
	//}
	//else
	//{
	//	printf("找不到！\n");
	//}
 
	//LTNode* find = NULL;
	//find = LTFind(plist, 2);
	//if (find)
	//{
	//	printf("找到了！\n");
	//}
	//else
	//{
	//	printf("找不到！\n");
	//}
	//LTInsert(find, 6);
	//LTPrint(plist);
	//LTErase(find);
	//find = NULL;
	//LTPrint(plist);
 
	LTDestroy(plist);
	plist = NULL;
}
 
int main()
{
	ListTest01();
	return 0;
}