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

举报
bug郭 发表于 2022/07/31 12:53:06 2022/07/31
【摘要】 写在前面之前在这篇博客手把手教你实现链表—单链表（数据结构C语言实现3）我们已经学习过了链表的相关知识，以及单链表的实现！如果忘记了的话，可以点开链接复习一下！我们今天重点带大家学习双向链表的实现！@TOC 双链表结构 单链表之前我们已经知道单向链表的结构：逻辑结构//类型创建 typedef int SLDataType; typedef struct SListNode { ...

写在前面

之前在这篇博客手把手教你实现链表—单链表（数据结构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;

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

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;
}
博主水平有限，如有问题还望指正，谢谢~~
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
C语言 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入