C实现通用数据结构--双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别 指向直接后继next和直接前驱prev。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。为了标识链表的头和尾，将 第一个元素的prev指针和最后一个元素的next指针设置为NULL

要反向遍历整个双向链表，使用prev指针从尾到头的顺序访问各个元素，因此为每个元素增加了一个指针的代价，换来的是双向链表更加灵活的访问。

本文地址：http://www.cnblogs.com/archimedes/p/c-datastruct-dlinklist.html，转载请注明源地址。

双向链表接口的定义

1、dlist_init

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

描述：初始化由list指定的双向链表，该操作应该在其他操作之前进行。当调用dlist_destory时，这里传入的参数提供了一种释放动态分配空间的方法

复杂度：O(n)

2、dlist_destroy

void dlist_destroy(DList *list);

描述：销毁由list指定的双向链表，该操作之后其他操作不能进行。除非重新调用dlist_init

复杂度：O(n)

3、dlist_ins_next

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

描述：将元素插入到由list指定的双链表中element元素之后，当链表为空的时候，element为NULL，新的元素包含一个指向data的指针，如果插入成功返回1，否则返回-1

复杂度：O(1)

4、dlist_ins_prev

int dlist_ins_prev(DList *list, DListElmt *element, const void *data);

描述：将元素插入到由list指定的双链表中element元素的前面，当链表为空的时候，element为NULL，新的元素包含一个指向data的指针，如果插入成功返回0，否则返回-1

复杂度：O(1)

5、dlist_remove

int dlist_remove(DList *list, DListElmt *element, void **data);

描述：移除由list指定的双链表中element元素，移除操作成功返回0，否则返回-1

复杂度：O(1)

6、dlist_size

int dlist_size(const DList *list);

描述：这是一个宏，用来计算双链表中元素的个数

复杂度：O(1)

7、dlist_head

DListElmt *dlist_head(const DList *list);

描述：这是一个宏，用来返回由list指定的双链表的头结点

复杂度：O(1)

8、dlist_tail

DListElmt dlist_tail(const DList *list);

描述：这是一个宏，用来返回由list指定的双链表的尾结点

复杂度：O(1)

9、dlist_is_head

int dlist_is_head(const DListElmt *element);

描述：这是一个宏，用来判断由element元素指定的元素是否为头结点，如果是返回1，否则返回0

复杂度：O(1)

10、dlist_is_tail

int dlist_is_tail(const DListElmt *element);

描述：这是一个宏，用来判断由element元素指定的元素是否为尾结点，如果是返回0，否则返回-1

复杂度：O(1)

11、dlist_data

void *dlist_data(const DListElmt *element);

描述：这是一个宏，用来返回由element元素指定的元素的数据域

复杂度：O(1)

12、dlist_next

DListElemt *dlist_next(const DListElmt *element);

描述：这是一个宏，用来返回由element元素指定的元素的后继结点，如果是返回0，否则返回-1

复杂度：O(1)

13、dlist_prev

DListElemt *dlist_prev(const DListElmt *element);

描述：这是一个宏，用来返回由element元素指定的元素的前驱结点，如果是返回0，否则返回-1

复杂度：O(1)

双向链表的实现和分析

抽象数据类型的头文件（list.h）：

typedef struct DListElmt_ { //为双链表结点建立结构

 void *data; //指向结点的数据域

 struct DListElmt_ *prev; //指向结点的前驱结点

 struct DListElmt_ *next; //指向结点的前驱结点

} DListElmt;

typedef struct DList_ { //建立双链表结构

 int size; //元素个数

 int (*match)(const void *key1, const void *key2); 匹配函数

 void (*destroy)(void *data); 析构函数

 DListElmt *head; //指向头结点

 DListElmt *tail; //指向尾结点

} DList;

//公共接口

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

void dlist_destroy(DList *list);

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

int dlist_ins_prev(DList *list, DListElmt *element, const void *data);

int dlist_remove(DList *list, DListElmt *element, 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 dlist_init(DList *list, void (*destroy)(void *data)) { //初始化list

 list- size = 0;

 list- destroy = destroy;

 list- head = NULL;

 list- tail = NULL;

 return;

}

回收双向链表：

void dlist_destroy(DList *list) {

 void *data;

 //移除每个元素

 while (dlist_size(list) 0) {

 if (dlist_remove(list, dlist_tail(list), (void **) data) == 0 list- destroy != NULL) {

 //调用一个用户自定义的函数释放动态分配的内存

 list- destroy(data);

 //现在没有操作了,释放结构体作为预防措施

 memset(list, 0, sizeof(DList));

 return;

}

插入新节点作为指定结点的直接后继结点:

参考如下示意图：

//插入指定元素的后继

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

 DListElmt *new_element;

 //不允许element元素为NULL，除非list为空. 

 if (element == NULL dlist_size(list) != 0)

 return -1; 

 //为element分配空间

 if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)

 return -1;

 //向链表中插入元素

 new_element- data = (void *)data;

 if (dlist_size(list) == 0) {

 //当链表为NULL的时候，插入到头结点 

 list- head = new_element;

 list- head- prev = NULL;

 list- head- next = NULL;

 list- tail = new_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, DListElmt *element, const void *data) {

 DListElmt *new_element; 

 if (element == NULL dlist_size(list) != 0) //不允许element元素为NULL，除非list为空. 

 return -1; 

 if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL) //为element分配空间

 return -1;

 //向链表中插入元素

 new_element- data = (void *)data;

 if (dlist_size(list) == 0) {

 //当链表为NULL的时候，插入到头结点 

 list- head = new_element;

 list- head- prev = NULL;

 list- head- next = NULL;

 list- tail = new_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 = new_element;

 //调整链表长度

 list- size++;

 return 0;

}

删除指定结点:

//删除指定结点

int dlist_remove(DList *list, DListElmt *element, void **data) {

 //不允许删除NULL元素或从空表中删除元素

 if (element == NULL || dlist_size(list) == 0)

 return -1;

 //从表中删除元素

 *data = element- data;

 if (element == list- head) {

 //删除表头结点 

 list- head = element- next;

 if (list- head == NULL) //如果element元素是尾结点

 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;

}

【数据结构】C语言版本的带哨兵位双向循环链表的快速实现方法 我们在之前学双向带头循环链表时，结尾部分简单讲解了快速实现的方法。本篇博客将详细讲解如何迅速实现，通过思路草图的方法轻松写出带头双向循环链表，甚至都可以直接用注释画草图。本篇博客是对 从零开始逐步实现带哨兵位循环双向链表 的补充，之前在写那篇博客的时候不小心忘记实现销毁接口了，这里正好能进行一个补充。
【数据结构】堆的概念 | 从零开始实现数组堆 我们之前似乎确凿在C语言教学里讲过堆，但是那是操作系统中的堆，我们今天将要讲的堆是数据结构里的堆。数据结构中也有栈和堆，它跟操作系统对内存划分中的栈和堆没有关系。我横竖卷不动其他人，于是就打算再更亿篇博客罢。
【数据结构】队列的基本概念 | 从零开始实现队列 | 利用思路草图将思路转变为代码 本章我们将学习 队列 ，首先介绍队列的概念和结构，然后我们将着重讲解栈的实现。我们从零开始写队列的接口，并从零开始步步解读。本章将继续巩固画思路草图的能力，只要思路草图画好了，就可以很轻松地将其转换成代码。