C语言实现双向链表

前言

       在讲双向链表之前，我会先总结一下前面的知识点，如需直接看双向链表的，可以直接跳转到双向链表的实现去阅读~~

链表的分类

       在上一篇的8道算法题，我提到了用哨兵位可以很好地进行插入，这个哨兵位就是头结点！还有在解决约瑟夫问题时，我提到了使用循环链表的概念，循环链表就是头尾相连，形成一个环。
链表的分类有这几种情况：带不带头（头结点==哨兵位），单向还是双向（就是一个节点只能找到下一个节点的就是单向，如果既能找到上一个节点又能找到下一个节点就是双向），循环还是不循环（头尾相连的就是循环，头尾不相连的就是不循环）

所以链表一共有八大类，那我们回顾一下什么是单链表，单链表实际上就是不带头单向不循环的链表，这里我要讲的双向链表实际上是带头双向循环的链表，只要我们会这两个链表的实现，其他的链表实现也是很简单的~~

链表的优势

       在C语言进阶的第一篇文章中，我带大家实现了动态顺序表，但是动态顺序表还是有存在空间浪费的出现，举个例子，我一共有101个数据需要保存，但是顺序表在第一百零一的时候会进行2倍或3倍扩容，假设扩2倍，那就是变成200容量，这时候就有99个空间浪费了，链表就可以实现一个数据一个数据的申请节点，不会有空间的浪费，但是单链表有一个缺陷，尾插尾删等操作时需要遍历所有节点导致效率不高，这时候我们就可以使用双向链表来大幅减少这种遍历的出现，也就是我会在下面提到的链表结构。

但是链表也有一个缺点，在数据量少的情况下，链表其实浪费的空间可能更大，因为链表结构是需要带一个或者两个指针的~~

双向链表的实现

双向链表的含义

       双向链表是带头结点（哨兵位），每一个结点都能找到前一个和后一个节点，并且头尾是相连的。形成带头双向循环的链表，双向链表就是它的简称。

那我们来定义双向链表的结构体：

typedef int ListDataType;

typedef struct ListNode
{
	ListDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

初始化和创建新节点

       注意双向链表是一个带头的循环的链表，带头意味着我们在初始化要创建一个头结点，那头结点的两个指针怎么处理？由于这是双向链表，需要头尾相连，因此我们将头节点的两个指针都指向自己！既然如此，我们就写一个函数来创建新节点，让每个新节点的指针开始都指向自己~~

//创建新节点
ListNode* CreatNewnode(ListDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail"); exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;

	return newnode;
}

//初始化
void ListInit(ListNode** pphead)
{
	*pphead = CreatNewnode(-1);
}

头指针的传参问题

尾插

尾插操作，我们需要改变三个节点，分别是newnode，head，还有原来的尾节点head->prev。

//尾插
void ListPushBack(ListNode* phead, ListDataType x)
{
	ListNode* newnode = CreatNewnode(x);

	newnode->prev = phead->prev;
	newnode->next = phead;

	phead->prev->next = newnode;
	phead->prev = newnode;
}

头插

头插，我们需要改变三个节点，newnode，head，d1；我们还是先改变newnode（不会对另外两个产生影响），再改变d1（防止改变head的时候找不到d1），最后改变head。

//头插
void ListPushFront(ListNode* phead, ListDataType x)
{
	ListNode* newnode = CreatNewnode(x);
	
	newnode->prev = phead;
	newnode->next = phead->next;

	phead->next->prev = newnode;
	phead->next = newnode;
}

打印

//打印
void ListPrint(ListNode* phead)
{
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

尾删

//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead && phead->next != phead);

	ListNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

头删

//头删
void ListPopFront(ListNode* phead)
{
	assert(phead && phead->next != phead);

	ListNode* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	free(del);
	del = NULL;
}

查找

//查找
ListNode* ListFind(ListNode* phead, ListDataType x)
{
	ListNode* pcur = phead->next;

	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}

	return NULL;
}

指定位置删除

//指定位置删除
void ListPopPos(ListNode* pos)
{
	assert(pos);
	
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

删除指定位置之前的数据

//删除指定位置前的数据
void ListPopPosFront(ListNode* phead, ListNode* pos)
{
	assert(phead);
	assert(pos && pos->prev != phead);

	ListNode* del = pos->prev;
	del->prev->next = pos;
	pos->prev = del->prev;
	free(del);
	del = NULL;
}

删除指定位置之后的数据

//删除指定位置之后的数据
void ListPopPosAfter(ListNode* phead, ListNode* pos)
{
	assert(phead);
	assert(pos && pos->next != phead);

	ListNode* del = pos->next;
	del->next->prev = pos;
	pos->next = del->next;
	free(del);
	del = NULL;
}

在指定位置之前插入数据

//在指定位置之前插入数据
void ListPushPosFront(ListNode* pos, ListDataType x)
{
	assert(pos);

	ListNode* newnode = CreatNewnode(x);
	newnode->next = pos;
	newnode->prev = pos->prev;

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

在指定位置之后插入数据

//在指定位置之后插入数据
void ListPushPosAfter(ListNode* pos, ListDataType x)
{
	assert(pos);

	ListNode* newnode = CreatNewnode(x);
	newnode->prev = pos;
	newnode->next = pos->next;

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

销毁链表

//销毁链表
void ListDestroy(ListNode* phead)
{
	assert(phead);

	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		ListNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}

//初始化
ListNode* ListInit()
{
	ListNode* phead = CreatNewnode(-1);
	return phead;
}

小结

封装函数

List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int ListDataType;

typedef struct ListNode
{
	ListDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

//初始化
void ListInit(ListNode** pphead);

//打印
void ListPrint(ListNode* phead);

//插入
void ListPushBack(ListNode* phead, ListDataType x);
void ListPushFront(ListNode* phead, ListDataType x);

//删除
void ListPopBack(ListNode* phead);
void ListPopFront(ListNode* phead);

//查找
ListNode* ListFind(ListNode* phead, ListDataType x);

//指定位置删除
void ListPopPos(ListNode* pos);

//删除指定位置前的数据
void ListPopPosFront(ListNode* phead, ListNode* pos);

//删除指定位置之后的数据
void ListPopPosAfter(ListNode* phead, ListNode* pos);

//在指定位置前插入数据
void ListPushPosFront(ListNode* pos, ListDataType x);

//在指定位置之后插入数据
void ListPushPosAfter(ListNode* pos, ListDataType x);

//销毁链表
void ListDestroy(ListNode* phead);

List.c

#include "List.h"

//创建新节点
ListNode* CreatNewnode(ListDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail"); exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;

	return newnode;
}

//初始化
void ListInit(ListNode** pphead)
{
	*pphead = CreatNewnode(-1);
}

//尾插
void ListPushBack(ListNode* phead, ListDataType x)
{
	ListNode* newnode = CreatNewnode(x);

	newnode->prev = phead->prev;
	newnode->next = phead;

	phead->prev->next = newnode;
	phead->prev = newnode;
}

//打印
void ListPrint(ListNode* phead)
{
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

//头插
void ListPushFront(ListNode* phead, ListDataType x)
{
	ListNode* newnode = CreatNewnode(x);
	
	newnode->prev = phead;
	newnode->next = phead->next;

	phead->next->prev = newnode;
	phead->next = newnode;
}

//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead && phead->next != phead);

	ListNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

//头删
void ListPopFront(ListNode* phead)
{
	assert(phead && phead->next != phead);

	ListNode* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	free(del);
	del = NULL;
}

//查找
ListNode* ListFind(ListNode* phead, ListDataType x)
{
	ListNode* pcur = phead->next;

	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}

	return NULL;
}

//指定位置删除
void ListPopPos(ListNode* pos)
{
	assert(pos);
	
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

//删除指定位置前的数据
void ListPopPosFront(ListNode* phead, ListNode* pos)
{
	assert(phead);
	assert(pos && pos->prev != phead);

	ListNode* del = pos->prev;
	del->prev->next = pos;
	pos->prev = del->prev;
	free(del);
	del = NULL;
}

//删除指定位置之后的数据
void ListPopPosAfter(ListNode* phead, ListNode* pos)
{
	assert(phead);
	assert(pos && pos->next != phead);

	ListNode* del = pos->next;
	del->next->prev = pos;
	pos->next = del->next;
	free(del);
	del = NULL;
}

//在指定位置前插入数据
void ListPushPosFront(ListNode* pos, ListDataType x)
{
	assert(pos);

	ListNode* newnode = CreatNewnode(x);
	newnode->next = pos;
	newnode->prev = pos->prev;

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

//在指定位置之后插入数据
void ListPushPosAfter(ListNode* pos, ListDataType x)
{
	assert(pos);

	ListNode* newnode = CreatNewnode(x);
	newnode->prev = pos;
	newnode->next = pos->next;

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

//销毁链表
void ListDestroy(ListNode* phead)
{
	assert(phead);

	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		ListNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}