# 工学1号馆

home

## 双向链表

Wu Yudong    September 26, 2015     Algorithm   594

### 双向链表接口的定义

1、dlist_init

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

2、dlist_destroy

void dlist_destroy(DList *list);

3、dlist_ins_next

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

4、dlist_ins_prev

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

5、dlist_remove

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

6、dlist_size

int dlist_size(const DList *list);

DListElmt *dlist_head(const DList *list);

8、dlist_tail

DListElmt dlist_tail(const DList *list);

int dlist_is_head(const DListElmt *element);

10、dlist_is_tail

int dlist_is_tail(const DListElmt *element);

11、dlist_data

void *dlist_data(const DListElmt *element);

12、dlist_next

DListElemt *dlist_next(const DListElmt *element);

13、dlist_prev

DListElemt *dlist_prev(const DListElmt *element);

### 双向链表的实现和分析

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          *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_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->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->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->tail = new_element;

} else {
//当链表非空的时候插入
new_element->next = element;
new_element->prev = element->prev;
if (element->prev == NULL)
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;

//删除表头结点
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;
}