数据结构与算法篇-双向循环链表

typedef struct dlist{
    int data;
    struct dlist *next;
    struct dlist *prev;
}dlist_t;

extern dlist_t *new_dlist_node(int data); //新建一个结点
extern dlist_t *dlist_add(dlist_t *list, int data); //插入一个结点
extern dlist_t *dlist_delete(dlist_t *list, int index); //删除索引对应的结点（索引从0开始）
extern dlist_t *dlist_index_of(dlist_t *list, int index); //查找索引对应的结点
extern void dlist_destroy(dlist_t *list); //销毁双向循环链表
extern void dlist_print(dlist_t *list); //打印链表数据

void free_dlist_node(dlist_t *node){
    if(node == NULL){
        return;
    }

    node->next = NULL;
    node->prev = NULL;
    free(node);
    node = NULL;
}

dlist_t *new_dlist_node(int data){
    dlist_t *node = (dlist_t *)malloc(sizeof(dlist_t));
    if(node == NULL){
        return NULL;
    }

    node->data = data;
    node->next = node;
    node->prev = node;

    return node;
}

dlist_t *dlist_add(dlist_t *list, int data){
    if(list == NULL){
        return NULL;
    }

    //新建一个结点
    dlist_t *node = new_dlist_node(data);
    if(node == NULL){
        return list;
    }

    //将结点插入双向循环链表
    list->prev->next = node;  //最后的结点next指针指向node
    node->next = list;  //node的next指针指向头结点
    node->prev = list->prev;  //node的prev指针指向原尾结点
    list->prev = node;  //头结点的prev指针指向新尾结点

    return list;
}

dlist_t *dlist_delete(dlist_t *list, int index){
    if(list == NULL || index < 0){
        return list;
    }

    dlist_t *head = list;
    int list_index = 0;

    //删除链表头结点
    if(index == 0){
        //链表只有一个结点
        if(head == list->next){
            free_dlist_node(list);
            list = NULL;
            return NULL;
        }else{
            //链表有大于1个结点
            head = head->next; //头结点往后移一个
            head->prev = list->prev; //头结点的prev指向尾部结点
            list->prev->next = head; //尾部结点的next指针指向头结点
            free_dlist_node(list); //释放结点内存
            return head;
        }
    }

    list = list->next;
    list_index++;

    //查询目标结点，通过检查当前结点是否是头结点判断是否已经把双线循环链表遍历了一遍
    while(list_index < index && head != list){
        list = list->next;
        list_index++;
    }
    //没有找到即将删除的结点
    if(head == list){
        return head;
    }
    //找到即将删除的结点
    else{
        list->prev->next = list->next; //目标结点的上一个结点的next指针指向目标结点的下一个结点
        list->next->prev = list->prev; //目标结点的下一个结点的prev指针指向目标结点的上一个结点
        free_dlist_node(list); //释放结点内存
        return head; //返回头结点
    }
}

dlist_t *dlist_index_of(dlist_t *list, int index){
    if(list == NULL || index < 0){
        return NULL;
    }

    //如果想要获取头结点，则直接返回头结点
    if(index == 0){
        return list;
    }

    dlist_t *head = list;
    list = list->next;
    int list_index = 1;
    //遍历链表查找指定的索引，通过检查当前结点是否等于头结点判断是否已遍历完毕
    while(list_index < index && list != head){
        list_index++;
        list = list->next;
    }
    //没有找到索引对应的结点
    if(list == head){
        return NULL;
    }
    //找到了索引对应的结点
    return list;
}

void dlist_destroy(dlist_t *list){
    if(list == NULL){
        return;
    }

    //如果只有一个结点
    if(list->next == list){
        free_dlist_node(list);
        return;
    }

    dlist_t *temp = list;
    list = list->next;
    while(list != temp){
        list = list->next; //遍历下一个结点
        temp->prev->next = list;
        list->prev = temp->prev;
        temp->next = NULL;
        temp->prev = NULL;
        free(temp);
        temp = list;
    }

    free_dlist_node(list);
}

void dlist_print(dlist_t *list){
    if(list == NULL){
        return;
    }

    dlist_t *head = list;
    printf("%d, ", list->data);
    list = list->next;
    while(list != head){
        printf("%d, ", list->data);
        list = list->next;
    }
    printf("\n");
}

#include <stdio.h>
#include "dlist.h"

int main() {
    dlist_t *list = new_dlist_node(2);
    int i = 0;

    for(i = 0; i < 7; i++){
        list = dlist_add(list, 3 + i);
    }
    printf("打印未处理过的完整链表\n");
    dlist_print(list);

    list = dlist_delete(list, 0); //删除第一个结点
    list = dlist_delete(list, 3); //删除第四个结点
    printf("打印删除2个结点后的链表\n");
    dlist_print(list);

    dlist_t *node = dlist_index_of(list, 2);
    printf("第3个结点是：%d\n", node->data);

    printf("销毁链表\n");
    dlist_destroy(list);
    list = NULL;

    return 0;
}

打印未处理过的完整链表
2, 3, 4, 5, 6, 7, 8, 9, 
打印删除2个结点后的链表
3, 4, 5, 7, 8, 9, 
第3个结点是：5
销毁链表