【数据结构】手撕双向链表

男娘i 2024-02-18 10:54 57阅读 0赞

**目录**

前言

1. 双向链表

带头双向循环链表的结构

2. 链表的实现

2.1 初始化

2.2 尾插

2.3 尾删

2.4 头插

2.5 头删

2.6 在pos位置之前插入

2.7 删除pos位置

3.双向链表完整源码

List.h

List.c

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

### 前言 ###

> **在上一期中我们介绍了单链表，也做了一些练习题，在一些题中使用单链表会十分繁琐。因为单链表只能正着走，不能倒着走，例如：回文、逆置。本期我们将学习带头双向循环链表。**

### 1. 双向链表 ###

#### 带头[双向循环链表][Link 1]的结构 ####

![aae326b52f484a89908dfeeaae07429e.png][]

>  **特点：带头双向循环链表结构最复杂，一般用在单独存储数据。结构虽然结构复杂，但是使用代码实现以后会发现结构会带来多优势，实现反而简单了。**

### 2. 链表的实现 ###

#### 2.1 初始化 ####

LTNode* LTInit()
    {
    	LTNode* phead = CreateLTNode(-1);
    	phead->next = phead;
    	phead->prev = phead;
    	return phead;
    }

#### 2.2 尾插 ####

带哨兵位的链表尾插时不用判断是否有节点，两种情况的插入相同，而且还不用传递二级指针。

![916563a76754480aa7fc7323bca266f9.png][]

void LTPushBack(LTNode* phead, LTDateType x)
    {
    	assert(phead);
    
    	LTNode* newnode = CreateLTNode(x);
    	phead->prev->next = newnode;
    	newnode->prev = phead->prev;
    	newnode->next = phead;
    	phead->prev = newnode;
    }

#### 2.3 尾删 ####

在尾删时我们通过 assert(phead->next != phead); 判断链表是否有节点。同时这个代码就有普遍性，不用单独考虑剩一个节点的情况。

![b23705fcae8b42399d5c69e32734e32c.png][]

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

#### 2.4 头插 ####

头删重要的是赋值的顺序，顺序错误会找不到后面的节点，导致内存泄漏。带哨兵位的链表不需要传递二级指针，因为改变的是结构体的变量。

![f03065131fa34c24b0c01e130e50bd93.png][]

void LTPushFront(LTNode* phead, LTDateType x)
    {
    	assert(phead);
    	LTNode* newnode = CreateLTNode(x);
    	newnode->next = phead->next;
    	phead->next->prev = newnode;
    	phead->next = newnode;
    	newnode->prev = phead;
    }

#### 2.5 头删 ####

我们可以多定义几个指针来保存后面节点的地址，这样就不会造成节点的丢失，不用考虑赋值的顺序，会更加方便。

![279fe148456d4761851ab99e9fff2146.png][]

void LTPopFront(LTNode* phead)
    {
    	assert(phead);
    	assert(phead->next != phead);
    
    	LTNode* tail = phead->next;
    	LTNode* next = tail->next;
    	phead->next = next;
    	next->prev = phead;
    	free(tail);
    	tail = NULL;
    }

#### 2.6 在pos位置之前插入 ####

void LTInsert(LTNode* pos, LTDateType x)
    {
    	assert(pos);
    
    	LTNode* posprev = pos->prev;
    	LTNode* newnode = CreateLTNode(x);
    	posprev->next = newnode;
    	newnode->prev = posprev;
    	newnode->next = pos;
    	pos->prev = newnode;
    }

#### 2.7 删除pos位置 ####

void LTErase(LTNode* pos)
    {
    	assert(pos);
    
    	LTNode* posprev = pos->prev;
    	LTNode* posnext = pos->next;
    	posprev->next = posnext;
    	posnext->prev = posprev;
    }

### 3.双向链表完整源码 ###

#### List.h ####

#include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    
    typedef int LTDateType;
    
    typedef struct ListNode
    {
    	LTDateType val;
    	struct ListNode* next;
    	struct ListNode* prev;
    }LTNode;
    
    LTNode* LTInit();
    
    void LTPrint(LTNode* phead);
    
    void LTPushBack(LTNode* phead, LTDateType x);
    
    void LTPushFront(LTNode* phead, LTDateType x);
    
    void LTPopBack(LTNode* phead);
    
    void LTPopFront(LTNode* phead);
    
    LTNode* LTFind(LTNode* phead, LTDateType x);
    
    void LTInsert(LTNode* pos, LTDateType x);
    
    void LTErase(LTNode* pos);
    
    void LTDestroy(LTNode* phead);

#### List.c ####

#include"List.h"
    
    LTNode* CreateLTNode(LTDateType x)
    {
    	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    	if (newnode == NULL)
    	{
    		perror("malloc fail");
    		exit(-1);
    	}
    	newnode->val = x;
    	newnode->next = NULL;
    	newnode->prev = NULL;
    }
    
    LTNode* LTInit()
    {
    	LTNode* phead = CreateLTNode(-1);
    	phead->next = phead;
    	phead->prev = phead;
    	return phead;
    }
    
    void LTPrint(LTNode* phead)
    {
    	assert(phead);
    	LTNode* cur = phead->next;
    	printf("<=>哨兵位<=>");
    	while (cur != phead)
    	{
    		printf("%d<=>", cur->val);
    		cur = cur->next;
    	}
    	printf("\n");
    }
    
    void LTPushBack(LTNode* phead, LTDateType x)
    {
    	assert(phead);
    
    	LTNode* newnode = CreateLTNode(x);
    	phead->prev->next = newnode;
    	newnode->prev = phead->prev;
    	newnode->next = phead;
    	phead->prev = newnode;
    }
    
    void LTPushFront(LTNode* phead, LTDateType x)
    {
    	assert(phead);
    	LTNode* newnode = CreateLTNode(x);
    	newnode->next = phead->next;
    	phead->next->prev = newnode;
    	phead->next = newnode;
    	newnode->prev = phead;
    }
    
    void LTPopBack(LTNode* phead)
    {
    	assert(phead);
    	LTNode* tail = phead->prev;
    	LTNode* tailprev = tail->prev;
    	free(tail);
    	phead->prev = tailprev;
    	tailprev->next = phead;
    }
    
    void LTPopFront(LTNode* phead)
    {
    	assert(phead);
    	assert(phead->next != phead);
    
    	LTNode* tail = phead->next;
    	LTNode* next = tail->next;
    	phead->next = next;
    	next->prev = phead;
    	free(tail);
    	tail = NULL;
    }
    
    LTNode* LTFind(LTNode* phead, LTDateType x)
    {
    	assert(phead);
    
    	LTNode* cur = phead->next;
    	while (cur != phead)
    	{
    		if (cur->val == x)
    		{
    			return cur;
    		}
    			cur = cur->next;
    	}
    	return NULL;
    }
    
    void LTInsert(LTNode* pos, LTDateType x)
    {
    	assert(pos);
    
    	LTNode* posprev = pos->prev;
    	LTNode* newnode = CreateLTNode(x);
    	posprev->next = newnode;
    	newnode->prev = posprev;
    	newnode->next = pos;
    	pos->prev = newnode;
    }
    
    void LTErase(LTNode* pos)
    {
    	assert(pos);
    
    	LTNode* posprev = pos->prev;
    	LTNode* posnext = pos->next;
    	posprev->next = posnext;
    	posnext->prev = posprev;
    }
    
    void LTDestroy(LTNode* phead)
    {
    	assert(phead);
    
    	LTNode* cur = phead->next;
    	while (cur != phead)
    	{
    		LTNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	free(phead);
    	phead = NULL;
    }

> 通过上面链表的实现，我们已经感受到了带头双向循环链表的方便和简单，它不需要去考虑链表是否有元素，还可以找到前一个元素，在我们使用中提供很大的便利。

**本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。**

![210c1b62ef6a46d9bacefd2ae1bcd2b0.png][]

[Link 1]: https://so.csdn.net/so/search?q=%E5%8F%8C%E5%90%91%E5%BE%AA%E7%8E%AF%E9%93%BE%E8%A1%A8&spm=1001.2101.3001.7020
[aae326b52f484a89908dfeeaae07429e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/242be085ea714cb7bddfc2599f38c0b6.png
[916563a76754480aa7fc7323bca266f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/b71a98b754d94ae6bc6918ecec87b919.png
[b23705fcae8b42399d5c69e32734e32c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/006787fdff7349fca8aa835c7538a08d.png
[f03065131fa34c24b0c01e130e50bd93.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/6ab7b2066da141b5b93131d1db760321.png
[279fe148456d4761851ab99e9fff2146.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/f8d499cdfe7246ce9ae0135771360401.png
[210c1b62ef6a46d9bacefd2ae1bcd2b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/01cf3842094649f0afa6cae2979684d3.png