开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 最最容易实现的链表结构——双向链表（数据结构C语言实现4） -> 正文阅读

[数据结构与算法]最最容易实现的链表结构——双向链表（数据结构C语言实现4）

写在前面

之前在这篇博客手把手教你实现链表—单链表（数据结构C语言实现3）我们已经学习过了链表的相关知识，以及单链表的实现！如果忘记了的话，可以点开链接复习一下！我们今天重点带大家学习双向链表的实现！

双链表结构

单链表

之前我们已经知道单向链表的结构：
逻辑结构
在这里插入图片描述

//类型创建
  typedef int SLDataType;
  typedef struct SListNode
  {
      SLDataType data;   //存值
      struct SListNode* next; //存下一节点的指针
  }SLNode;

结构体存放了一个date数据和一个next结构体指针指向下一个节点！
我们再来看一下物理结构
在这里插入图片描述
这便是单链表，结构简单，但我们实现起来却比较复杂的一种链表结构，我们今天来看一下双向链表！

双向链表

所谓双向链表顾名思义就是，节点方向是双向的，不像单链那样，只能从头节点出发到尾结点!

typedef int LDataType;
typedef struct ListNode
{
 struct ListNode*prev;
 LDataType data;
 struct ListNode*next;
}LisNode;

在这里插入图片描述
从上面的逻辑结构我们可以看出这个双向循环链表是带哨兵位，就是带头，并且第一个节点与最后一个节点相连说明是循环的！所以上面的结构是带头双向循环链表我们今天要实现的链表也是这种最特殊的链表！
链表的分类：
在这里插入图片描述

3	3
带头	不带头
循环	不循环
单向	双向

每一个链表结构都有很多种组合：
eg:带头不循环单向 …
是否带头，是否循环，是否双向
2x2x2所以一共有八中组合，我们来学习最复杂的结构!
带头双向循环链表

双向链表的实现

在这里插入图片描述我们先来创建一个双向链表的结构体节点

//节点类型创建
typedef int LDataType;
typedef struct ListNode
{
	struct ListNode* prev;
	LDataType data;
	struct ListNode* next;
}ListNode;

接口实现

创建新的节点

//创建新的节点
ListNode* ListBuyNewNode(LDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode)
	{
		newnode->data = x;
		newnode->next = NULL;
		newnode->prev = NULL;
		return newnode;
	}
	else
	{
		printf("malloc fail!\n");
		return NULL;
	}
	
}

链表初始化返回头节点

//初始化链表返回头结点
ListNode* ListInit()
{
	ListNode* head=ListBuyNewNode(0);
	head->next = head;
	head->prev = head;
	return head;
}

链表不用了销毁

//回收
void ListDestroy(ListNode* head)
{
	head->next=head->prev = NULL;
}

打印

//打印
void ListPrint(ListNode* head)
{
	assert(head);
	ListNode* cur = head->next;
	while (cur!=head)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

头插
和单向不带头链表不一样，因为链表带了头节点就只需要传一级指针就可以进行头插！因为头节点是不会改变的

//头插
void ListFrontPush(ListNode* head, LDataType x)
{
	ListNode* newnode = ListBuyNewNode(x);
	newnode->next = head->next;
	newnode->prev = head;
	head->next->prev= newnode;
	head->next = newnode;
}

在这里插入图片描述
**注：**如果我们直接像上面一样不创建其他变量，直接插入节点，我们需要先连接new的指针，再改变head和head->next的指针，先连后改如果我们现将head->next改变指向了new我们就无法找到head->next节点了！其他接口也是如此！
头插接口测试

在这里插入图片描述
头删

//头删
void ListFrontPop(ListNode* head)
{
	ListNode* ret = head->next;
	head->next = ret->next;
	ret->next->prev = head;
	free(ret);
	ret = NULL;

}

头删接口测试
在这里插入图片描述

ListNode* head = ListInit();
	ListFrontPush(head, 1);
	ListFrontPush(head, 2);
	ListFrontPush(head, 3);
	ListFrontPush(head, 4);
	ListPrint(head);
	ListFrontPop(head);
	ListFrontPop(head);
	ListPrint(head);

在这里插入图片描述
尾插

//尾插
void ListBackPush(ListNode* head, LDataType x)
{
	ListNode* new = ListBuyNewNode(x);
	new->next = head;
	new->prev = head->prev;
	head->prev->next= new;
	head->prev = new;
}

尾插接口测试

ListNode* head = ListInit();
	ListFrontPush(head, 1);
	ListFrontPush(head, 2);
	ListFrontPush(head, 3);
	ListFrontPush(head, 4);
	ListPrint(head);
	ListBackPush(head, 1);
	ListBackPush(head, 2);
	ListBackPush(head, 3);
	ListBackPush(head, 4);
	ListBackPush(head, 5);
	ListPrint(head);

在这里插入图片描述
尾删

//尾删
void ListBackPop(ListNode* head)
{
	ListNode* tail = head->prev;
	head->prev = tail->prev;
	tail->prev->next = head;
	free(tail);
	tail = NULL;
}

尾删接口测试

ListNode* head = ListInit();
	ListFrontPush(head, 1);
	ListFrontPush(head, 2);
	ListFrontPush(head, 3);
	ListFrontPush(head, 4);
	ListPrint(head);
	ListBackPush(head, 1);
	ListBackPush(head, 2);
	ListBackPush(head, 3);
	ListBackPush(head, 4);
	ListBackPush(head, 5);
	ListPrint(head);
	ListBackPop(head);
	ListBackPop(head);
	ListBackPop(head);
	ListPrint(head);

在这里插入图片描述
查找

//查找x节点并返回
ListNode* ListFind(ListNode* head, LDataType x)
{
	ListNode* ret = head->next;
	while (ret!= head)
	{
		if (ret->data == x)
		{
			return ret;
		}
		ret = ret->next;
	}
	return NULL;

}

pos节点修改

//在pos前插入
void ListInsert(ListNode* head, ListNode* pos,LDataType x)
{
	ListNode* new = ListBuyNewNode(x);
	new->next = pos;
	new->prev = pos->prev;
	pos->prev->next = new;
	pos->prev = new;
}

pos节点删除

//pos节点删除
void ListErase(ListNode* head, ListNode* pos)
{
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

接口测试

void test1()
{
	ListNode* head = ListInit();
	ListFrontPush(head, 1);
	ListFrontPush(head, 2);
	ListFrontPush(head, 3);
	ListFrontPush(head, 4);
	ListPrint(head);
	ListNode* pos = ListFind(head, 3);
	if (pos)
	{
		ListInsert(head, pos, 33);
		ListPrint(head);
		ListErase(head, pos);
		ListPrint(head);
	}
}

在这里插入图片描述

源码

List.h头文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>


//节点类型创建
typedef int LDataType;
typedef struct ListNode
{
	struct ListNode* prev;
	LDataType data;
	struct ListNode* next;
}ListNode;
//创建新的节点
ListNode*ListBuyNewNode(LDataType x);
//初始化链表返回头结点
ListNode* ListInit();
//回收
void ListDestroy(ListNode*head);
//打印
void ListPrint(ListNode* head);
//头插
void ListFrontPush(ListNode* head,LDataType x);
//头删
void ListFrontPop(ListNode* head);
//尾插
void ListBackPush(ListNode* head,LDataType x);
//尾删
void ListBackPop(ListNode* head);

//查找
ListNode* ListFind(ListNode* head, LDataType x);
//pos节点删除
void ListErase(ListNode* head, ListNode* pos);
//在pos前插入
void ListInsert(ListNode* head, ListNode* pos , LDataType x);

List.c所有接口源码

//创建新的节点
ListNode* ListBuyNewNode(LDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode)
	{
		newnode->data = x;
		newnode->next = NULL;
		newnode->prev = NULL;
		return newnode;
	}
	else
	{
		printf("malloc fail!");
		return NULL;
	}
	
}
//初始化链表返回头结点
ListNode* ListInit()
{
	ListNode* head=ListBuyNewNode(0);
	head->next = head;
	head->prev = head;
	return head;
}
//回收
void ListDestroy(ListNode* head)
{
	head->next=head->prev = NULL;
}
//打印
void ListPrint(ListNode* head)
{
	assert(head);
	ListNode* cur = head->next;
	while (cur!=head)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
//头插
void ListFrontPush(ListNode* head, LDataType x)
{
	ListNode* newnode = ListBuyNewNode(x);
	newnode->next = head->next;
	newnode->prev = head;
	head->next->prev= newnode;
	head->next = newnode;
	
}
//头删
void ListFrontPop(ListNode* head)
{
	ListNode* ret = head->next;
	head->next = ret->next;
	ret->next->prev = head;
	free(ret);
	ret = NULL;

}
//尾插
void ListBackPush(ListNode* head, LDataType x)
{
	ListNode* new = ListBuyNewNode(x);
	new->next = head;
	new->prev = head->prev;
	head->prev->next= new;
	head->prev = new;
}
//尾删
void ListBackPop(ListNode* head)
{
	ListNode* tail = head->prev;
	head->prev = tail->prev;
	tail->prev->next = head;
	free(tail);
	tail = NULL;
}
//查找
ListNode* ListFind(ListNode* head, LDataType x)
{
	ListNode* ret = head->next;
	while (ret!= head)
	{
		if (ret->data == x)
		{
			return ret;
		}
		ret = ret->next;
	}
	return NULL;

}
//pos节点删除
void ListErase(ListNode* head, ListNode* pos)
{
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}
//在pos前插入
void ListInsert(ListNode* head, ListNode* pos,LDataType x)
{
	ListNode* new = ListBuyNewNode(x);
	new->next = pos;
	new->prev = pos->prev;
	pos->prev->next = new;
	pos->prev = new;
}