4.双向循环链表的模拟实现

  • 开发
  • 13

1.双向链表的实现

image-20240404225836268

1.1双向链表节点的结构声明

typedef int LTDataType;

typedef struct ListNode
{
    struct ListNode* prev;  // 指向该节点的前一个节点
	struct ListNode* next;  // 指向该节点的后一个节点
	LTDataType data;        // 该节点中存储的数据
}LTNode;					// 将这个结构体重新命名为LTNode

1.2链表的初始化

image-20221221050208838

LTNode* ListInit()
{
    // 创建一个节点，这个节点是哨兵位
	LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
	if (guard == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

    // 这是一个带头双向循环的链表
    // 此时只有一个哨兵位，因此哨兵位的前一个节点和后一个节点都是哨兵位本身
	guard->next = guard;
	guard->prev = guard;

	return guard;
}

1.3 链表的尾插

// 创建一个新节点
LTNode* BuyListNode(LTDataType x)
{
    // 创建一个新节点
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

    // 初始化这个节点的指针，和数据
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
    
	return node;
}

image-20221221045924349

// 尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

    // 尾插一个数据前，创建一个新节点，将这个数据存储到这个节点中
	LTNode* newnode = BuyListNode(x);
    
    // phead就是头节点，因为是双向循环链表，所以phead->prev就是双向循环链表的尾节点
	LTNode* tail = phead->prev;    

    // 尾插一个新节点，就是将下面三个节点，按照顺序进行连接
    // tail newnode phead 
    // 1.尾节点指向新节点
	tail->next = newnode; 
    // 2.新节点的前指针，指向尾节点
	newnode->prev = tail;
    // 3.新节点的后指针，指向头节点
	newnode->next = phead;
    // 4.头节点的前指针，指向新节点，新节点成为这个双向循环链表的新的尾节点
	phead->prev = newnode;
}

1.4链表的打印

image-20220828163401093

void ListPrint(LTNode* phead)
{
	assert(phead);
	printf("phead<=>");
    
    //不打印哨兵位的头
    // phead就是哨兵位，不存储数据，因此不需要进行打印
	LTNode* cur = phead->next;  
    
    // cur等于phead，说明已经循环了一周，所有的数据都已经被打印了
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

1.5链表的头插

  • 方法一

image-20220828164424170

  • 方法二

image-20220828164452671

// 因为双向循环链表是有哨兵位的，头插的节点是插入到哨兵位之后的
// 也就是将 head newnode d1 这三个节点，按照顺序连接就可以
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

    // 方法一：
    // 需要关心节点连接的循序（如果先执行第二步，那么phead指向的就是新节点，而不是d1节点）
	// 创建一个要插入的新节点，存储的数据为x
	LTNode* newnode = BuyListNode(x);
    
    // 第一步
    // phead->next就是d1节点
    // 新节点的后指针指向d1节点
	newnode->next = phead->next;
    // phead->next->prev 就是d1节点的前指针；也就是d1节点的前指针指向新节点
	phead->next->prev = newnode;

    // 第二步
    // 哨兵位的后指针指向新节点
	phead->next = newnode;
    // 新节点的前指针指向哨兵位
	newnode->prev = phead;

    
    
    // 方法二：
    /*
	// 不关心顺序（第一步和第二步哪个先执行都可以）
	LTNode* newnode = BuyListNode(x);
	// 1.先保存d1节点的地址
	LTNode* first = phead->next;
	// 第一步：
	// 哨兵位的后指针指向新节点
	phead->next = newnode;
	// 新节点的前指针指向哨兵位
	newnode->prev = phead;
	
	// 第二步：
	// 新节点的后指针指向d1节点
	newnode->next = first;
	// d1节点的前指针指向新节点
	first->prev = newnode;
	*/
    
    // 方法三：
    // 在phead->next位置前插入，也就是头插
    // void ListInsert(LTNode* pos, LTDataType x)  这个函数就是在pos位置前插入一个节点
	// ListInsert(phead->next, x);
}

1.6链表的尾删

image-20240405171132075

// 用来判断是否为空链表，空链表无法头删
bool ListEmpty(LTNode* phead)
{
	assert(phead);

    // 方法一（比较麻烦）
	/*
	if (phead->next == phead)
		return true;
	else
		return false;
	*/

    // 如果相等，那么就是空链表（因为这是一个双向循环链表）
	return phead->next == phead;
}


void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));

    // 哨兵位的前指针指向的就是双向循环链表的尾节点
	LTNode* tail = phead->prev;
    // 尾节点的前指针指向的前节点将其命名为prev
	LTNode* prev = tail->prev;

    // 要进行尾删，也就是将 phead tail prev 三个节点中的tail删除，再将phead和prev连接
    // 1.连接phead和prev
	prev->next = phead;
	phead->prev = prev;
    
    // 释放要删除的节点空间，将其变为空指针，防止产生野指针
	free(tail);
	tail = NULL;
}

1.7链表的头删

image-20220828170122719

// 对于双向循环链表,头删就是将 phead d1 d2中的d1节点删除，再将phead和d2节点连接
void ListPopFront(LTNode* phead)
{
	assert(phead);
    // 保证这个双向循环链表不是空链表
	assert(!ListEmpty(phead));
	
    // phead->next就是d1节点
    LTNode* first = phead->next;
    // phead->next->next就是d2节点
	LTNode* second = first->next;

    // 连接phead和d2节点
	phead->next = second;
	second->prev = phead;

    // 释放d1节点
	free(first);
	first = NULL;
}

1.8链表节点的数量

size_t ListSize(LTNode* phead)
{
	assert(phead);

	size_t n = 0;
	LTNode* cur = phead->next;
    
    // 当cur != phead，说明链表循环一周结束
	while (cur != phead)
	{
		++n;
		cur = cur->next;
	}

	return n;
}

1.9链表的查找

LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	size_t n = 0;
    // 哨兵位没有存储数据，不需要进行查找
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

        // 迭代
		cur = cur->next;
	}

	return NULL;
}

1.10在pos位置之前插入

image-20220828172755297

// 在pos之前插入
// 也就是将prev newnode pos进行连接
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

    // 将pos前指针指向的节点，命名为prev
	LTNode* prev = pos->prev;
    // 创建一个新节点
	LTNode* newnode = BuyListNode(x);

	// 连接3个节点 prev newnode pos;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

头插

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

    //在phead->next之前插入，也就是头插
	ListInsert(phead->next, x);
}

尾插

image-20220828173223249

void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

    //在phead之前插入，也就是尾插
    ListInsert(phead, x);
}

1.11删除pos位置

image-20220828173538770

void ListErase(LTNode* pos)
{
	assert(pos);

    // prev pos next
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
    
	// 连接prev和next，释放pos节点
	prev->next = next;
	next->prev = prev;
    
	free(pos);
    //需要调用的人自行置空，因为pos是传值拷贝，在这里将pos置空，主函数中的pos并没有被改变
	//pos = NULL; 
}

尾删

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
    
    //删除phead->prev也就是尾删
	ListErase(phead->prev); 
}

头删

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	
    // 删除phead->next也就是头删
	ListErase(phead->next);
}

1.12销毁链表


void ListDestory(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
        // 释放当前节点
		free(cur);
        
        // 迭代
		cur = next;
	}

    // 释放哨兵位
	free(phead);
    
    // 可以传二级，内部置空头结点
	// 建议：也可以考虑用一级指针，让调用ListDestory的人置空  （保持接口一致性）
	// phead = NULL;
}

2.双向循环链表的完整实现

  • List.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

// 双链表的节点的结构体
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;


// 初始化一个双向循环链表
LTNode* ListInit();
// 销毁这个双向循环链表
void ListDestory(LTNode* phead);

// 打印链表
void ListPrint(LTNode* phead);

// 尾插
void ListPushBack(LTNode* phead, LTDataType x);

// 头插
void ListPushFront(LTNode* phead, LTDataType x);

// 尾删
void ListPopBack(LTNode* phead);

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

// 判断链表是否为空
bool ListEmpty(LTNode* phead);

// 链表的节点数量
size_t ListSize(LTNode* phead);

// 查找指定节点
LTNode* ListFind(LTNode* phead, LTDataType x);

// pos位置前插入节点
void ListInsert(LTNode* pos, LTDataType x);
// 删除pos位置的节点
void ListErase(LTNode* pos);
  • List.c
#include "List.h"

// 初始化，并返回哨兵位的地址
LTNode* ListInit()
{
	LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
	if (guard == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

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

	return guard;
}

// 创建一个新节点
LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}

// 打印链表中的数据
void ListPrint(LTNode* phead)
{
	assert(phead);
	printf("phead<=>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	ListInsert(phead, x);
}

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	ListInsert(phead->next, x);
}

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));

	ListErase(phead->prev);
}

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));

	ListErase(phead->next);
}

bool ListEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

size_t ListSize(LTNode* phead)
{
	assert(phead);

	size_t n = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		++n;
		cur = cur->next;
	}

	return n;
}

LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	size_t n = 0;
	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* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);

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

// 删除pos位置
void ListErase(LTNode* pos)
{
	assert(pos);

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

	prev->next = next;
	next->prev = prev;
	free(pos);
	//pos = NULL;
}

// 可以传二级，内部置空头结点
// 建议：也可以考虑用一级指针，让调用ListDestory的人置空  （保持接口一致性）
void ListDestory(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
}
  • main.c
#define _CRT_SECURE_NO_WARNINGS

#include "List.h"

void TestList1()
{
	// 初始化链表
	LTNode* plist = ListInit();

	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);

	ListPrint(plist);

	ListPushFront(plist, 10);
	ListPushFront(plist, 20);
	ListPushFront(plist, 30);
	ListPushFront(plist, 40);
	ListPrint(plist);

	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);

	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);

	// 防止内存泄漏
	ListDestory(plist);
	plist = NULL;
}

void TestList2()
{
	LTNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);

	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);

	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);

	ListDestory(plist);
	plist = NULL;
}

void TestList3()
{
	LTNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);

	// ...
}

int main()
{
	TestList2();

	return 0;
}

3.顺序表和链表的区别

image-20220828180116805

image-20220828180145437
image-20220828180204839

阅读全部

相关推荐

  2. 模拟LinkedList实现的双向循环链表

    2024-04-06 11:24:01       10 阅读

  4. 带头循环双向链表的实现

    2024-04-06 11:24:01       20 阅读

  5. python实现的循环双向链表

    2024-04-06 11:24:01       12 阅读

  8. 模拟LinkedList实现的双向链表

    2024-04-06 11:24:01       10 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-04-06 11:24:01       16 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-04-06 11:24:01       16 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-04-06 11:24:01       15 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-04-06 11:24:01       18 阅读

热门阅读

  1. C++入门

    C++入门

    2024-04-06 11:24:01      14 阅读

  2. Linux 指令

    2024-04-06 11:24:01       22 阅读

  3. MySQL Payload

    2024-04-06 11:24:01       13 阅读

  5. 金蝶Apusic应用服务器 未授权目录遍历漏洞复现

    2024-04-06 11:24:01       13 阅读

  7. 在Ubuntu 14.04上如何备份和恢复Redis数据

    2024-04-06 11:24:01       18 阅读

  8. 关于阿里云中RDS数据库的CPU使用率和内存使用率的20道高级面试题2

    2024-04-06 11:24:01       14 阅读

  11. Flink集群从节点TaskManager启动分析

    2024-04-06 11:24:01       12 阅读

  13. 大语言模型LLM《提示词工程指南》学习笔记01

    2024-04-06 11:24:01       14 阅读

  14. 如何更改WordPress站点的域名：完全指南

    2024-04-06 11:24:01       15 阅读

  15. Day3-struct类型、列转行、行转列、函数

    2024-04-06 11:24:01       15 阅读

  17. MySQL 里记录货币用什么字段

    2024-04-06 11:24:01       13 阅读

  21. C# Socket发送、接收结构体

    2024-04-06 11:24:01       18 阅读

  27. 【ubuntu】Vim配置记录

    2024-04-06 11:24:01       14 阅读

  28. ubuntu20.04 安裝PX4 1.13

    2024-04-06 11:24:01       16 阅读

  30. 习题3-2 高速公路超速处罚

    2024-04-06 11:24:01       13 阅读