Wu Yudong's Blog

本文利用C语言实现通用双向链表数据结构

双向链表概述

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

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

双向链表接口的定义

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;
}

双向链表

双向链表概述

双向链表接口的定义

双向链表的实现和分析

Comments