双链表（数据结构）——C语言

目录

1 概念与结构

2 实现双向链表

申请节点BuyNode

判断双链表是否为空LTEmpty

打印双链表LTPrint

创建双链表LTInit()

尾插LTPushBack

头插LTPushFront

尾删LTPopBack

头删LTPopFront

查找指定节点LTFind

指定位置插入LTInsert

指定位置删除LTErase

销毁双链表LTDestory

3.整体代码

List.h

List.c

1 概念与结构

（注：这里面的“节点”和“结点”是同一个意思）

双链表，既有指向前一个节点的指针，也有指向后一个节点的指针，而且还是循环的，最后一个结点的后一个节点为头指针，头结点的前一个指针为最后一个结点，带头链表⾥的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这⾥“放哨的”

注意：这⾥的“带头”跟前⾯单链表说的“头结点”是两个概念，单链表阶段称呼不严谨。

2 实现双向链表

创建三个文件，List.c,List.h,test.c,分别为实现函数的文件，头文件，测试文件

List.c

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

typedef int DataType;

typedef struct ListNode
{
	DataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

LTNode* LTInit();
void LTDestory(LTNode* phead);

LTNode* BuyNode(DataType x);
LTNode* LTFind(LTNode* phead, DataType x);

bool LTEmpty(LTNode* phead);
void LTPrint(LTNode* phead);

void LTPushBack(LTNode* phead,DataType x);
void LTPushFront(LTNode* phead,DataType x);

void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

void LTInsert(LTNode* pos, DataType x);
void LTErase(LTNode* pos);

包括了结构体LTNode表示结点，这里有一个结构体自引用，用来找到下一个结点位置，以及实现的各种函数这里typedef的SLDataType，便于后续修改数据类型，这里以int类型为例。

申请节点BuyNode

LTNode* BuyNode(DataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}

申请节点，所以这里函数返回值为结构体指针LTNode，这里利用malloc函数，申请空间，将值赋给newnode->data，注意这里满足双链表循环的特点，所以下一个结点，和前一个结点这里不能置为空，都要指向自己。

判断双链表是否为空LTEmpty

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

这里判断结果返回bool类型，当头结点指向自己说明为空。

打印双链表LTPrint

void LTPrint(LTNode* phead)
{
	assert(!LTEmpty(phead));
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

打印双链表中所有的data，这里和单链表一样，需要遍历链表，先定义一个指向有效节点的指针（即头结点的next），但是这里要注意循环截止的条件，根据循环双链表的特点，尾结点的next指向头结点，所以截止的条件当pcur==phead。

创建双链表LTInit()

LTNode* LTInit()
{
	LTNode* node = BuyNode(-1);
	return node;
}

创建双链表即创建头结点(哨兵位)，调用申请节点的函数。

尾插LTPushBack

void LTPushBack(LTNode* phead,DataType x)
{
	assert(phead);
	LTNode* newnode = BuyNode(x);
	newnode->next = phead;
	newnode->prev = phead->prev;

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

从尾部插入，双链表不用像单链表一样遍历去寻找尾结点，直接通过头结点的prev找到尾结点，在通过改变指针的指向完成插入，申请节点，先改变newnode的指针，newnode的prev指向尾结点（即head->prev），newnode的next指向头结点，再改变原来尾结点的next，指向newnode，最后改变head的prev为newnode，注意最后两步的代码位置不能交换。

头插LTPushFront

void LTPushFront(LTNode* phead, DataType x)
{
	assert(phead);
	LTNode* newnode =BuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;

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

注意这里头插，不是在头结点之前插入（头结点之前插入这样的话，就是尾插），而是在头结点之后插入，先申请节点，再改指针指向，newnode的next指向head->next，newnode的prev则指向head，再改变原来第一个有效节点的prev，指向newnode，最后改变head的next指向newnode，同理这里注意最后两步的代码位置不能交换。

尾删LTPopBack

void LTPopBack(LTNode* phead)
{
	assert(!LTEmpty(phead));
	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

断言链表是否为空，从尾部删除，可以先定义删除的结点del，增加代码的可读性，这里只需要改变新的尾结点的next（即del->prev->next）指向头结点，再改变头结点的prev指向新的尾结点（即phead->=del->prev），再将原来的尾结点释放掉即可。

头删LTPopFront

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

断言链表是否为空，这里和头插相同，删除的是头结点之后的结点，还是先定义del，改变新的第一个有效节点的prev指向头结点（即del->next->prev = phead），再改变头结点的next，指向新的第一个有效节点（即phead->next = del->next），最后释放删除的节点。

查找指定节点LTFind

LTNode* LTFind(LTNode* phead, DataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

和单链表一样，先定义一个指向第一个有效节点的指针（即phead->next）要遍历双链表，依次对比pcur->data是否等于x，找到后直接返回pcur，这里还是注意循环截止的条件（pcur==phead），未找到返回NULL。

指定位置插入LTInsert

void LTInsert(LTNode* pos, DataType x)
{
	assert(pos);
	LTNode* newnode = BuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;

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

断言pos为存在的位置，这里和尾插一样只是在pos的后面插入，的先找到pos的next节点，然后先改变newnode指针的指向，先改变newnode的next指向d2，即（pos->next），和newnode的prev指向pos，再改变原来pos->next结点prev的指向newnode（即pos->next->prev = newnode），最后改变pos->next指向新节点newnode。

指定位置删除LTErase

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

断言pos位置有效，这里删除只需要改变pos->next结点的指向，和pos->prev的指向，先改变pos->next结点的prev指向pos->prev,再改变pos->prev的next节点指向pos->next,最后将pos节点释放掉。

销毁双链表LTDestory

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

先定义一个指向第一个有效节点的指针（即phead->next）要遍历双链表，这里销毁要向将pcur的next保存，再删除pcur以免丢失pcur结点（即无法找到pos->next），截止到pcur==phead，最后将头结点也释放掉。

3.整体代码

List.h

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

typedef int DataType;

typedef struct ListNode
{
	DataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

LTNode* LTInit();
void LTDestory(LTNode* phead);

LTNode* BuyNode(DataType x);
LTNode* LTFind(LTNode* phead, DataType x);

bool LTEmpty(LTNode* phead);
void LTPrint(LTNode* phead);

void LTPushBack(LTNode* phead,DataType x);
void LTPushFront(LTNode* phead,DataType x);

void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

void LTInsert(LTNode* pos, DataType x);
void LTErase(LTNode* pos);

List.c

#include"List.h"

LTNode* BuyNode(DataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}

LTNode* LTFind(LTNode* phead, DataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

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

void LTPrint(LTNode* phead)
{
	assert(!LTEmpty(phead));
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

LTNode* LTInit()
{
	LTNode* node = BuyNode(-1);
	return node;
}

void LTPushBack(LTNode* phead,DataType x)
{
	assert(phead);
	LTNode* newnode = BuyNode(x);
	newnode->next = phead;
	newnode->prev = phead->prev;

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

void LTPushFront(LTNode* phead, DataType x)
{
	assert(phead);
	LTNode* newnode =BuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;

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

void LTPopBack(LTNode* phead)
{
	assert(!LTEmpty(phead));
	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

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

void LTInsert(LTNode* pos, DataType x)
{
	assert(pos);
	LTNode* newnode = BuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;

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

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

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