c语言数据结构双向链表

双向链表介绍

为了克服单链表单向性的缺点，可利用双向链表，在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱。单链表的全称一般为单向不带头不循环链表，而相对应，双向链表的全称一般为双向带头循环链表。而双向链表的头又称为哨兵位，它本身不含任何信息，它的next指针指向第一个节点，它的prev指针指向最后一个节点。

双向链表的优点

双向遍历：可以从链表的任一端开始遍历，向前或向后查找。

方便的插入和删除：对于任何一个非头(尾)结点，插入和删除操作更方便，因为可以直接访问        前一个或后一个元素，不需要像在单向链表中那样需要遍历找到前驱结点。

灵活性高：与数组等连续存储结构相比，链表在插入和删除操作时不需要移动其他元素，从而      节省了操作时间。

双向链表的应用场景

双向链表非常适合那些需要两个方向遍历的应用，如双向队列、某些类型的缓存实现、文件系统的路径跟踪等等。在需要频繁插入和删除操作的场景下，它也通常比单链表表现得更好。

双向链表的结构

typedef struct List
{
	elem data;
	struct List* next;//后一个结点指针
	struct List* prev;//前一个结点指针
}list;

在下代码之前，为了方便之后的使用，我们先将类型名重命名。

typedef int elem;

双向链表所需的头文件如下：

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

双向链表的创建节点

list* buy(elem x)//申请结点
{
	list* new = (list*)malloc(sizeof(list));
	if (new == NULL)
	{
		perror("malloc");
		exit(1);
	}
	new->data = x;
	new->next = new->prev = new;
	return new;
}

 由于创建双向链表节点的时候，为了方便起见，避免next和prev指针变为野指针，在创建的时候将节点的next和prev指针都指向它本身。

双向链表的初始化

list* ini()//初始化
{
	list* pa = buy(-1);
    return pa;
}

我们可以创建一个新链表用它来接受初始化函数的返回值。

在双向链表中存在一个哨兵位，也就是头节点，它的next指针指向下一个节点，它的prev指针指向最后一个节点，但是在创建哨兵位的时候它也存在相应的数据，但我们可以创建一个不一样的数据来表明它为哨兵位。

尾插法

void PB(list* pa, elem x)//尾插法
{
	assert(pa);
	list* new = buy(x);
	
	new->next = pa;
	new->prev = pa->prev;
	pa->prev->next = new;//分两部分看，pa->prev的next指针
	pa->prev = new;
	
}

有同学可能疑问为什么在插入的时候为什么创建的是一级指针，那是因为在双向链表中哨兵位节点不能被删除，节点的地址也不能发生改变。但我们可以通过改变节点的next和prev指针来增加节点。

在尾插法中，链表需要修改的只有哨兵位的prev和d3的next,所以我们先对创建的节点的next和prev进行修改 ，然后我们再修改d3，pa->prev->next就是pa的prev指向的节点的next指针，使其指向新创建的节点，最后再对pa的prev进行修改，避免地址丢失找不到节点。

头插法

void PF(list* pa, elem x)//头插法
{
	assert(pa);
	list* new = buy(x);
	new->next = pa->next;
	new->prev = pa;
	pa->next->prev = new;
	pa->next = new;
}

由图可见，在头插法中需要修改的只有头节点的next和下一个节点的prev。所以我们先对创建的节点的next和prev进行插入，然后再修改pa的next指针指向的节点的prev进行修改，最后再修改头节点的next指针，避免了节点的丢失。 

打印

为了方便我们观察双向链表，我们可以创建一个打印双向链表数据的函数。

void print(list* pa)//打印函数
{
	list* new = pa->next;
	while (new != pa)
	{
		printf("%d->", new->data);
		new = new->next;
	}
	printf("\n");
}

由于哨兵位是概念中并不含任何元素，所以我们可以新创建一个节点，让它为第一个节点，由于双向链表在整体上是不断循环的，所以我们要在while循环上加上条件，避免死循环，让它在遇到哨兵位的时候循环停下。

尾删

void SB(list* pa)//尾删
{
	assert(pa && pa->next != pa);
	list* del = pa->prev;
	del->prev->next = pa;
	pa->prev = del->prev;
	free(del);
	del = NULL;
}

由图可知，在尾插时改变的有哨兵位结点的prev和前一个结点的next指针。所以在尾插法只需要依次改变这两个结点的指针，最后在释放掉最后一个结点的空间就可以完成尾删。

头删

void SF(list* pa)//头删
{
	assert(pa && pa->next != pa);
	list* del = pa->next;
	pa->next = del->next;
	del->next->prev = pa;
	free(del);
	del = NULL;
}

在头删时，在双向链表中收到影响的有哨兵位的next和第二个节点的prev指针， 为了方便我们先创建一个节点并把头删的节点的地址给他，随后将头节点的next指针进行修改，再将del的next指针指向的节点的prev指向头节点。

查找

list* find(list* pa,elem x)//查找
{
	list* new = pa->next;
	while (new != pa)
	{
		if (new->data == x)
		{
			return new;
		}
		new = new->next;
	}
	return NULL;
}

在查找函数中，我们创建一个节点令它指向第一个节点，并使用while循环让它在双向链表中遍历，如果找到了相对应的数据，那就返回该节点的地址，如果找不到，那就返回NULL,所以我们可以通过判断返回值是否为NULL，来判断是否找到数据。

在指定位置之后插入信息

void IS(list* pos, elem x)//在pos之后插入信息
{
    assert(pos);
	list* new = buy(x);
	new->prev = pos;
	new->next = pos->next;
	pos->next->prev = new;
	pos->next = new;
}

 

在指定位置插入信息时，需要改变的只有插入位置的前一个结点和后一个结点，此时我们需要改变前一个结点的next指针和后一个结点prev指针。注意在改的时候不要丢失结点。

 删除指定位置信息

void LE(list* pos)//删除pos结点
{
    assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
 
}

由图可知，在删除指定位置的结点时影响的只有指定位置的前一个结点和后一个结点，所以我们通过改变pos位置前后结点的next和prev指针，最后释放掉指定位置结点的空间，并将其置为空。

销毁双向链表

void dele(list* pa)//销毁
{
    assert(pa);
	list* new = pa->next;
	while (new != pa)
	{
		list* del = new->next;//创建两个指针可以不断往下找到下一个结点
		free(new);
		new=del;
	}
	free(pa);
	pa = NULL;
 
}

在销毁双向链表时，我们创建两个指针，并让它依次往后遍历，并释放掉new指向的空间，直到遍历完整个链表，最后再将头节点置空就可以了。

可能有同学会疑问一些函数在创建使用时不使用二级指针，还要在之后的main()函数中将结点置空，那是因为我们要保持接口一致性，接口一致性的目标是确保相似的功能有相似的使用方式，且在整个软件系统中保持一致。使得程序更易于理解、使用和维护。

源码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int elem;
typedef struct List
{
	elem data;
	struct List* next;//后一个结点指针
	struct List* prev;//前一个结点指针
}list;
 
list* buy(elem x)//申请结点
{
	list* new = (list*)malloc(sizeof(list));
	if (new == NULL)
	{
		perror("malloc");
		exit(1);
	}
	new->data = x;
	new->next = new->prev = new;
	return new;
}
 
void ini(list** pa)//初始化
{
	*pa = buy(-1);
}
 
void PB(list* pa, elem x)//尾插法
{
	assert(pa);
	list* new = buy(x);
	
	new->next = pa;
	new->prev = pa->prev;
	pa->prev->next = new;//分两部分看，pa->prev的next指针
	pa->prev = new;
	
}
void PF(list* pa, elem x)//头插法
{
	assert(pa);
	list* new = buy(x);
	new->next = pa->next;
	new->prev = pa;
	pa->next->prev = new;
	pa->next = new;
}
 
void print(list* pa)//打印函数
{
	list* new = pa->next;
	while (new != pa)
	{
		printf("%d->", new->data);
		new = new->next;
	}
	printf("\n");
}
void SB(list* pa)//尾删
{
	assert(pa && pa->next != pa);
	list* del = pa->prev;
	del->prev->next = pa;
	pa->prev = del->prev;
	free(del);
	del = NULL;
}
 
void SF(list* pa)//头删
{
	assert(pa && pa->next != pa);
	list* del = pa->next;
	pa->next = del->next;
	del->next->prev = pa;
	free(del);
	del = NULL;
}
 
list* find(list* pa,elem x)//查找
{
	list* new = pa->next;
	while (new != pa)
	{
		if (new->data == x)
		{
			return new;
		}
		new = new->next;
	}
	return NULL;
}
 
void IS(list* pos, elem x)//在pos之后插入信息
{
	assert(pos);
	list* new = buy(x);
	new->prev = pos;
	new->next = pos->next;
	pos->next->prev = new;
	pos->next = new;
}
 
void LE(list* pos)//删除pos结点
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
 
}
 
void dele(list* pa)//销毁
{
	assert(pa);
	list* new = pa->next;
	while (new != pa)
	{
		list* del = new->next;//创建两个指针可以不断往下找到下一个结点
		free(new);
		new=del;
	}
	free(pa);
	pa = NULL;
 
}