数据结构:详解【链表】的实现(单向链表+双向链表)

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

一,前言

1.顺序表的问题和思考

问题:

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

思考:
如何解决以上问题呢?下面给出了链表的结构来看看。

二 ,有关链表的概念,结构和分类

1. 链表的概念和结构

链表是一种物理存储结构上非连续、非顺序的存储构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

1.1 逻辑结构(就是我们想象的,数据元素依次链接):
数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言

1.2 物理结构(实实在在的在内存中真实存储的结构,数据元素不一定是连续存储的):
数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言

1. 每个结点(一块空间)都是随机在内存中动态开辟(malloc)出来的,都有它们的地址(第一个字节的地址),这些地址也是随机的。
2. 每个新结点都包含两个区域——数据域和指针域。数据域存放我们要操作的数据,指针域存放着下一个结点的地址。我们就是通过这个地址和下一个结点建立联系。
3. 最后一个结点的指针域中存放的是NULL。

2. 链表的分类

实际中的链表种类非常多,以下情况组合起来就有8种链表构:
数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言
比如:
数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言

数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言
数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言

虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构,下面也只对这两种结构进行代码实现:
数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言

  1. 无头单向非循环链表: 结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  2. 带头双向循环链表: 结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。

三,无头单向非循环链表(单链表)

1.单链表的功能

单链表的功能一般有如下几个:

  • 打印数据
  • 动态申请新结点
  • 尾部插入数据
  • 头部插入数据
  • 尾部删除数据
  • 头部删除数据
  • 查找指定数据的位置
  • 在pos位置前插入数据
  • 删除pos处的数据

2.单链表功能的实现

2.1 建立单链表

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;//要操作的数据
	struct SListNode * next;//指向下一个结点的指针
}SLNode;

2.2 打印数据

首先定义一个指针cur指向第一个结点(头指针phead),使用循环进行遍历,当cur != NULL时,打印数据,再让cur指向下一个结点,直至跳出循环。

数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言

代码实现如下:

void SListPrint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

2.3 动态申请新结点
由于链表在内存中不是一块连续的空间,所以每次进行插入(增加)数据的操作时,都要在内存中创建新结点,即动态开辟(malloc)一块空间。

//这个函数是每次在增加数据时进行调用的

SLNode* BuySListNode(SLTDataType x)
{
     //随机开辟一块空间(结点)
	SLNode* newnode =(SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	newnode->data = x;//存入要插入的数据
	newnode->next = NULL;//把最后一个结点指向空

	return newnode;
}

2.4 尾部插入数据
尾插分为两种情况:
1.如果链表中没有结点时,直接让新结点指向头指针;
2.链表中至少有一个结点时,需要循环找到链表的尾结点的指针,再链接上新结点。
数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言
代码实现如下:

void SListPushBack(SLNode** pphead, SLTDataType x)
{
	SLNode* newnode = BuySListNode(x);
	
	//1.如果表中没有一个节点
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//2.有两个节点以上,找尾,
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//链接新节点
		tail->next = newnode;
	}
}

2.5 头部插入数据
头插,首先在内存中开辟一个结点,把链表内原来第一个结点的地址存入新结点中,使两者建立联系,再把新结点的地址存入头指针即可。
数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言

代码实现如下:

void SListPushFront(SLNode** pphead, SLTDataType x)
{
	SLNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

2.6 尾部删除数据
尾删分为三种情况:
1.如果链表中没有数据(链表为空),则不需要删除,略作提示终止程序即可;
2.如果表中只有一个结点,直接free释放,再置空即可;
3.如果表中多于一个结点,不能直接循环找到尾结点删除,这样前一个结点会形成野指针,而是要先保存倒数第二个结点的地址,再把尾结点释放置空。

数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言

代码实现如下:

void SListPopBack(SLNode** pphead)
{
	//1.链表内无数据
	if (*pphead == NULL)
	{
		printf("链表为空!\n");
		return;
	}
	//2.如果只有一个结点
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* prev = NULL;
		SLNode* tail = *pphead;
		//3.记住前一个位置
		while (tail->next != NULL)
		{
			prev= tail;
			tail = tail->next;
		}
		
		free(tail);
		prev->next = NULL;
	}
}

2.7 头部删除数据
头删,相同的道理,不能直接把第一个结点free释放,这样就找不到后面的数据了,而是先要定义一个指针变量保存第二个结点的地址,再把第一个结点free释放,置空。最后让头指针指向这个变量。
数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言

代码实现如下:

void SListPopFront(SLNode** pphead)
{
		SLNode* cur = NULL;
		cur = (*pphead)->next;
		free(*pphead);
		*pphead = cur;
}

2.8 查找指定数据的位置
循环遍历链表,查找出指定数字的位置,用指针pos保存,这个函数一般配合下面两个函数一起使用。

代码实现如下:

SLNode* SListFind(SLNode* phead, SLTDataType x)
{
	SLNode* cur = phead;
	while (cur!=NULL)
	{
		if (cur->data == x)
		{
		   //找到了发回地址
			return cur;
		}
		cur = cur->next;
	}
   //没有找到,返回空
	return NULL;
}

2.9 在pos位置前插入数据
这个函数包含两种情况:
1.当在第一个结点前插入时(pos指向第一个结点,pos是通过查找函数找到的),相当于头插;
2.当在其余结点前插入时,需要一个变量prev保存pos的前一个结点的地址,再把prev,pos,newnode这三个结点链接起来。
数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言
代码实现如下:

void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x)
{
	SLNode* newnode = BuySListNode(x);

	//当在第一个结点前插入时,相当于头插
	if ((*pphead)->next == NULL)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLNode* prev = NULL;
		SLNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		prev = cur;//保存到了pos前一个结点的地址
		prev->next = newnode;
		newnode->next = pos;
	}
}

2.10 删除pos处的数据
相同的,这个函数也包含两种情况:
1.当要删除第一个结点时(此时pos指向第一个结点),相当于头删;
2.当pos指向其他位置时,不能直接free释放掉pos,而是要先找到pos前一个结点的位置,把它与pos的后一个结点进行链接,最后free释放掉pos。

数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言
代码实现如下:

void SListErase(SLNode** pphead, SLNode* pos)
{
	//当要删除第一个结点时,相当于头删
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}

}

3.完整代码

SList.h

#define _CRT_SECURE_NO_WARNINGS 

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

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);

//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);

//打印数据
void SListPrint(SLTNode* phead);

//尾删
void SListPopBack(SLTNode** pphead);

//头删
void SListPopFront(SLTNode** pphead);

//查找
SLTNode* SListFind(SLTNode* pphead, SLTDataType x);

//在pos位置前插入数据
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在pos位置处删除数据
void SListEarse(SLTNode** pphead, SLTNode* pos);

SList.c

#define _CRT_SECURE_NO_WARNINGS

#include "SList.h"

void SListPrint(SLTNode* phead)
{
	SLTNode* cur =phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

SLTNode* BuySListNode(SLTDataType x)
{
	//开辟新节点
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
}

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	//判断刚开始是否有节点,若没有,则直接开辟
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//若已经存在节点 则找到尾结点,链接新节点
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void SListPopFront(SLTNode** pphead)
{
	if (*pphead == NULL)
	{
		printf("链表无数据!\n");
	}
	//注意不能直接free,要先记住第二个节点的地址,再释放第一个节点
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

void SListPopBack(SLTNode** pphead)
{
	//1.当链表为空时
	if (*pphead == NULL)
	{
		printf("链表无数据!\n");
		return;
	}
	//2.只有一个节点时,直接释放掉,再置空
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		//让prev记住倒数第二个节点,此时tail指向最后一个节点
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		//释放最后一个空间
		free(tail);
		//这时prev是最后一个节点,要置空,避免野指针
		prev->next = NULL;
	}
	
}

SLTNode* SListFind(SLTNode* pphead, SLTDataType x)
{
	SLTNode* cur = pphead;
	//遍历链表,找数
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;

	}
	return NULL;
}

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	//要在第一个节点前插入数据时,相当于头插
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = BuySListNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

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

void SListEarse(SLTNode** pphead, SLTNode* pos)
{
	//1.当pos为第一个节点时,没有前一个节点,删除时相当于头删
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	 }
	else
	{
		//2.Pos不是第一个节点,找到pos的前一个位置,再释放空间
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}

}

test.c

#define _CRT_SECURE_NO_WARNINGS 

#include "SList.h"

 //在这里对那些函数接口进行测试,例如:
void SListTest()
{
   //定义一个头指针,置空
	SLTNode* plist = NULL;
	
	//这里传地址的原因是我们要对链表中的数据进行修改,
	//由于形参是实参的一份临时拷贝,改变形参不影响实参
	//所以只有传地址,对内存进行修改
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);

	//在3前面插入有一个30,先找到3的前一个的位置,再插入
	SLTNode* pos = SListFind(plist, 3);
	if (pos)
	{
		SListInsert(&plist,pos,30);
	}
	SListPrint(plist);

}

int main()
{
	SListTest();

	return 0;
}

四,带头双向循环链表(双链表)

虽然单链表是我们要掌握基础链表之一,但是它并不完美,比如它不能从后往前操作,不容易找到前驱,每次尾插,尾删都要进行遍历,使得时间复杂度为O(N)等,使用起来其实并不是那么方便。

下面介绍的双链表虽然结构更复杂,但是它完美解决了单链表的缺陷,使用起来十分方便,丝滑。

1.单链表与双链表的结构区别

数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言

  • 双链表的"带头"是指需要在链表的最前端动态申请一个特殊的结点,这第一个结点不存储有效数据,这种结点也称为带哨兵位的头结点 它的好处是在进行增删查改等操作时,不需要改变传过来的指针了,也就意味着不需要传二级指针了。
    而且,与单链表相比,它不仅有存放下一个结点地址的next指针(也可叫后驱指针),还会增加一个前驱指针prev,用来存放上一个节点的地址。这样就使得每个节点都能快速找到自己的前一个结点,也能找到自己的下一个结点。 最终会形成"循环"。
    双链表的这两点结构对我们增删查改的实现有极大的方便,使它能够完美解决单链表的缺陷。
  • 单链表的结构就更简单了,它没有带头,也没有循环,只能从头到尾前一个结点指向后一个结点。

2.双链表的功能

双链表的功能一般有如下几个:

  • 初始化链表
  • 打印数据
  • 动态申请新结点
  • 尾部插入数据
  • 头部插入数据
  • 尾部删除数据
  • 头部删除数据
  • 查找指定数据的位置
  • 在pos位置前插入数据
  • 删除pos处的数据
  • 销毁链表

3.双链表功能的实现

3.1 建立双链表

typedef int SLTDataType;

typedef struct ListNode
{
	SLTDataType data;//要操作的数据
	struct ListNode* next;//后驱指针
	struct ListNode* prev;//前驱指针

}ListNode;

3.2 初始化链表
首先要申请一个带哨兵位的头结点,并且让它的前驱和后驱都指向自己。
数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言
代码实现如下:

//注意:这个函数并没有进行传参,而是通过返回值的方式
//把申请空间的地址返回。这就避免了使用二级指针。
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

3.3 动态申请新结点
在初始化链表和插入数据时,都需要在内存中动态申请新结点。

ListNode* BuyListNode(SLTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

3.4 打印数据
首先定义一个指针cur指向第二个结点(头节点不存放数据),由于是循环链表,所以通过循环,当cur != phead时,打印出数据即可。

数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言
代码实现如下:

void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;

	if (cur == phead)
	{
		printf("链表为空!\n");
		return;
	}

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

3.5 尾部插入数据
尾插,申请新结点newnode,定义变量tail指向最后一个结点(其实就是phead的前驱,这就避免了要向单链表那样通过遍历找到尾节点,体现出了双链表的优越性。),再链接起phead,newnode,tail

数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言
代码实现如下:

void ListPushBcck(ListNode* phead, SLTDataType x)
{
	assert(phead);//断言
	ListNode* newnode = BuyListNode(x);

	ListNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	
	phead->prev = newnode;
	newnode->next = phead;
	
}

3.6 头部插入数据
头插,就是在头结点phead和和第二个结点之间插入,申请新结点newnode,再定义变量first指向第二个结点,再链接起三者即可。
数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言
代码实现如下:

void ListPushFront(ListNode* phead, SLTDataType x)
{
	assert(phead);

	ListNode* first = phead->next;
	ListNode* newnode = BuyListNode(x);
	
	phead->next = newnode;
	newnode->prev = phead;
	
	newnode->next = first;
	first->prev = newnode;

}

3.7 尾部删除数据
尾删,与单链表类似,不能直接把最后一个结点free释放。定义一个变量tail指向尾结点(其实就是phead->prev),再定义一个变量prev保存倒数第二个结点的地址(其实就是tail->prev),再进行三者链接,最后释放,置空。

数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言
代码实现如下:

void ListPopBcck(ListNode* phead)
{
	assert(phead);
	
	//此时链表一个结点都没有
	assert(phead->next != phead);

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

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

	free(tail);
	tail = NULL;

}

3.8 头部删除数据
头删,是删除第二个结点,不能直接释放第二个结点。定义变量first指向第二个结点(就是phead->next),再定义变量second指向第三个结点(就是first->next),再进行三者链接,最后释放,置空。

数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言
代码实现如下:

void ListPopFront(ListNode* phead)
{
	assert(phead);
	
	//此时链表一个结点都没有
	assert(phead->next != phead);

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

	free(first);
	first = NULL;

}

3.9 查找指定数据的位置
定义变量cur指向第二个结点,直接循环遍历,直至cur指向phead。若找到了,则直接返回该结点的地址,用pos接收,否则返回NULL。这个函数一般与下面两个函数配合使用。

ListNode* ListFind(ListNode* phead, SLTDataType x)
{
	assert(phead);

	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

3.10 在pos位置前插入数据
pos是查找函数找到的位置,申请新结点newnode,定义变量prev指向pos的前一个结点,再链接三者即可。

数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言
代码实现如下:

void ListInsert(ListNode* pos, SLTDataType x)
{
	assert(pos);//断言,pos不能为空

	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);
	
	prev->next = newnode;
	newnode->prev = prev;

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

3.11 删除pos处的数据
与前面类似,不能直接free释放pos处的空间。定义变量prev指向(保存)pos前一个结点的(地址),定义变量next指向(保存)pos后一个结点(地址),再把两者进行链接,最后释放,置空。
数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言
代码实现如下:

void ListEarse(ListNode* pos)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* next = pos->next;

	prev->next = next;
	next->prev = prev;

	free(pos);//释放
	pos = NULL;
}

3.12 销毁链表
销毁链表是从第二个结点开始,循环依次释放。定义变量cur指向第二个结点,与前面类似,不能直接释放cur处的空间,而是要先保存到下一个结点的空间,再把当前节点空间释放。最后再释放头结点(phead),置空。

数据结构:详解【链表】的实现(单向链表+双向链表),数据结构,链表,c语言

代码实现如下:

void ListDestory(ListNode* phead)
{
	assert(phead);
	
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;//保存下一个结点的地址
		free(cur);//先释放有数据的结点
		cur = next;
	}

	free(phead);//释放哨兵位头结点
	phead = NULL;
}

4. 完整代码

List.h

#define _CRT_SECURE_NO_WARNINGS 

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

typedef int SLTDataType;

typedef struct ListNode
{
	SLTDataType data;
	struct ListNode* next;
	struct ListNode* prev;

}ListNode;


//初始化链表
ListNode* ListInit();

//销毁链表
void ListDestory(ListNode* phead);

//打印数据
void ListPrint(ListNode* phead);

//尾插
void ListPushBcck(ListNode* phead, SLTDataType x);

//头插
void ListPushFront(ListNode* phead, SLTDataType x);

//尾删
void ListPopBcck(ListNode* phead);

//头删
void ListPopFront(ListNode* phead);

//查找
ListNode*  ListFind(ListNode* phead, SLTDataType x);

//在pos前插入数据
void ListInsert( ListNode* pos, SLTDataType x);

//删除pos处的数据
void ListEarse( ListNode* pos);

List.c

#define _CRT_SECURE_NO_WARNINGS 

#include "List.h"

ListNode* BuyListNode(SLTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

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

	return phead;
}

void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;

	if (cur == phead)
	{
		printf("链表为空!\n");
		return;
	}

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

void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
	phead = NULL;
}

void ListPushBcck(ListNode* phead, SLTDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);

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

}

void ListPushFront(ListNode* phead, SLTDataType x)
{
	assert(phead);

	ListNode* first = phead->next;
	ListNode* newnode = BuyListNode(x);
	
	phead->next = newnode;
	newnode->prev = phead;
	
	newnode->next = first;
	first->prev = newnode;

}

void ListPopFront(ListNode* phead)
{
	assert(phead);
	
	//此时链表一个结点都没有
	assert(phead->next != phead);

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

	free(first);
	first = NULL;

}

void ListPopBcck(ListNode* phead)
{
	assert(phead);
	
	//此时链表一个结点都没有
	assert(phead->next != phead);

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

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

	free(tail);
	tail = NULL;

}

ListNode* ListFind(ListNode* phead, SLTDataType x)
{
	assert(phead);

	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

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

	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);
	
	prev->next = newnode;
	newnode->prev = prev;

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

void ListEarse(ListNode* pos)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* next = pos->next;

	prev->next = next;
	next->prev = prev;

	free(pos);
	pos = NULL;
}

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

#define _CRT_SECURE_NO_WARNINGS 

#include "List.h"

//在这个函数中进行各函数接口的测试:
ListNode* ListTest()
{
	ListNode* plist = ListInit();

	ListPushBcck(plist, 1);
	ListPushBcck(plist, 2);
	ListPushBcck(plist, 3);
	ListPushBcck(plist, 4);
	ListPrint(plist);


	ListDestory(plist);

	return 0;
}

int main()
{
	ListTest();

	return;
}

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

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

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

相关文章

  • 数据结构《链表》无头单向非循环-动图详解

    前面学习了顺序表发现,顺序表虽然好,但也有很多不足的地方,比方说,顺序表是一块连续的物理空间,如果头插或者头删,那么整个数组的数据都要移动。但是链表不一样,链表是通过指针访问或者调整,链表是物理空间是不连续的,通过当前的next指针找到下一个。 插

    2024年02月06日
    浏览(50)
  • 数据结构——实现单向链表

    单链表是一种常见的数据结构,用于存储一系列的数据元素,每个节点包含数据和指向下一个节点的指针。 单链表通常用于实现某些算法或数据结构,如链式前向星、哈希表、链式栈、队列等等。 单链表在程序设计中的作用不可忽略,是很多基础算法的核心数据结构之一。

    2024年02月07日
    浏览(60)
  • 【数据结构】单向链表实现 超详细

    目录 一. 单链表的实现 1.准备工作及其注意事项 1.1 先创建三个文件 1.2 注意事项:帮助高效记忆和理解 2.链表的基本功能接口 2.0 创建一个 链表 2.1 链表的 打印  3.链表的创建新节点接口 4.链表的节点 插入 功能接口 4.1 尾插接口 4.2 头插接口     4.3 指定位置 pos 之前  插入

    2024年02月19日
    浏览(68)
  • 【数据结构】双向链表详解

    当我们学习完单链表后,双向链表就简单的多了,双向链表中的头插,尾插,头删,尾删,以及任意位置插,任意位置删除比单链表简单,今天就跟着小张一起学习吧!! 还有双向带头不循环链表,双向不带头循环链表,着重使用双向带头循环链表,带头也就是有哨兵位。

    2024年02月09日
    浏览(54)
  • 数据结构入门 — 链表详解_双向链表

    数据结构入门 — 双向链表详解 博客主页链接:https://blog.csdn.net/m0_74014525 关注博主,后期持续更新系列文章 文章末尾有源码 *****感谢观看,希望对你有所帮助***** 第一篇:数据结构入门 — 链表详解_单链表 第二篇:数据结构入门 — 链表详解_双向链表 第三篇:数据结构入门

    2024年02月11日
    浏览(49)
  • 【数据结构】动图详解双向链表

    目录 1.单向链表的劣势 2.带头双向循环链表         1.逻辑结构        2.结点的代码实现 3.双向链表接口的实现         1.接口1---初始化         2.接口2,3---头插,尾插         3. 接口4,5---头删,尾删         3. 接口6---查找          4. 接口7,8--插入,

    2024年01月23日
    浏览(63)
  • 数据结构之双向链表详解

    😽博主CSDN主页:小源_😽 🖋️个人专栏:《数据结构》🖋️ 😀努力追逐大佬们的步伐~ 上一篇文章中我们重点讲解了无头单向非循环链表的模拟实现,现在我们来讲解LinkedList(无头双向链表实现 )的模拟实现。 本章重点: 本文着重讲解了LinkedList(无头双向单链表)的实现

    2024年02月04日
    浏览(56)
  • 数据结构学习分享之双向链表详解

        💓博主CSDN:杭电码农-NEO💓🎉🎉🎉       ⏩专栏分类:数据结构学习分享(持续更新中🫵)⏪🎉🎉🎉       我们上一期说到,两链表中有两个最常用的结构,一个是最简单的无头不循环单向链表,还有一个就是 结构相对比较复杂的带头双向循环链表 ,我们这一章节就来

    2024年02月04日
    浏览(71)
  • 数据结构 - 链表详解(二)—— 带头双向循环链表

    链表的结构一共有 八种 :带头单向循环链表、带头单向非循环链表、带头双向循环链表、带头双向非循环链表、无头单向循环链表、无头单向非循环链表、无头双向循环链表、无头双向非循环链表。 今天我们来详解带头双向循环链表 带头双向循环链表是一种数据结构,它通

    2024年04月26日
    浏览(58)
  • 数据结构:线性表之-循环双向链表(万字详解)

    目录 基本概念 1,什么是双向链表 2,与单向链表的区别 双向链表详解 功能展示: 1. 定义链表 2,创建双向链表 3,初始化链表 4,尾插 5,头插 6,尾删 判断链表是否被删空 尾删代码 7,头删 8,pos位置之前插入 优化后的头插 优化后的尾插 9,删除pos位置的节点 优化后的尾删 优

    2024年02月09日
    浏览(62)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包