【数据结构】单链表 && 双链表(链式和数组实现)

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

       🔥🔥 欢迎来到小林的博客!!
      🛰️博客主页:✈️小林爱敲代码
      🛰️博客专栏:✈️ 数据结构与算法
      🛰️社区 :✈️ 进步学堂
      🛰️欢迎关注:👍点赞🙌收藏✍️留言

前言

今天给大家带来四个内容,一个是单链表非带头的实现,一个是双链表带头循环的实现。剩下的就是数组模拟单链表和双链表。

单链表

链表,在内存中并不是连续存储的。而链表通常会有next指针指向它的下一个节点。链表的最后一个节点一定指向空。

数组双链表,数据结构与算法,数据结构,链表

头插

头插我们需要让新节点指向头节点,然后更换头节点为新节点即可。

数组双链表,数据结构与算法,数据结构,链表

尾插

我们只需要找到最后一个节点,让它的next指向新节点,再把新节点指向NULL即可。

数组双链表,数据结构与算法,数据结构,链表

头删

先保存头节点的下一个节点,然后删除头节点。并把保存下来的下一个节点设置为新的头节点。

数组双链表,数据结构与算法,数据结构,链表

尾删

尾删需要记录一下最后一个节点的前一个节点。然后删除最后一个节点,把前一个节点指向NULL。否则会出现指向野指针的情况。

数组双链表,数据结构与算法,数据结构,链表

指定位置后插入

我们这里只讲解在指定位置的后一个元素插入,因为单链表在指定节点的前一个插入,需要前一个节点。但是单链表只指后不指前。所以想拿到前一个节点必须再遍历一次,所以不建议单链表用前插。在指定位置后插,我们只需要保存一下这个位置的下一个节点,然后让新节点指向这个位置的下一个节点。这个位置指向新节点。

假设我们在pos位置后面插入:

数组双链表,数据结构与算法,数据结构,链表

指定位置后删除

我们还是删除指定位置后的元素,因为如果删除指定元素,我们也需要它的前一个节点。单链表无法直接获取前一个节点。指定位置后删除,我们只需要保存下一个节点的下一个节点,然后删除下一个节点,然后让这个位置指向保存下来的的节点。

数组双链表,数据结构与算法,数据结构,链表

单链表的代码实现:

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

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;


// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode)); //开辟空间
	newNode->data = x; //空间值为x
	return newNode;
}
// 单链表打印
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur) //遍历一遍链表
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	if (*pplist == NULL)//如果链表为空调用头插
	{
		SListPushFront(pplist, x); 
		return;
	}
    //找到尾部节点
	SListNode* tail = *pplist;
	while (tail->next)
	{
		tail = tail->next;
	}
    //复用SListInsertAfter函数插入
	SListInsertAfter(tail, x);
}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newNode = BuySListNode(x);
	if (*pplist == NULL) //链表为空需要更新头节点
	{
		*pplist = newNode;
		newNode->next = NULL;
		return;
	}
	newNode->next = *pplist;
	*pplist = newNode;
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist && *pplist);
	if ((*pplist)->next == NULL) //链表就一个元素,调用头删
	{
		SListPopFront(pplist);
		return;
	}
	SListNode* tail = *pplist;
	SListNode* prev = NULL;
	
    //遍历链表并删除
	while (tail->next)
	{
		prev = tail;
		tail = tail->next;
	}
	free(tail);
	prev->next = NULL;
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist && *pplist);
    //头删
	SListNode* next = (*pplist)->next;
	free(*pplist);
	*pplist = next;
}
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (x == cur->data)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* next = pos->next;
	SListNode* newNode = BuySListNode(x);
	pos->next = newNode;
	newNode->next = next;
}
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	SListNode* nextnext = pos->next->next;
	free(pos->next);
	pos->next = nextnext;
}
// 单链表的销毁
void SListDestroy(SListNode* plist)
{
	SListNode* cur = plist;
	SListNode* next = plist->next;
	while (cur)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
}

双链表

这里我们实现一个带头循环的双链表,因为循环链表可以从头节点直接找到最后一个节点。带头是因为更好的确定链表的尾部,带头节点在这里就冲当了尾节点的作用。

数组双链表,数据结构与算法,数据结构,链表

指定位置前插入

双链表我们只需要写指定插入和指定删除,就可以复用这两个接口实现头插,头删,尾插,尾删了。指定位置前插入和单链表类似。先保存前一个节点坐标,然后让前一个节点和新节点连接,再把自己的prev指针指向新节点。

为了方便观看,我把首尾节点指向的线省略了,实际上指针是指向首尾的。我们在pos前插入一个节点。

数组双链表,数据结构与算法,数据结构,链表

动图演示可能线连接的不怎么好看,但最后都是这样的

数组双链表,数据结构与算法,数据结构,链表

指定位置删除

指定位置删除,我们只需要存下前一个节点和后一个节点。然后把两个节点连接起来,再释放当前节点即可。

数组双链表,数据结构与算法,数据结构,链表

双链表代码实现:

#include <assert.h>
#include<stdio.h>

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;

typedef struct _ListNode
{
	LTDataType _data;
	struct _ListNode* _next; //指向后一个节点
	struct _ListNode* _prev; //指向前一个节点
}ListNode;



//创建节点
ListNode* CreateListNode(LTDataType x)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	newNode->_data = x;
	return newNode;
}

// 创建链表,返回链表的头结点.
ListNode* ListCreate()
{
	ListNode* head = CreateListNode(0);
	head->_next = head; //自己指向自己
	head->_prev = head; //自己指向自己
	return head;
}

// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	ListNode* cur = pHead->_next;
	while (cur != pHead)
	{
		ListNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	free(pHead);
}
// 双向链表打印
void ListPrint(ListNode* pHead)
{
	ListNode* cur = pHead->_next;
	while(cur != pHead)
	{
		printf("%d->", cur->_data);
		cur = cur->_next;
	}
	printf("NULL\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	ListInsert(pHead, x); //复用指定插入
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	ListErase(pHead->_prev); //复用指定删除
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	ListInsert(pHead->_next, x); //复用指定插入
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	ListErase(pHead->_next); //复用指定删除
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	while (pHead)
	{
		if (pHead->_data == x)
			return pHead;
		pHead = pHead->_next;
	}
	return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	ListNode* prev = pos->_prev;
	ListNode* newNode = CreateListNode(x);
	prev->_next = newNode;
	newNode->_prev = prev;
	newNode->_next = pos;
	pos->_prev = newNode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->_prev;
	ListNode* next = pos->_next;
	free(pos);
	prev->_next = next;
	next->_prev = prev;
}

数组模拟单链表

数组模拟链表我们需要开一个数组来存链表的值,还要开一个数组连存储链表的指向,还需要一个变量来代表链表的编号。

e[] 数组用来存储链表的值 , ne[] 数组用来存储节点指向节点的下标,数组的下标代表节点。 head代表头节点,值-1则为空节点。 idx 是给链表的节点的一个编号,代表下标。

代码:

#include<iostream>
using namespace std;

const int N = 100010; //链表总大小
int e[N];//存储值
int ne[N];//存储下一个节点 
int head,idx;  

//链表初始化
void init()
{
    head = -1 ; //-1为空
    idx = 0; //当前节点的编号
}
void add_to_head(int x)  //头插
{
    e[idx] = x; //给新节点赋值
    ne[idx] = head; //指向head指向的节点
    head = idx++; //头节点指向新节点
}

//插入到k节点后面
void add(int k ,int x)
{
    e[idx] = x; //idx编号的元素的值赋值为x
    ne[idx] = ne[k]; //指向k节点的下一个节点
    ne[k] = idx++; //指向新插入节点
}

void remove(int k )
{
    ne[k] = ne[ne[k]]; //指向下一个节点的下一个节点
}

数组模拟双链表

单链表需要一个数组来存储指向的节点,那么双链表就需要两个数组来存储,一个指向前节点,一个指向后节点。

r[] 存储节点的后一个节点下标

l[] 存储节点的前一个节点下标

e[] 存储节点的值

hh 头的下标

tt 尾的下标

idx 节点的编号,对应数组下标,每一个新的编号被使用说明创建了一个节点

#include<iostream>
#include<string>
using namespace std;

const int N = 1e6 + 10;
int r[N],l[N],e[N];
int hh,tt,idx;

void init()
{
    hh = 0,tt = 1,idx = 2;//hh代表头,tt代表尾,idx是其他节点的编号
    r[hh] = tt; //头指向尾
    l[tt] = hh; //尾指向头
}

//指定位置的右边插入
void add_right(int k,int x)
{
    e[idx] = x; //idx编号的节点的值为x
    r[idx] = r[k],l[idx] = k; //idx右边指向k的右边,坐标指向k
    l[r[k]] = idx,r[k] = idx++; //k右节点的坐标指向idx,k的右边指向idx。idx编号+1
}
//删除
void remove(int k)
{
    r[l[k]] = r[k]; //k前一个节点的右一个节点指向k的右节点
    l[r[k]] = l[k]; //k后一个节点的左节点指向k的左节点
}

总结:

链式实现的链表的动态的,每次增加节点需要开辟空间。开辟空间是有消耗的。而数组模拟的链表是静态的,这就意味着数组模拟的链表比链式实现的链表更快。但因为是静态的,会占用固定的空间。所以个人推荐,做题的时候用静态链表,其他的时候用动态链表。文章来源地址https://www.toymoban.com/news/detail-790247.html

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

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

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

相关文章

  • 数据结构--线性表(顺序表、单链表、双链表、循环链表、静态链表)

    前言  学习所记录,如果能对你有帮助,那就泰裤辣。 目录 1.线性表概念 定义 基本操作 2.顺序表 定义 顺序表的实现--静态分配 动态分配 顺序表的特点 顺序表的插入和删除 顺序表的查找 按位查找  按值查找 3.单链表 定义 单链表的初始化 不带头节点的单链表 带头节点的单

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

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

    2024年04月10日
    浏览(61)
  • 【数据结构与算法】顺序表与链表(单链表和双链表)超详解图示与源码。

                                                       大家好,今天我们来学习数据结构中的顺序表与链表!源码在最后附上 首先我们先来认识一下 顺序表 :                                       **如上图所示:很多人会以为数组就是顺序表,顺序表就是数组,这

    2024年02月21日
    浏览(60)
  • 数据结构与算法—二叉树数组表示(ArrayBinTree)、二叉树的链式表示(LinkedBinTree)的基于C++模板代码实现

    1、二叉树的顺序表示:ArrayBinTree.h 二叉树的顺序表示法操作方便,但缺点是容易造成存储空间浪费。 这是一个用数组实现的二叉树类模板。它可以创建一个空树,也可以在指定的位置插入结点并设置结点的值,可以删除子树,并支持逐层遍历。使用该类时,需要提供一个元

    2024年02月06日
    浏览(44)
  • 【玩转408数据结构】线性表——单链表的定义以及增删改查(线性表的链式表示 上)

            到这里我们已经了解到线性表是具有 相同数据类型 的 有限个数据元素 序列,而线性表的顺序存储也就是顺序表,顺序表的存储形式十分直观,我们在实现时使用数组进行实现,但顺序表在插入或者删除元素时需要移动大量元素,那么怎么样才能在插入删除元素时不

    2024年02月21日
    浏览(57)
  • 【一起学数据结构与算法】Java实现双链表

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 打印双链表非常简单,只需要单独创一个结点

    2024年02月22日
    浏览(43)
  • 【Java数据结构 -- 实现双链表的接口方法】

    双链表是一种数据结构,其中每个节点包含 一个指向前一个节点的指针和一个指向后一个节点的指针 。由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来,因此双链表可以任意且快速的插入和删除元素。 引用接口IList,在把

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

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

    2024年02月04日
    浏览(63)
  • [C语言][数据结构][链表] 双链表的从零实现!

    目录 零.必备知识 0.1 一级指针 二级指针 0.2 双链表节点的成员列表         a. 数据         b. 后驱指针         c. 前驱指针 0.3 动态内存空间的开辟 一. 双链表的实现与销毁         1.1 节点的定义         1.2 双向链表的初始化 创建新节点         1.3 尾插       

    2024年04月17日
    浏览(245)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包