数据结构---双链表

前言：

在算法和数据结构总结---单链表中总结数据结构中最基本的结构---单链表，但是单链表正如它的名字一样，只能单向的的遍历结点。那么有没有一种数据结构是可以双向遍历的，可以向前遍历，也可以向后遍历了。双向链表就是这样的数据结构。

双链表

双链表的每个数据成员除了数据域和next指针外还增加了一个prev指针指向前驱元素。在内存中每一个链表结点的长度增加，换来可以更为灵活对链表的结点进行访问。比如单链表在查找一个链表结点的时只能不停的向后进行遍历，而双链表可以向前也可以向后。为了标识链表头和链表尾，链表头的元素的prev指针为NULL，链表尾的元素的next指针为NULL。

双向链表接口的公共接口

---

void dlist_init(DList*list,void (*destroy)(void *data));

返回值：无
描述：这个是双向链表初始化函数，必须在链表进行其他操作其使用，DList*list是双向链表的头尾信息结构体。当调用list_destroy时，destroy参数提供一种释放动态内存的方法。当链表中的元素有动态分配的内存，在摧毁链表时必须free掉分配的动态内存。destroy作为一个用户自己可以设置的析构函数，提高了链表的稳定性，如果链表当中不存在应该释放的动态内存，destroy的值应该为NULL。

时间复杂度：O(1) 在链表初始化时，时间是固定的。

---

void dlist_destroy(List* list)

返回值：无
描述：销毁list指向的双向链表，在销毁后不可以对list进行任何的数组操作，除非重新在对数组进行初始化操作，如果传给dlist_init函数的形参destroy不是NULL的话，则每次移除链表元素都要执行该函数一次。

时间复杂度：O(n) n代表链表中元素的个数。

---

int dlist_ins_next(DList* list, ListElement* element, const void* data);

返回值：如果成功插入链表返回0，出现错误返回-1
描述：将元素插入element元素的后结点之后。当初如element为空链表的时候，新元素可能加入链表的任何一个地方。为了避免出现错误，element应该设置为NULL。

时间复杂度：O(1) 插入的行为是固定时间的

---

int list_ins_prev(DList* list, ListElement* element, const void* data);

返回值：如果成功插入链表返回0，出现错误返回-1
描述：将元素插入element元素的后结点之前。当初如element为空链表的时候，新元素可能加入链表的任何一个地方。为了避免出现错误，element应该设置为NUL

时间复杂度：O(1) 插入的行为是固定时间的

int dlist_rem_next(DList* list, ListElement* element, void** data);

返回值：如果返回值成功则返回0，出现错误则返回-1
描述：函数的功能是移除，从list指向的双向链表中移除由element指向的元素，并把element中数据地址返回给用户指定的data中。

复杂度：O(1) 移除链表元素的时间是固定的

---

宏定义

#define dlist_size(list) ((list)->size)
#define dlist_head(list) ((list)->head)
#define dlist_tail(list) ((list)->tail)
#define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0)
#define dlist_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define dlist_data(element) (element->data)
#define dlist_next(element) (element->next)
#define dlist_prev(element) (element->prev)

复杂度：O(1) 宏定义的时间都是固定的，为了提高代码的可读性

单链表的头文件dlist.h

//clist.h
#pragma once
#ifndef DLIST_H 
#define DLIST_H 
// 双向链表中元素
typedef struct DListElement_
{
	void* data;
	struct DListElement_* prev;
	struct DListElement_* next;
}DListElement;

typedef struct Dlist_ 
{
	void* data;
	int size;
	int (*match)(const void* key1, const void* key2);
	void (*destroy)(void* data);
	DListElement* head;
	DListElement* tail;
}DList;

// 双向链表接口
void dlist_init(DList*list,void (*destroy)(void *data));
void dlist_destroy(DList* list);
int  dlist_ins_next(DList* list, DListElement* element, const void* data);
int  dlist_ins_prev(DList* list, DListElement* element, const void* data);
int  dlist_remove(DList* list,DListElement *element,const void **data);

#define dlist_size(list) ((list)->size)
#define dlist_head(list) ((list)->head)
#define dlist_tail(list) ((list)->tail)
#define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0)
#define dlist_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define dlist_data(element) (element->data)
#define dlist_next(element) (element->next)
#define dlist_prev(element) (element->prev)



#endif

双向链表函数的实现原理

链表初始化

void list_init(DList* list, void (destroy)(void data));

---

链表初始化的操作很简单，只要创造一个空链表就可以，将存储链表头和尾信息的结果体置
为空指针，链表的长度size为0。链表的析构函数置为我们指定的析构函数。

---

void dlist_init(DList* list, void (*destroy)(void* data))
{
	list->size = 0;
	list->destroy = destroy;
	list->head = NULL;
	list->tail = NULL;
	
	return;
}

双向链表后插

int dlist_ins_next(DList* list, ListElement* element, const void* data)

---

双向链表的后插和单向链表的后插很相似，最大的区别就是在于出了要管理next指针的指向外，在要管理prev指针的指向正确。 最后整个list的长度要加1；

归纳起来可以分解成下面几步。

1. 插入的链表节点的prev指向上一个链表节点的prev。
2. 插入链表节点的next指向上一个节点next指向的值注意不是值，这里面的值就是原本下一节点的pre的地址。
3. 将上一个链表节点的next存储值设置为改节点的地址。
4. 下一节点prev的存储的值设为插入节点的next地址。

int  dlist_ins_next(DList* list, DListElement* element, const void* data)
{   
	DListElement* new_element;
	if (element == NULL && dlist_size(list) != 0) 
	{
		return -1;
	}
	
	if ((new_element = (DListElement *)malloc(sizeof(DListElement))) == NULL)
	{
		return -1;
	}
	if (dlist_size(list) == 0)
	{
		list->head = element;
		list->head->next = NULL;
		list->head->prev = NULL;
		list->tail = element;
	}
	else
	{
		new_element->next = element->next;
		new_element->prev = element;
		if (element->next == NULL)
		{
			list->tail = new_element;
		}
		else
		{
			element->next->prev = new_element;
		}
		element->next = new_element;
	}
	list->size++;
	return 0;
}

双向链表后插

int dlist_ins_pre(DList* list, ListElement* element, const void* data)

---

双向链表的前插和单向链表的后插很相似，最大的区别就是在于出了要管理next指针的指向外，在要管理prev指针的指向正确。 最后整个list的长度要加1；

int  dlist_ins_prev(DList* list, DListElement* element, const void* data)
{
	DListElement* new_element;
	if (element == NULL && dlist_size(list) != 0)
	{
		return -1;
	}
	if ((new_element = (DListElement*)malloc(sizeof(DListElement))) == NULL)
	{
		return -1;
	}
	if (dlist_size(list) == 0)
	{
		list->head = element;
		list->head->next = NULL;
		list->head->prev = NULL;
		list->tail = element;
	}
	else
	{
		new_element->next = element;
		new_element->prev = element->prev;
		if (element->prev == NULL)
		{
			list->head = new_element;
		}
		else
		{
			element->prev->next = new_element;
		}
		element->prev = element;
	}
	list->size++;
	return 0;
}

双向链表移除

int dlist_remove(DList* list, ListElement* element, const void* data)

双向链表的后插和单向链表的后插很相似，最大的区别就是在于出了要管理next指针的指向外，在要管理prev指针的指向正确。 最后整个list的长度要减1；

int  dlist_remove(DList* list, DListElement* element, const void** data)
{
	if (element == NULL || dlist_size(list) == 0)
	{
		return -1;
	}
	*data = element->data;
	if (element == list->head)
	{
		list->head = element->next;
		if (list->head == NULL)
		{
			list->tail = NULL;
		}
		else
			element->next->prev = NULL;
	}
	else
	{
		element->prev->next = element->next;
		if (element->next == NULL)
		{
			list->tail = element->prev;
		}
		else
		{
			element->next->prev = element->prev;
		}
		free(element);
		list->size--;
		return 0;
	}

}

完整代码：

#pragma once
#ifndef DLIST_H 
#define DLIST_H 
// 双向链表中元素
typedef struct DListElement_
{
	void* data;
	struct DListElement_* prev;
	struct DListElement_* next;
}DListElement;

typedef struct Dlist_ 
{
	void* data;
	int size;
	int (*match)(const void* key1, const void* key2);
	void (*destroy)(void* data);
	DListElement* head;
	DListElement* tail;
}DList;

// 双向链表接口
void dlist_init(DList*list,void (*destroy)(void *data));
void dlist_destroy(DList* list);
int  dlist_ins_next(DList* list, DListElement* element, const void* data);
int  dlist_ins_prev(DList* list, DListElement* element, const void* data);
int  dlist_remove(DList* list,DListElement *element,const void** data);

#define dlist_size(list) ((list)->size)
#define dlist_head(list) ((list)->head)
#define dlist_tail(list) ((list)->tail)
#define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0)
#define dlist_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define dlist_data(element) (element->data)
#define dlist_next(element) (element->next)
#define dlist_prev(element) (element->prev)



#endif

#include <stdio.h>
#include <stdlib.h>
#include "dlist.h"


void dlist_init(DList* list, void (*destroy)(void* data))
{
	list->size = 0;
	list->destroy = destroy;
	list->head = NULL;
	list->tail = NULL;
	
	return;
}

void dlist_destroy(DList* list)
{
	void* data;
	while (list->size != 0)
	{
		if (dlist_remove(list,dlist_tail(list),(void **)&data) == 0 &&list->destroy != NULL)
		{
			list->destroy(data);
		}
	}
}

int  dlist_ins_next(DList* list, DListElement* element, const void* data)
{   
	DListElement* new_element;
	if (element == NULL && dlist_size(list) != 0) 
	{
		return -1;
	}
	
	if ((new_element = (DListElement *)malloc(sizeof(DListElement))) == NULL)
	{
		return -1;
	}
	if (dlist_size(list) == 0)
	{
		list->head = element;
		list->head->next = NULL;
		list->head->prev = NULL;
		list->tail = element;
	}
	else
	{
		new_element->next = element->next;
		new_element->prev = element;
		if (element->next == NULL)
		{
			list->tail = new_element;
		}
		else
		{
			element->next->prev = new_element;
		}
		element->next = new_element;
	}
	list->size++;
	return 0;
}


int  dlist_ins_prev(DList* list, DListElement* element, const void* data)
{
	DListElement* new_element;
	if (element == NULL && dlist_size(list) != 0)
	{
		return -1;
	}
	if ((new_element = (DListElement*)malloc(sizeof(DListElement))) == NULL)
	{
		return -1;
	}
	if (dlist_size(list) == 0)
	{
		list->head = element;
		list->head->next = NULL;
		list->head->prev = NULL;
		list->tail = element;
	}
	else
	{
		new_element->next = element;
		new_element->prev = element->prev;
		if (element->prev == NULL)
		{
			list->head = new_element;
		}
		else
		{
			element->prev->next = new_element;
		}
		element->prev = element;
	}
	list->size++;
	return 0;
}

int  dlist_remove(DList* list, DListElement* element, const void** data)
{
	if (element == NULL || dlist_size(list) == 0)
	{
		return -1;
	}
	*data = element->data;
	if (element == list->head)
	{
		list->head = element->next;
		if (list->head == NULL)
		{
			list->tail = NULL;
		}
		else
			element->next->prev = NULL;
	}
	else
	{
		element->prev->next = element->next;
		if (element->next == NULL)
		{
			list->tail = element->prev;
		}
		else
		{
			element->next->prev = element->prev;
		}
		free(element);
		list->size--;
		return 0;
	}

}