I C语言 I 实现双向循环链表

实现细节：

1、带一个哨兵位（哨兵节点，初始节点，不存储有效数据，用来方便后期数据的存储与查找）

2、与单向链表不同的是，双向链表中每个数据节点包含两个指针，分别指向前后两个节点

3、双向链表是循环的，其尾节点后不是空指针，而是与头部的哨兵节点通过指针相连

辅助理解图：

具体实现代码：

1、****对链表进行初始化：

初始化：哨兵位的前后指针均指向哨兵节点本身

void ListInit(ListNode** pphead)
{
    *pphead = (ListNode*)malloc(sizeof(ListNode));
    if (*pphead == NULL)
    {
        perror("ListInit");
        exit(-1);
    }
    (*pphead)->date = -1;
    (*pphead)->next = *pphead;
    (*pphead)->prev = *pphead;
}

2、任意位置前的插入

注意：插入位置前后节点中的前后指针要进行相应的更换

void Any_insert(ListNode* pos,Listtype date)
{
    ListNode* Prev = pos->prev;
//建立新节点
    ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
    if (NewNode == NULL)
    {
        perror("Any_insert");
        exit(-1);
    }
    NewNode->date = date;
    NewNode->next = pos;
    pos->prev = NewNode;
    Prev->next = NewNode;
    NewNode->prev = Prev;
}

3、任意位置的删除

** 细节点：当链表中没有数据时，就不用删除，因此需要建立一个函数进行判断**

bool Determine(ListNode* pphead)
{//判断链表中有无元素
    assert(pphead);
    return pphead == pphead->next; 
}

void Any_delet(ListNode* pos)
{
    assert(!Determine(pos));
    ListNode* Next = pos->next;
    ListNode* Prev = pos->prev;
    Next->prev = Prev;
    Prev->next = Next;
    free(pos);
}

4、头插和尾删

** 此处的插入和删除，十分方便，即：对上面的任插和任删进行套用**

头插如下：

void Head_insert(ListNode* pphead, Listtype date)
{
    ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
    if (NewNode == NULL)
    {
        perror("Head_insert");
        exit(-1);
    }

    //单独实现
    //NewNode->date = date;
    //NewNode->prev = pphead;
    //NewNode->next = pphead->next;
    //pphead->next->prev = NewNode;
    //pphead->next = NewNode;
    
    //进行任插的复用
    Any_insert(pphead->next ,date);

}

** 尾删如下：**

void Tail_delet(ListNode* pphead)
{
    assert(pphead);

    //单独实现
    //assert(Determine(pphead));
    /*ListNode* tail = pphead->prev;
    if (tail != pphead)
    {
        ListNode* tailprev = tail->prev;
        tailprev->next = pphead;
        pphead->prev = tailprev;
        free(tail);
    }*/

    //尾删的复用
    Any_delet(pphead->prev);
}

完整代码：

头文件：

#pragma once
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int Listtype;

typedef struct ListNode
{
    struct ListNode* prev;
    Listtype date;
    struct ListNode* next;
}ListNode;

void ListInit(ListNode** pphead);                      //链表初始化
void ListNode_ADD(ListNode* pphead, Listtype date);    //尾插
void Head_insert(ListNode* pphead, Listtype date);     //头插
void ListNode_Print(ListNode* pphead);                 //链表打印
void Tail_delet(ListNode* pphead);                     //尾删
bool Determine(ListNode* pphead);                      //判断表中有无数据
void Any_insert(ListNode* pos, Listtype date);         //任插
void Any_delet(ListNode* pos);                         //任删
void List_Destory(ListNode* pos);                      //链表清空

//___________________________________________________________________________________________________________________________________________________________________________________________________

具体函数：

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h" 

//链表打印
void ListNode_Print(ListNode* pphead)
{
    assert(pphead);
    ListNode* phead = pphead;
    pphead = pphead->next;
    for (; pphead != phead; pphead = pphead->next)
    {
        printf("%d ", pphead->date);
    }
    printf("\n");
}

bool Determine(ListNode* pphead)
{//判断链表中有无元素
    assert(pphead);
    return pphead == pphead->next; 
}

//链表初始化
void ListInit(ListNode** pphead)
{
    *pphead = (ListNode*)malloc(sizeof(ListNode));
    if (*pphead == NULL)
    {
        perror("ListInit");
        exit(-1);
    }
    (*pphead)->date = -1;
    (*pphead)->next = *pphead;
    (*pphead)->prev = *pphead;
}

//尾插
void ListNode_ADD(ListNode* pphead,Listtype date)
{
    //ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
    //if (NewNode == NULL)
    //{
    //    perror("ADD_malloc");
    //    exit(-1);
    //}
    //NewNode->date = date;
    //NewNode->prev = pphead->prev;
    //pphead->prev->next = NewNode;
    //pphead->prev = NewNode;
    //NewNode->next = pphead;

    //任插的复用
    Any_insert(pphead, date);

}
void Head_insert(ListNode* pphead, Listtype date)
{
    ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
    if (NewNode == NULL)
    {
        perror("Head_insert");
        exit(-1);
    }
    //NewNode->date = date;
    //NewNode->prev = pphead;
    //NewNode->next = pphead->next;
    //pphead->next->prev = NewNode;
    //pphead->next = NewNode;
    
    //进行任插的复用
    Any_insert(pphead->next ,date);

}

void Tail_delet(ListNode* pphead)
{
    assert(pphead);
    //assert(Determine(pphead));
    
    /*ListNode* tail = pphead->prev;
    if (tail != pphead)
    {
        ListNode* tailprev = tail->prev;
        tailprev->next = pphead;
        pphead->prev = tailprev;
        free(tail);
    }*/

    //尾删的复用
    Any_delet(pphead->prev);
}

//在任意位置前插入
void Any_insert(ListNode* pos,Listtype date)
{
    ListNode* Prev = pos->prev;
    ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
    if (NewNode == NULL)
    {
        perror("Any_insert");
        exit(-1);
    }
    NewNode->date = date;
    NewNode->next = pos;
    pos->prev = NewNode;
    Prev->next = NewNode;
    NewNode->prev = Prev;
}

//任意位置删除
void Any_delet(ListNode* pos)
{
    assert(!Determine(pos));
    ListNode* Next = pos->next;
    ListNode* Prev = pos->prev;
    Next->prev = Prev;
    Prev->next = Next;
    free(pos);
}

//链表清空
void List_Destory(ListNode* pos)
{
    ListNode* head = pos,*Prev = pos->prev;
    for (pos = pos->prev; head != pos;pos = Prev)
    {
        Prev = pos->prev;
        Any_delet(pos);
    }
    printf("\n清空完成\n");
}

//___________________________________________________________________________________________________________________________________________________________________________________________________

测试：

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

void ListTest(ListNode** pphead)
{
    ListInit(pphead);
    Head_insert(*pphead, 60);
    Head_insert(*pphead, 100);
    Head_insert(*pphead, 60);
    Head_insert(*pphead, 50);
    ListNode_Print(*pphead);

    Tail_delet(*pphead);
    Tail_delet(*pphead);
    Tail_delet(*pphead);

    ListNode_Print(*pphead);
}

int main()
{
    ListNode* pphead = NULL;
    ListTest(&pphead);

    return 0 ;
}

//___________________________________________________________________________________________________________________________________________________________________________________________________