【数据结构】双向链表

YoungMLet

发布于 2024-03-01 10:26:43

910

发布于 2024-03-01 10:26:43

文章被收录于专栏：C++/Linux

双向链表

带头双向循环链表的实现

今天我们来实现一下带头双向循环链表，顾名思义，带头就是有哨兵位，哨兵位不是链表的头，它是连接头节点的一个节点，方便操作链表而已；双向就是一个节点可以找到下一个节点，也可以找到上一个节点，所以每个节点应该有两个结构体指针；循环就是没有空指针，哨兵位的上一个节点是尾，尾的下一个节点是哨兵位；如下图为带头双向循环链表：

1. 函数的声明

以下是函数的声明部分，我们主要实现双向链表的增删查改功能；

		#pragma once
		#include <stdio.h>
		#include <stdlib.h>
		#include <assert.h>
		#include <stdbool.h>
		
		//类型的命名
		typedef int LTDataType;
		
		//定义节点
		typedef struct ListNode
		{
			struct ListNode* prev;
			struct ListNode* next;
			LTDataType data;
		}LTNode;
		
		//初始化链表
		LTNode* ListInit();
		
		//打印链表
		void ListPrint(LTNode* phead);
		
		//判断是否是空链表
		bool IsEmpty(LTNode* phead);
		
		//尾插、头插、头删、尾删
		void ListPushBack(LTNode* phead, LTDataType x);
		void ListPushFront(LTNode* phead, LTDataType x);
		void ListPopFront(LTNode* phead);
		void ListPopBack(LTNode* phead);
		
		//查找
		LTNode* LTFindPos(LTNode* phead, LTDataType x);
		
		//在pos位置之前插入
		void LTInsertPos(LTNode* pos, LTDataType x);
		
		//删除pos位置
		void LTErasePos(LTNode* pos);
		
		//销毁
		void LTDestroy(LTNode* phead);

2. 函数的实现

为了防止创建新的节点的时候重复出现，我们将创建节点写成一个函数：

		LTNode* BuyListNode(int x)
		{
			LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
			assert(newnode);
		
			newnode->data = x;
			newnode->next = NULL;
			newnode->prev = NULL;
			return newnode;
		}

初始化节点，只需要一个哨兵位，它的next和prev都指向自己；

		LTNode* ListInit()
		{
			LTNode* phead = BuyListNode(-1);
			phead->next = phead;
			phead->prev = phead;
		
			return phead;
		}

打印链表的函数：

		void ListPrint(LTNode* phead)
		{
			assert(phead);
		
			LTNode* cur = phead->next;
			printf("guard<==>");
			while (cur != phead)
			{
				printf("%d<==>",cur->data);
				cur = cur->next;
			}
			printf("\n");
		}

由于头删尾删的时候不能是空链表，带头的链表的空链表相当于只有一个哨兵位，所以头删尾删的时候链表中不能只剩下哨兵位；

		bool IsEmpty(LTNode* phead)
		{
			assert(phead);
			return phead->next == phead;
		}

尾插函数：

		void ListPushBack(LTNode* phead,LTDataType x)
		{
			assert(phead);
			LTNode* newnode = BuyListNode(x);
			LTNode* tail = phead->prev;
		
			newnode->next = phead;
			tail->next = newnode;
		
			newnode->prev = tail;
			phead->prev = newnode;
		}

头插函数：

		void ListPushFront(LTNode* phead, LTDataType x)
		{
			assert(phead);
			LTNode* newnode = BuyListNode(x);
			LTNode* next = phead->next;
		
			newnode->next = next;
			newnode->prev = phead;
			next->prev = newnode;
			phead->next = newnode;
		}

头删函数：

		void ListPopFront(LTNode* phead)
		{
			assert(phead);
			assert(!IsEmpty(phead));
		
			LTNode* del = phead->next;
			LTNode* next = del->next;
		
			phead->next = next;
			next->prev = phead;
			free(del);
		}

尾删函数：

		void ListPopBack(LTNode* phead)
		{
			assert(phead);
			assert(!IsEmpty(phead));
		
			LTNode* tail = phead->prev;
			LTNode* tailprev = tail->prev;
		
			tailprev->next = phead;
			phead->prev = tailprev;
			free(tail);
		}

查找某个节点的函数，返回找到的节点，否则返回空；

		LTNode* LTFindPos(LTNode* phead, LTDataType x)
		{
			assert(phead);
		
			LTNode* cur = phead->next;
			while (cur)
			{
				if (cur->data == x)
				{
					return cur;
				}
				cur = cur->next;
			}
			return NULL;
		}

在pos位置之前插入的插入函数：

		void LTInsertPos(LTNode* pos, LTDataType x)
		{
			assert(pos);
		
			LTNode* newnode = BuyListNode(x);
		
			LTNode* ptr = pos->prev;
		
			ptr->next = newnode;
			newnode->next = pos;
			pos->prev = newnode;
			newnode->prev = ptr;
		}

删除pos位置的函数：

		void LTErasePos(LTNode* pos)
		{
			assert(pos);
			assert(!IsEmpty(pos));
		
			LTNode* ptr = pos->prev;
			LTNode* next = pos->next;
		
			ptr->next = next;
			next->prev = ptr;
			free(pos);
		}

销毁链表的函数：

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

3. 主函数测试

		#include "List.h"
		
		int main()
		{
			LTNode* phead = ListInit();
		
			ListPushBack(phead, 1);
			ListPushBack(phead, 2);
			ListPushBack(phead, 3);
			ListPushBack(phead, 4);
		
			ListPushFront(phead, 10);
		
			ListPopBack(phead);
		
			ListPopFront(phead);
		
			LTNode* pos = LTFindPos(phead, 3);
			LTInsertPos(pos, 20);
			LTErasePos(pos);
		
		
			ListPrint(phead);
			LTDestroy(phead);
			return 0;
		}

以上就是带头双向循环链表的基本实现，感兴趣的伙伴可以自行尝试噢！！！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-01-03，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构