数据结构（初阶）—— C语言实现双向带头循环链表_c双向链表带头尾

 

目录

一、链表种类的优劣

二、什么是双向循环链表 

三，双向循环链表各接口函数实现 

1.双链表的初始化

2.双链表的打印 

3.扩容函数 

4.双链表的尾插 

5.双链表的尾删

6.双链表的头插

7.双链表的头删 

8.双链表的查找

9. 双链表在pos位置之前插入结点

10.双链表删除pos位置的结点 

11.双链表的销毁 

四、源代码 

List.h

List.c

test.c

五、顺序表和双向链表的总结

1.顺序表的优点与缺点

2. 双向链表的优点与缺点

---

一、链表种类的优劣

链表可分为8种：

单向	双向
单向带头循环	双向带头循环
单向带头不循环	双向带头不循环
单向不带头循环	双向不带头循环
单向不带头不循环	双向不带头不循环

在C语言实现链表那篇博客中https://blog.csdn.net/sjsjnsjnn/article/details/123920224?spm=1001.2014.3001.5501

主要实现的是单向不带头非循环的链表结构；

此结构：

        结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

-------------------------------------------------------------------------------------------------------------------------

本次主要分析 双向带头循环链表的链表结构；

此结构：

         结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向 循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而 简单了；

二、什么是双向循环链表 

     双向循环链表和单链表都是由结点组成的，单链表包含一个数据域和一个指针域构成，而双向循环链表不同，它是由一个数据域和两个指针域组成，其中指针包含前驱指针（prev）和后继指针（next）；

三，双向循环链表各接口函数实现 

1.双链表的初始化

//双向带头循环链表的初始化
LTNode* ListInit()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//创建头结点
	phead->next = phead;//后继指针指向头
	phead->prev = phead;//前驱指针指向头
	return phead;
}

2.双链表的打印 

//双向带头循环链表的打印
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d->", cur->Data);
		cur = cur->next;
	}
	printf("\n");
}

3.扩容函数 

//增容函数
LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->Data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

4.双链表的尾插 

//双向带头循环链表的尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

5.双链表的尾删

//双向带头循环链表的尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);
	tailprev->next = phead;
	phead->prev = tailprev;
	//ListErase(phead->prev);//尾删就相当于复用Erase这个函数
}

 

6.双链表的头插

//双向带头循环链表的头插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* next = phead->next;//先找到头
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
	//ListInsert(phead->next, x);
}

 

7.双链表的头删 

//双向带头循环链表的头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//如果哨兵位的后继指针指向的是头，就不能去调用头删
	LTNode* next = phead->next;//先找到头结点
	LTNode* nextNext = next->next;//再找到头结点的下一个结点
	phead->next = next->next;
	nextNext->prev = phead;
}

 

8.双链表的查找

//双向带头循环链表的查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;//从头结点出发
	while (cur != phead)
	{
        //找到返回对应的地址
		if (cur->Data == x)
		{
			return cur;
		}
        //找不到继续向后找
		cur = cur->next;
	}
    //彻底找不到
	return NULL;
}

9. 双链表在pos位置之前插入结点

//双向带头循环链表pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* posPrev = pos->prev;//先找到pos的前一个结点的位置
	LTNode* newnode = BuyListNode(x);
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

10.双链表删除pos位置的结点 

//双向带头循环链表pos位置删除
void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;//找到pos的前一个位置
	LTNode* posNext = pos->next;//和pos的后一个位置
    //把前一个结点和后一个结点链接起来
	posPrev->next = posNext;
	posNext->prev = posPrev;
    //释放pos结点
	free(pos);
	pos = NULL;
}

11.双链表的销毁 

//双向带头循环链表的销毁
void ListDestroy(LTNode* phead)
{
    //在销毁链表的时候，逐个销毁，销毁前一个，必须要保存下一个结点的地址
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

四、源代码 

List.h

#pragma once
 
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
 
typedef int LTDataType;
 
typedef struct ListNode
{
	LTDataType Data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;
 
//双向带头循环链表的初始化
LTNode* ListInit();
 
//双向带头循环链表的打印
void ListPrint(LTNode* phead);
 
//增容函数
LTNode* BuyListNode(LTDataType x);
 
//双向带头循环链表的尾插
void ListPushBack(LTNode* phead, LTDataType x);
 
//双向带头循环链表的尾删
void ListPopBack(LTNode* phead);
 
//双向带头循环链表的头插
void ListPushFront(LTNode* phead, LTDataType x);
 
//双向带头循环链表的头删
void ListPopFront(LTNode* phead);
 
//双向带头循环链表的查找
LTNode* ListFind(LTNode* phead, LTDataType x);
 
//双向带头循环链表pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x);
 
//双向带头循环链表pos位置删除
void ListErase(LTNode* pos);
 
//双向带头循环链表的销毁
void ListDestroy(LTNode* phead);

List.c

#include "List.h"
 
//双向带头循环链表的初始化
LTNode* ListInit()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//创建头结点
	phead->next = phead;//后继指针指向头
	phead->prev = phead;//前驱指针指向头
	return phead;
}
 
//双向带头循环链表的打印
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d->", cur->Data);
		cur = cur->next;
	}
	printf("\n");
}
 
//增容函数
LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->Data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
 
//双向带头循环链表的尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
 
//双向带头循环链表的尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);
	tailprev->next = phead;
	phead->prev = tailprev;
	//ListErase(phead->prev);//尾删就相当于复用Erase这个函数
}
 
//双向带头循环链表的头插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* next = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
	//ListInsert(phead->next, x);
}
 
//双向带头循环链表的头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* next = phead->next;
	LTNode* nextNext = next->next;
	phead->next = next->next;
	nextNext->prev = phead;
}
 
//双向带头循环链表的查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->Data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
 
//双向带头循环链表pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}
 
//双向带头循环链表pos位置删除
void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
	pos = NULL;
}
 
//双向带头循环链表的销毁
void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

test.c

#include "List.h"
 
 
void TestList1()
{
	LTNode* plist = ListInit();
	ListPushBack(plist, 5);
	ListPushBack(plist, 6);
	ListPushBack(plist, 7);
	ListPushBack(plist, 8);
	ListPrint(plist);
	ListPopBack(plist);
	ListPrint(plist);
 
	ListPushFront(plist, 4);
	ListPushFront(plist, 3);
	ListPushFront(plist, 2);
	ListPushFront(plist, 1);
	ListPrint(plist);
	//ListPopFront(plist);
	//ListPopFront(plist);
	//ListPrint(plist);
 
	LTNode* ret = ListFind(plist, 4);
	ListInsert(ret, 30);
	ListPrint(plist);
	ListDestroy(plist);
	plist = NULL;
}
 
int main()
{
	TestList1();
	return 0;
}

五、顺序表和双向链表的总结

1.顺序表的优点与缺点

优点：（可以使用下标访问 ）     

1.支持随机访问；需要随机访问结构支持算法可以很好的适用；

        2.cpu高速缓存命中率更高 

缺点：

        1.头部、中部插入删除数据时间效率低。O(N)

        2.连续的物理空间，空间不够需要增容；

                ①、增容有一定程度消耗

                ②、为了避免频繁增容，一般我们都按倍数去增，用不完可能存在一定的空间浪费

2. 双向链表的优点与缺点

优点：（不可以使用下标访问 ）

        1.任意位置插入，效率高；o(1)

        2.按需申请释放空间；

缺点：

        1.不支持随机访问；意味着：一些排序，二分查找在这种结构上不适用；

        2.链表存储一个值，同时要存储链接指针，也有一定的消耗；

        3.cpu高速缓存命中率更低；