bug郭

2022-10-12 08:37 赣南师范大学测试工程师发布于江西

关注

数据结构链表结构——双向链表（C语言实现）

大家好,我是bug郭,一名双非科班的在校大学生。对C/JAVA、数据结构、Spring系列框架、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流

作者简介:

CSDN java领域新星创作者blog.csdn.net/bug..
掘金LV3用户 juejin.cn/user/bug..
阿里云社区专家博主,星级博主,developer.aliyun.com/bug..
华为云云享专家 bbs.huaweicloud.com/bug..

写在前面

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

双链表结构

单链表

之前我们已经知道单向链表的结构： 逻辑结构

//类型创建
  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;

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

带头	不带头
循环	不循环
单向	双向
每一个链表结构都有很多种组合：
`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;
}

<hr> 博主水平有限，如有问题还望指正，谢谢~~

#C语言#