C语言数据结构 - 链表（双向链表实现）

傷城~ 2023-10-10 18:43 192阅读 0赞

#include <stdlib.h>
    
    typedef int bool;
    #define TRUE 1
    #define FALSE 0
    
    // 节点值类型（初始默认为int，后期可以改为需要的类型）
    typedef int E;
    
    // 链表节点结构体
    typedef struct ListNode {
        E ele; // 节点值
        struct ListNode *prev; // 前驱节点
        struct ListNode *next; // 后继节点
    } Node;
    
    // 链表结构体
    typedef struct List {
        Node *head; // 头节点
        Node *tail; // 尾节点
        int size; // 链表长度
    } LinkedList;
    
    /*!
     * 初始化链表
     * @return 链表指针
     */
    LinkedList *init() {
        // 申请内存
        LinkedList *list = (LinkedList *) malloc(sizeof(LinkedList));
    
        // 申请内存失败
        if (list == NULL) {
            return NULL;
        }
    
        // 初始化链表成员
        list->head = NULL;
        list->tail = NULL;
        list->size = 0;
    
        return list;
    }
    
    /*!
     * 释放链表
     * @param list 链表
     */
    void destroy(LinkedList* list) {
        Node* cur = list->head;
    
        // 释放链表各个节点的内存
        while(cur != NULL) {
            Node* tmp = cur->next;
            free(cur);
            cur = tmp;
        }
    
        // 释放链表结构体内存
        free(list);
    }
    
    /*!
     * 插入元素
     * @param list 链表
     * @param index 插入位置
     * @param ele 元素值
     * @return 操作结果
     */
    bool add(LinkedList *list, int index, E ele) {
        // 注意:越界位置中尾巴位置list->size可以插入
        if (index < 0 || index > list->size) {
            return FALSE;
        }
    
        // 申请内存，创建一个新节点
        Node *node = (Node *) malloc(sizeof(Node));
    
        // 申请内存失败
        if (node == NULL) {
            return FALSE;
        }
    
        // 初始化节点
        node->ele = ele;
        node->prev = NULL;
        node->next = NULL;
    
        if (list->size == 0) {
            // 空链表插入
            list->head = node;
            list->tail = node;
        } else if (index == 0) {
            // 头插
            node->next = list->head;
            list->head->prev = node;
            list->head = node;
        } else if (index == list->size) {
            // 尾插
            list->tail->next = node;
            node->prev = list->tail;
            list->tail = node;
        } else {
            // 中间位置插入
            Node *cur = list->head;
    
            for (int i = 0; i < index; i++) {
                cur = cur->next;
            }
    
            Node *prevIndexNode = cur->prev;
            prevIndexNode->next = node;
            node->prev = prevIndexNode;
    
            Node *nextIndexNode = cur;
            node->next = nextIndexNode;
            nextIndexNode->prev = node;
        }
    
        // 节点数+1
        list->size++;
    
        return TRUE;
    }
    
    /*!
     * 删除元素
     * @param list 链表
     * @param index 指定删除位置
     * @return 被删除的元素的地址（注意：返回值是特地开辟了一块内存来存储的，因此使用完该返回值，需要注意释放内存，避免内存泄露）
     */
    E *delete(LinkedList *list, int index) {
        // 越界位置不能删除
        if (index < 0 || index >= list->size) {
            return NULL;
        }
    
        // 指向将被删除节点
        Node *removeNode;
    
        if (list->size == 1) {
            // 单节点链表删除唯一节点
            removeNode = list->head;
            list->head = NULL;
            list->tail = NULL;
        } else if (index == 0) {
            // 头删
            removeNode = list->head;
            list->head = list->head->next;
            list->head->prev = NULL;
        } else if (index == list->size - 1) {
            // 尾删
            removeNode = list->tail;
            list->tail = list->tail->prev;
            list->tail->next = NULL;
        } else {
            // 中间位置删除
            Node *cur = list->head;
            for (int i = 0; i < index; i++) {
                cur = cur->next;
            }
    
            removeNode = cur;
    
            Node *prev = cur->prev;
            Node *next = cur->next;
    
            prev->next = next;
            next->prev = prev;
        }
    
        // 链表节点个数-1
        list->size--;
    
        // 申请一块内存用于存放被删除节点的值
        E *p = (E *) malloc(sizeof(E));
        *p = removeNode->ele;
    
        // 释放被删除节点的空间
        free(removeNode);
    
        return p;
    }
    
    /*!
     * 修改元素
     * @param list 链表
     * @param index 指定修改位置
     * @param ele 元素值
     * @return 操作结果
     */
    bool set(LinkedList *list, int index, E ele) {
        // 越界位置无法操作
        if (index < 0 || index >= list->size) {
            return FALSE;
        }
    
        // 找到index位置的节点cur
        Node *cur = list->head;
        for (int i = 0; i < index; i++) {
            cur = cur->next;
        }
    
        // 修改节点值
        cur->ele = ele;
    
        return TRUE;
    }
    
    /*!
     * 查找元素
     * @param list 链表
     * @param index 查找位置
     * @return 指定位置的元素值
     */
    E *get(LinkedList *list, int index) {
        // 越界位置无法操作
        if (index < 0 || index >= list->size) {
            return NULL;
        }
    
        // 找到index位置的节点cur
        Node *cur = list->head;
        for (int i = 0; i < index; i++) {
            cur = cur->next;
        }
    
        // 返回元素值
        return &cur->ele;
    }