双链表(Doubly Linked List)结构

959641-20171114141702171-165324270

链表的作用比较广泛,大多作为其它数据结构的基础结构,例如 Queue, Stack,Hash Table 等。

代码:

#ifndef DLIST_H
#define DLIST_H

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

typedef struct dlist_node {

    void *data;
    struct dlist_node *prev;
    struct dlist_node *next;

} dlist_node;

typedef struct dlist {

    size_t size;

    struct dlist_node *head;
    struct dlist_node *tail;

} dlist;

/**
 *
 * @param data
 * @return
 */
dlist_node *dlist_node_new(void *data) {
    dlist_node *node = malloc(sizeof(struct dlist_node));
    node->data = data;
    node->prev = node->next = NULL;

    return node;
}

/**
 *
 * @return
 */
dlist *dlist_new() {
    dlist *list = malloc(sizeof(struct dlist));
    list->size = 0;
    list->head = list->tail = NULL;

    return list;
}

/**
 *
 * @param list
 * @param data
 * @return
 */
dlist_node *dlist_append(dlist *list, void *data) {
    dlist_node *node = dlist_node_new(data);
    if (list->size == 0) {
        list->head = list->tail = node;
    } else {
        node->prev = list->tail;
        list->tail->next = node;
        list->tail = node;
    }

    list->size += 1;

    return node;
}

#define dlist_head(list) (list->head)
#define dlist_tail(list) (list->tail)
#define dlist_length(list) (list->size)
#define dlist_data(node) (node->data)
#define dlist_node_next(node) (node->next)
#define dlist_node_prev(node) (node->prev)

/**
 *
 * @param list
 */
void dlist_remove_head(dlist *list) {
    if (list->size == 0) {
        return ;
    }
    dlist_node *origin_head = list->head;
    list->head = list->head->next;
    list->head->prev = NULL;
    free(origin_head);
    list->size -= 1;
}

/**
 *
 * @param list
 */
void dlist_remove_tail(dlist *list) {
    if (list->size == 0) {
        return ;
    }
    dlist_node *origin_tail = list->tail;
    list->tail = list->tail->prev;
    list->tail->next = NULL;
    free(origin_tail);
    list->size -= 1;
}

/**
 *
 * @param list
 */
void dlist_free(dlist *list, void (*data_free) (void *)) {

    dlist_node *current = list->head;

    while (current) {
        dlist_node *next = current->next;
        if (data_free != NULL) {
            data_free(current->data);
        }
        free(current);
        current = next;
    }

    free(list);
}

/**
 *
 * @param list
 * @param callback
 */
void dlist_foreach(dlist *list, void (*callback) (void *)) {
    if (list->size == 0) {
        return ;
    }

    dlist_node *current = list->head;

    while (current) {
        callback(current->data);
        current = current->next;
    }
}

/**
 *
 * @param list
 * @param data
 * @return
 */
dlist_node *dlist_insert_head(dlist *list, void *data) {

    dlist_node *node = dlist_node_new(data);

    node->next = list->head;
    list->head->prev = node;
    list->head = node;

    list->size += 1;

    return node;
}

/**
 *
 * @param list
 * @param data
 * @return
 */
dlist_node *dlist_insert_tail(dlist *list, void *data) {
    dlist_node *node = dlist_node_new(data);

    node->prev = list->tail;
    list->tail->next = node;
    list->tail = node;
    list->size +=1;

    return node;
}

/**
 *
 * @param list
 * @param current
 * @param data
 * @return
 */
dlist_node *dlist_insert(dlist *list, dlist_node *current, void *data) {

    dlist_node *node = dlist_node_new(data);

    dlist_node *next = current->next;

    current->next = node;
    node->prev = current;
    node->next = next;
    next->prev = node;

    list->size += 1;

    return node;
}
#endif