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

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

一,前言

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日
    浏览(9)
  • 数据结构——实现单向链表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    2024年02月09日
    浏览(8)
  • 数据结构——实现双向链表

    怎么说呢?光乍一听名字好像很难的样子是吧,那如果你这样认为的话,可就要让你大跌眼镜了哦,其实双向带头循环链表从操作和理解上来说都是要易于单项不带头不循环链表(俗称单链表)的。 咱们就来见识见识吧!希望真的能让你们“大跌眼镜”哈! 双向带头循环链

    2024年02月07日
    浏览(14)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包