单链表(Singly Linked List)结构

单向链表(又名单链表、线性链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过从头部开始,依序往下读取。

21796f454953f919e6b34e7eeaaa5a2d jpg

代码:

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

/**
 * 定义数据结构
 */
typedef struct slist_node {
    void *data;
    struct slist_node *next;
} slist_node;

typedef struct slist {

    size_t size;

    struct slist_node *head;
    struct slist_node *tail;

} slist;

/**
 * 创建链表节点
 * @param data
 * @return
 */
slist_node *slist_node_new(void *data) {

    slist_node *node = malloc(sizeof(struct slist_node));

    node->data = data;
    node->next = NULL;

    return node;
}

/**
 * 创建链表
 * @return
 */
slist *slist_new() {
    slist *list = malloc(sizeof(struct slist));
    list->head = list->tail = NULL;
    list->size = 0;
    return list;
}

/**
 * 追加
 * @param list
 * @param data
 * @return
 */
slist_node *slist_append(slist *list, void *data) {

    slist_node *node = slist_node_new(data);

    if (list->size == 0) {
        list->head = list->tail = node;
    } else {

        list->tail->next = node;
        list->tail = node;
    }

    list->size += 1;

    return node;
}

#define slist_head(list) (list->head)
#define slist_tail(list) (list->tail)
#define slist_data(list_node) (list_node->data)
#define slist_length(list) (list->size)
#define slist_node_next(list_node) (list_node->next)
#define slist_empty(list) (list->size == 0)

/**
 * 移除链表头
 * @param list
 * @return
 */
slist *slist_remove_head(slist *list) {

    slist_node *node = list->head;
    list->head = node->next;
    free(node);
    list->size -= 1;

    return list;
}

bool slist_exist(slist * list, slist_node *node) {

    slist_node *current = list->head;
    while (current) {
        if (current == node) {
            return true;
        }
        current = current->next;
    }

    return false;
}
/**
 * 通过传入回调遍历链表, 第二个参数为函数指针
 * @param list
 * @param cb
 */
void slist_foreach(slist *list, void (*cb) (void *)) {
    if (list->size == 0) {
        return ;
    }

    slist_node *node = list->head;
    while (node) {
        cb(node->data);
        node = node->next;
    }
}

void slist_insert(slist_node *current, slist_node *node) {
    slist_node *next = current->next;
    current->next = node;
    node->next = next;
}

void slist_insert_head(slist *list, slist_node *node) {
    node->next = list->head;
    list->head = node;
}
/**
 * 释放资源,将使用 malloc 创建的所有数据资源释放,包含
 * 所有的 node 和 list, 理论上还有 data, 因为 data
 * 为泛型, 有可能是复杂的 struct 实例
 * @param list
 */
void slist_free(slist *list, void (*data_free) (void *)) {

    slist_node *current = list->head;
    slist_node *next;

    while (current) {
        next = current->next;

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

    free(list);
}