数据结构——双链表(C语言)

这篇具有很好参考价值的文章主要介绍了数据结构——双链表(C语言)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

​编辑

 双链表的初始化:

 双链表的打印:

双链表的尾插:

双链表的头插: 

双链表的尾删:

 文章来源地址https://www.toymoban.com/news/detail-646295.html

双链表的头删:

双链表pos位置之前的插入:

双链表pos位置的删除:

关于顺序表和链表的区别:


 

  1. 上篇文章给大家讲解了无头单向循环链表,它的特点:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构子结构,如哈希桶、图的邻接表等等。但是呢,单链表在笔试中还是很常见的。
  2. 今天我给大家讲解一下带头双向链表,它的特点:结构复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然复杂,但是使用代码实现以后会发现结构会带来很多优势。

数据结构——双链表(C语言),数据结构,网络,数据结构,链表,经验分享,c++

如图,这就是今天我为大家讲解的双链表结构了。下面跟随我的思路走下去,希望让你对链表有新的理解。

 


 双链表的初始化:

  • 今天我给大家带来另一种方式改变链表的结构,如果想了解双指针来改变链表的结构,可以参考参考我的上一篇单链表的博客。
  • 思路:我创建了一个节点,然后把节点赋给了phead,再让它的上一个位置和下一个位置分别指向它自己,最后返回phead就是我们要的哨兵位的头节点了。
ListNode* ListCreate(ListDateType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}
ListNode* ListInit()
{
	ListNode* phead = ListCreate(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

 


 双链表的打印:

  • 因为要让终端出现下面的样子,我就用到了打印的函数。
  • 首先,还是老套路,我先断言了一下,防止传的参数有问题。
  • 因为这里的phead是一个哨兵位,存放着无效的数据,所以,我就定义了一个cur的节点,用循环打印链表中的所有值,并标明他们的方向。

数据结构——双链表(C语言),数据结构,网络,数据结构,链表,经验分享,c++

void ListPrint(ListNode* phead)
{
	assert(phead);

	printf("phead<->");
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<->", cur->val);
		cur = cur->next;
	}
	printf("\n");
}

 


双链表的尾插:

  • 在双链表尾插的时候,它的优势就体现出来了,如果是单链表,要尾插的话,是只有遍历找尾节点的,但是呢,如果是双向链表,phead的前一个节点就是尾节点,它就不用找尾,也不需要遍历了。这也是双链表的优势之一。
  • 尾插思路:先断言一下,然后用tail保存尾节点,创建一个新节点,然后改变尾节点和头节点链接关系,让newnode为新的尾节点。

数据结构——双链表(C语言),数据结构,网络,数据结构,链表,经验分享,c++

 

void ListPushBack(ListNode* phead,ListDateType x)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newnode = ListCreate(x);

	tail->next = newnode;
	newnode->prev = tail;

	newnode->next = phead;
	phead->prev = newnode;


}

 


双链表的头插: 

  • 思路:头插的话,就是先保存一下头节点的位置,然后创建一个新节点,然后改变他们的链接关系就可以了。因为我是先保存了它们的位置,所以谁先链接先都可以,如果没有保存的话,要向好逻辑,不要出现找不到头节点的位置了。
void ListPushFront(ListNode* phead, ListDateType x)
{
	assert(phead);
	ListNode* newnode = ListCreate(x);
	ListNode* first = phead->next;

	phead->next = newnode;
	newnode->prev = phead;

	newnode->next = first;
	first->prev = newnode;
	
}

 


双链表的尾删:

  • 思路:尾删的话,就要记录一下尾节点的前一个节点了,然后去改变一下phead和尾节点前一个节点的链接关系。
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	ListNode* tail = phead->prev;
	ListNode* tailprev = phead->prev->prev;
	tailprev->next = phead;
	phead->prev = tailprev;

	free(tail);

}

 


双链表的头删:

  • 思路:头删的思路,其实和尾删的思路差不多,只不过这里保存的是phead之后的第二个节点了。然后就是改变链接关系。
void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead != phead->next);

	ListNode* first = phead->next;
	ListNode* second = first->next;

	phead->next = second;
	second->prev = phead;

	free(first);

}

双链表pos位置之前的插入:

  • 思路:如果是插入的话,是不是和尾插和头插差不多呢,我在这里是保存的pos之前的节点,然后创建一个新的节点,让pos之前的节点指向新节点,让新节点和pos再建立连接关系。
void ListInsert(ListNode* pos, ListDateType x)
{
	assert(pos);

	ListNode* posprev = pos->prev;
	ListNode* newnode = ListCreate(x);

	posprev->next = newnode;
	newnode->prev = posprev;

	newnode->next = pos;
	pos->prev = newnode;
}

 


双链表pos位置的删除:

  • 思路:pos位置要删除的话,保存pos上一个节点和pos下一个节点,然后free掉pos位置,再改变他们的链接关系。
  1. void ListErase(ListNode* pos)
    {
    	assert(pos);
    	ListNode* posprev = pos->prev;
    	ListNode* posnext = pos->next;
    
    	posprev->next = posnext;
    	posnext->prev = posprev;
    	
    	free(pos);
    }

大家看了pos位置的删除和pos之前的插入,是不是感觉和前面的尾插尾删和头插头删差不多呢,其实呢,最后的两个函数是可以进行对函数的复用的。

  •  尾插:其实就是在ListInsert函数传phead就可以了,这样就实现了尾插。
	ListInsert(phead, x);
  • 头插:头插是改变phead之后的位置,所以直接传phead->next就可以了。
	ListInsert(phead->next, x);
  • 头删和尾删:因为我写的删除的函数是删除pos位置,所以传要删除的位置就可以了。
	ListErase(phead->prev);
	ListErase(phead->next);

 

 


关于顺序表和链表的区别:

  •  存储空间上:顺序表在物理上是连续的,而链表逻辑上是连续的,而物理上是不一定连续的。
  • 随机访问上:顺序表是支持随机访问的,而链表是不支持的,向要访问链表中的节点,是需要遍历的。
  • 任意位置的插入和删除:在这里链表就有很大的优势了,链表只需要改变指向就可以实现对任意位置的插入和删除。但是对于顺序表,它可能需要搬运元素,效率太低了。
  • 插入:顺序表因为是连续的,所以在插入的上面,可能会有malloc扩容,但是呢malloc是有消耗的,如果一次扩二倍,但是用的不多,就会造成对空间的浪费,如果一次扩的空间是+1,可能局面临着多次扩容,而malloc的消耗并不低,所以这是不可取的。而链表并没有容器的概念,在这方面有优势。
  • 缓存利用率:顺序表的缓存命中率高,而链表低。

#define  _CRT_SECURE_NO_WARNINGS 1
#include "DoubleList.h"

ListNode* ListCreate(ListDateType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

ListNode* ListInit()
{
	ListNode* phead = ListCreate(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

void ListPrint(ListNode* phead)
{
	assert(phead);

	printf("phead<->");
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<->", cur->val);
		cur = cur->next;
	}
	printf("\n");
}

void ListPushBack(ListNode* phead,ListDateType x)
{
	assert(phead);
	//ListNode* tail = phead->prev;
	//ListNode* newnode = ListCreate(x);

	//tail->next = newnode;
	//newnode->prev = tail;

	//newnode->next = phead;
	//phead->prev = newnode;

	ListInsert(phead, x);

}

void ListPushFront(ListNode* phead, ListDateType x)
{
	assert(phead);
	//ListNode* newnode = ListCreate(x);
	//ListNode* first = phead->next;

	//phead->next = newnode;
	//newnode->prev = phead;

	//newnode->next = first;
	//first->prev = newnode;
	
	ListInsert(phead->next, x);
}

void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	//ListNode* tail = phead->prev;
	//ListNode* tailprev = phead->prev->prev;
	//tailprev->next = phead;
	//phead->prev = tailprev;

	//free(tail);
	
	ListErase(phead->prev);
}

void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead != phead->next);

	//ListNode* first = phead->next;
	//ListNode* second = first->next;

	//phead->next = second;
	//second->prev = phead;

	//free(first);

	ListErase(phead->next);
}

int ListSize(ListNode* phead)
{
	assert(phead);

	int size = 0;
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		++size;
		cur = cur->next;
	}

	return size;
}

void ListInsert(ListNode* pos, ListDateType x)
{
	assert(pos);

	ListNode* posprev = pos->prev;
	ListNode* newnode = ListCreate(x);

	posprev->next = newnode;
	newnode->prev = posprev;

	newnode->next = pos;
	pos->prev = newnode;
}

void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* posprev = pos->prev;
	ListNode* posnext = pos->next;

	posprev->next = posnext;
	posnext->prev = posprev;
	
	free(pos);
}

 


 

什么是缓存利用率:

关于“Cache Line” ,缓存是把数据加载到离自己进的位置,对于CPU来说,CPU是一块一块存储的。而这就叫“Chche Line”。

我们所写的程序,其实都是会形成不同的指令,然后让CPU执行,但是呢,CPU执行速度快,内存跟不上,所以CPU一般都是把数据放到缓存中,对于小的字节来说,直接由寄存器来读取,大的字节会用到三级缓存。

简而言之,数据先被读取,然后运算,最后放到主存中,如果没有命令,就继续。

而顺序表呢,它的物理结构是连续的,它可能一开始没有命中,但是一旦缓存命中了,它可能就会被连续命中,所以这也是顺序表缓存利用率高的原因,而链表也是因为他的物理结构,导致缓存利用率低。

 

数据结构——双链表(C语言),数据结构,网络,数据结构,链表,经验分享,c++

下面是双链表的源码:

#define  _CRT_SECURE_NO_WARNINGS 1
#include "DoubleList.h"

ListNode* ListCreate(ListDateType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

ListNode* ListInit()
{
	ListNode* phead = ListCreate(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

void ListPrint(ListNode* phead)
{
	assert(phead);

	printf("phead<->");
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<->", cur->val);
		cur = cur->next;
	}
	printf("\n");
}

void ListPushBack(ListNode* phead,ListDateType x)
{
	assert(phead);
	//ListNode* tail = phead->prev;
	//ListNode* newnode = ListCreate(x);

	//tail->next = newnode;
	//newnode->prev = tail;

	//newnode->next = phead;
	//phead->prev = newnode;

	ListInsert(phead, x);

}

void ListPushFront(ListNode* phead, ListDateType x)
{
	assert(phead);
	//ListNode* newnode = ListCreate(x);
	//ListNode* first = phead->next;

	//phead->next = newnode;
	//newnode->prev = phead;

	//newnode->next = first;
	//first->prev = newnode;
	
	ListInsert(phead->next, x);
}

void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	//ListNode* tail = phead->prev;
	//ListNode* tailprev = phead->prev->prev;
	//tailprev->next = phead;
	//phead->prev = tailprev;

	//free(tail);
	
	ListErase(phead->prev);
}

void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead != phead->next);

	//ListNode* first = phead->next;
	//ListNode* second = first->next;

	//phead->next = second;
	//second->prev = phead;

	//free(first);

	ListErase(phead->next);
}

int ListSize(ListNode* phead)
{
	assert(phead);

	int size = 0;
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		++size;
		cur = cur->next;
	}

	return size;
}

void ListInsert(ListNode* pos, ListDateType x)
{
	assert(pos);

	ListNode* posprev = pos->prev;
	ListNode* newnode = ListCreate(x);

	posprev->next = newnode;
	newnode->prev = posprev;

	newnode->next = pos;
	pos->prev = newnode;
}

void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* posprev = pos->prev;
	ListNode* posnext = pos->next;

	posprev->next = posnext;
	posnext->prev = posprev;
	
	free(pos);
}
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int ListDateType;

typedef struct ListNode
{
	ListDateType val;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

ListNode* ListCreate(ListDateType x);
void ListPrint(ListNode* phead);
ListNode* ListInit();
void ListPushBack(ListNode* phead,ListDateType x);
void ListPushFront(ListNode* phead, ListDateType x);
void ListPopBack(ListNode* phead);
void ListPopFront(ListNode* phead);
int ListSize(ListNode* phead);
void ListInsert(ListNode* pos, ListDateType x);
void ListErase(ListNode* pos);

 

 

 

 

 

 

 

 

 

 

 

 

到了这里,关于数据结构——双链表(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——双链表(C语言)

    目录 ​编辑  双链表的初始化:  双链表的打印: 双链表的尾插: 双链表的头插:  双链表的尾删:   双链表的头删: 双链表pos位置之前的插入: 双链表pos位置的删除: 关于顺序表和链表的区别:   上篇文章给大家讲解了无头单向循环链表,它的特点:结构简单,一般

    2024年02月13日
    浏览(61)
  • 【玩转408数据结构】线性表——双链表、循环链表和静态链表(线性表的链式表示 下)

            在前面的学习中,我们已经了解到了链表(线性表的链式存储)的一些基本特点,并且深入的研究探讨了单链表的一些特性,我们知道,单链表在实现插入删除上,是要比顺序表方便的,但是,单链表中每个结点仅存在一个指针指向其后续结点,那么如果我们想要找

    2024年04月10日
    浏览(61)
  • 【C语言】数据结构——带头双链表实例探究

    💗个人主页💗 ⭐个人专栏——数据结构学习⭐ 💫点击关注🤩一起学习C语言💯💫 我们在前面学习了单链表和顺序表。 今天我们来学习双向循环链表。 在经过前面的一系列学习,我们已经掌握很多知识,相信今天的内容也是很容易理解的。 关注博主或是订阅专栏,掌握第

    2024年02月03日
    浏览(45)
  • 【数据结构】C语言实现双链表的基本操作

    大家好,很高兴又和大家见面啦!!! 经过前面几个篇章的内容分享,相信大家对顺序表和单链表的基本操作都已经熟练掌握了。今天咱们将继续分享线性表的链式存储的第二种形式——双链表。在今天的内容中,咱们将介绍双链表的创建以及一些基本操作,接下来跟我一起

    2024年02月04日
    浏览(63)
  • 【数据结构】 循环双链表的基本操作 (C语言版)

    目录 一、循环双链表 1、循环双链表的定义: 2、循环双链表的优缺点: 二、循环双链表的基本操作算法(C语言)    1、宏定义  2、创建结构体 3、循环双链表的初始化  4、循环双链表按位查找 5、循环双链表插入 6、循环双链表查找 7、循环双链表删除 8、求循环双链表长

    2024年01月22日
    浏览(59)
  • C语言数据结构--链表

    顺序表的问题及思考 问题: 1. 中间/头部的插入删除,时间复杂度为O(N) 2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有

    2024年02月05日
    浏览(44)
  • C语言数据结构——链表

    目录 前言 一、什么是链表 1.1链表的结构和概念 1.2 链表的分类 二、无头单向非循环链表 2.1 创建结构体 2.2 动态申请一个节点 2.3 单链表打印 2.4 单链表尾插/尾删 2.4.1 单链表尾插  2.4.2 单链表尾删 2.5 单链表头插/头删 2.5.1 头插 2.5.2 头删 2.6 单链表查找 2.7 单链表中间插入/中

    2024年02月16日
    浏览(55)
  • 数据结构:链表(Python语言实现)

    链表分为单链表、双链表、循环单链表和循环双链表。 本文以单链表为例,用python创建一个单链表数据结构,同时定义链表节点的增加、删除、查询和打印操作。 创建一个名为Node的节点类,节点类里面包含2个属性和1个方法。 分别为data数据域属性和next指针域属性。 has_va

    2024年02月16日
    浏览(54)
  • 数据结构链表(C语言实现)

            机遇对于有准备的头脑有特别的亲和力。本章将讲写到链表其中主要将写到单链表和带头双向循环链表的如何实现。    话不多说安全带系好,发车啦 (建议电脑观看) 。 附:红色,部分为重点部分;蓝颜色为需要记忆的部分(不是死记硬背哈,多敲);黑色加粗

    2024年02月10日
    浏览(40)
  • C语言实现链表--数据结构

    魔王的介绍:😶‍🌫️一名双非本科大一小白。 魔王的目标:🤯努力赶上周围卷王的脚步。 魔王的主页:🔥🔥🔥大魔王.🔥🔥🔥 ❤️‍🔥大魔王与你分享:很喜欢宫崎骏说的一句话:“不要轻易去依赖一个人,它会成为你的习惯当分别来临,你失去的不是某个人而是你精

    2024年02月02日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包