双向链表基本操作

1.DLinklist.h

#pragma once

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

//构建一个结构体,包含链表的数据,前一个指针及后一个指针
typedef char DLinkType;

typedef struct DLinkNode {
    DLinkType data;
    struct DLinkNode* next;
    struct DLinkNode* prev;
} DLinkNode;

void DLinkListInit(DLinkNode** head);//链表的初始化

DLinkNode* DLinkListPushBack(DLinkNode* head, DLinkType value);//尾插

void DLinkListPopBack(DLinkNode* head);//尾删

void DLinkListPushFront(DLinkNode* head, DLinkType value);//头插

void DLinkListPopFront(DLinkNode* head);//头删

DLinkNode* DLinkListFind(DLinkNode* head, DLinkType to_find);//查找

/**
* @brief 往指定位置之前插入一个元素
*/
void DLinkListInsert(DLinkNode* pos, DLinkType value);//前插

/**
* @brief 往指定位置之后插入一个元素
*/
void DLinkListInsertAfter(DLinkNode* pos, DLinkType value);//后插

void DLinkListErase(DLinkNode* head,DLinkNode* pos);//删除指定位置的元素


void DLinkListRemove(DLinkNode* head,DLinkType value); //删除指定值的元素


void DLinkListRemoveAll(DLinkNode* head,DLinkType value);//删除所有相同值得元素


size_t DLinkListSize(DLinkNode* head); //链表长度


int DLinkListEmpty(DLinkNode* head);//链表是否为空


void DLinkListDestroy(DLinkNode** head);//销毁链表

2.DLinklist.c

#include "dblinklist.h"

DLinkNode* CreateNode(DLinkType value){
    DLinkNode* new_node = (DLinkNode*)malloc(sizeof(DLinkNode));
    new_node->data = value;
    new_node->next = new_node;
    new_node->prev = new_node;
    return new_node;
}

void DestroyNode(DLinkNode* ptr){
    free(ptr);
}

void DLinkListInit(DLinkNode** head){
    if(head == NULL){
        //非法输入
        return;
    }
    DLinkNode* cur = CreateNode('0');
    *head = cur;
}

DLinkNode* DLinkListPushBack(DLinkNode* head, DLinkType value){
    if(head == NULL){
        //非法输入
        return NULL;
    }
    DLinkNode* new_node = CreateNode(value);
    head->prev->next = new_node;
    new_node->prev = head->prev;
    head->prev = new_node;
    new_node->next = head;
    return new_node;
}

void DLinkListPopBack(DLinkNode* head){
    if(head == NULL){
        //非法输入
        return;
    }
    DLinkNode* to_delete = head->prev;
    to_delete->prev->next = head;
    head->prev = to_delete->prev;
    DestroyNode(to_delete);
}

void DLinkListPushFront(DLinkNode* head, DLinkType value){
    if(head == NULL){
        //非法输入
        return;
    }
    DLinkNode* new_node = CreateNode(value);
//    head->next = new_node;
//    new_node->prev = head;
//    head->prev = new_node->next;
//    new_node->next = head->prev;
    DLinkNode* new_node_prev = head;
    DLinkNode* new_node_next = head->next;
    new_node->prev = new_node_prev;
    new_node->next = new_node_next;
    new_node_prev->next = new_node;
    new_node_next->prev = new_node;
    return;
}


void DLinkListPopFront(DLinkNode* head){
    if(head ==NULL){
        //非法输入
        return;
    }
    DLinkNode* to_delete = head->next;
    head->next = to_delete->next;
    to_delete->next->prev = head;
    return;
}

DLinkNode* DLinkListFind(DLinkNode* head, DLinkType to_find){
    if(head ==NULL){
        //非法输入
        return NULL;
    }
    DLinkNode* cur = head->next;
    while(cur != head){
        if(cur->data == to_find){
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

void DLinkListInsert(DLinkNode* pos, DLinkType value){
    if(pos == NULL){
        //非法输入
        return;
    }
    DLinkNode* to_insert = CreateNode(value);
    to_insert->prev = pos->prev;
    pos->prev->next = to_insert;
    pos->prev = to_insert;
    to_insert->next = pos;
    return;
}

void DLinkListInsertAfter(DLinkNode* pos, DLinkType value){
    if(pos == NULL){
        //非法输入
        return;
    }
    DLinkNode* to_insert = CreateNode(value);
    to_insert->next = pos->next;
    pos->next->prev = to_insert;
    pos->next = to_insert;
    to_insert->prev = pos;
    return;
}

void DLinkListErase(DLinkNode* head,DLinkNode* pos){
    if(head == NULL){
        //非法输入
        return;
    }
    DLinkNode* pos_prev = pos->prev;
    DLinkNode* pos_next = pos->next;


    pos_prev->next = pos_next;
    pos_next->prev = pos_prev;


    DestroyNode(pos);
    return;
}


void DLinkListRemove(DLinkNode* head,DLinkType value){
    if(head ==NULL){
        //非法输入
        return;
    }
    DLinkNode* pos = DLinkListFind(head,value);
    if(pos!=NULL){
        DLinkListErase(head,pos);
    }
    return;
}


void DLinkListRemoveAll(DLinkNode* head,DLinkType value){
    if(head == NULL){
        //非法输入
        return;
    }
    while(1){
    DLinkNode* pos = DLinkListFind(head,value);
    if(pos!=NULL){
        DLinkListErase(head,pos);
        }else
            break;
    }
    return;
}


size_t DLinkListSize(DLinkNode* head){
    if(head == NULL){
        //非法输入
        return 0;
    }
    size_t count = 0;
    DLinkNode* cur = head->next;
    while(cur!=head){
        cur = cur->next;
        ++count;
    }
    return count;
}


int DLinkListEmpty(DLinkNode* head){
    if(head->next == head && head->prev == head){
        return 1;
    }
    return 0;
}


void DLinkListDestroy(DLinkNode** head){
    if(head == NULL){
        //非法输入
        return;
    }
    DLinkNode* to_destroy = (*head)->next;
    while(to_destroy!=(*head)){
        DLinkNode* cur = to_destroy;
        (*head)->next = to_destroy->next;
        to_destroy->next->prev = *head;
        DestroyNode(cur);
        to_destroy = to_destroy->next;
    }
    DestroyNode(*head);
    *head = NULL;
    return;
}