【数据结构】双向链表定义与实现

主页：HABUO🍁主页：HABUO

🌜有时候世界虽然是假的，但并不缺少真心对待我们的人🌛

1.链表的分类

实际上链表有很多种，前面我们所讲述的单链表只是其中一个结构最简单的链表，只不过用起来很麻烦，需要考虑很多种情况。事实上还有带头链表、双向链表等等，基本就是根据带头不带头、单向或者双向、循环或者非循环进行划分，共计8种，我们讲述两个极端，第一个就是无头单向非循环链表，这是结构最简单用起来最麻烦的。第二个就是带头双向循环链表，这是结构最复杂但用起来却是最简单的。相信通过这两个链表的学习，就是用到其它链表也游刃有余。其中这两个链表的结构如下：

无头单向非循环链表(单链表)：

带头双向循环链表：

2.带头双向循环链表

下面我们就类似于前面博客对单链表的介绍一样，对带头双向循环链表的相关接口进行一一实现。

首先我们在头文件中对各种接口的声明进行书写，主要涉及以下接口：

typedef int LTDataType;
//结构体新节点声明
typedef struct ListNode
{
    struct ListNode* prev;
    struct ListNode* next;
    LTDataType data;
}ListNode;

// 创建返回链表的头结点
 ListNode* ListCreate();
 //创建一个新节点
 ListNode* BuyListNode();
 // 双向链表销毁
void ListDestory(ListNode* plist);
 // 双向链表打印
void ListPrint(ListNode* plist);
 // 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
 // 双向链表尾删
void ListPopBack(ListNode* plist);
 // 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
 // 双向链表头删
void ListPopFront(ListNode* plist);
 // 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
 // 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
 // 双向链表删除pos位置的结点
void ListErase(ListNode* pos, ListNode* phead);

这是带头双向循环链表整个工程文件的头文件，包含了结构体的声明，和各种接口的声明。结构体的定义中我们定义了这个节点需要存储的数据、指向下一个节点的地址、以及指向上一个节点的地址，能存储上一个节点的地址是它与单链表最重要的区别，也正是这个区别，让我们在使用的时候也相对简单了不少，接下来我们将对各个接口进行实现，接口实现我们在List.c文件中，测试在test.c文件进行。

首先，因为带头节点，所以我们要首先设置一个头节点，这个头节点是很重要的，具体如下：

//创建一个头节点
ListNode* ListCreate()
{
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    if (head == NULL)
    {
        printf("开辟节点失败");
        return NULL;
    }
    head->next = head;
    head->prev = head;
    return head;
}

头节点，我们malloc一块空间大小为ListNode，让next指向它自己，prev也指向它自己，这样才能满足带头双向循环链表。

下一步，无论是头删头插、尾删尾插、任意位置插删，都需要节点才行，因此我们建立一个接口，专门用来向内存申请空间来建立新节点。具体操作与上述建立头节点大同小异，不再赘述。

紧接着我们就先实现头插头删，具体见下：

// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x)
{
    assert(plist);
    ListNode* next = plist->next;
    ListNode* NewNext = BuyListNode();
    NewNext->data = x;
    NewNext->next = plist->next;
    NewNext->prev = plist;
    plist->next = NewNext;
    next->prev = NewNext;
}

// 双向链表头删
void ListPopFront(ListNode* plist)
{
    assert(plist);
    assert(plist->next != plist);
    ListNode* next = plist->next;
    ListNode* NewNext = next->next;
    NewNext->prev = plist;
    plist->next = NewNext;
    free(next);
    next = NULL;
}

头插头删，在双向链表里，非常简单，只要我们把逻辑搞清楚，头插，就是把头节点的next放入咱们要插入节点的地址，插入节点的prev指向我们头节点的地址，头节点的下一个节点的prev指向我们所要插入的节点，我们所插入节点的next指向这个节点，就这个逻辑，至于插入时有没有节点完全不用考虑，可以仔细想想因为我们有头节点，即使没有其它节点，这个头节点的next是不是就它自己，这是一个闭环怎么做都不会造成单链表这个错误那个错误的。头删亦是如此，只要把各个节点的next、prev维护好就ok！

下面是尾插尾删，只要头插头删会了这跟玩似的！具体见下：

// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x)
{
    assert(plist);
    ListNode* tail = plist->prev;
    ListNode* NewTail = BuyListNode();
    NewTail->data = x;
    NewTail->prev = plist->prev;
    tail->next = NewTail;
    NewTail->next = plist;
    plist->prev = NewTail;
}

// 双向链表尾删
void ListPopBack(ListNode* plist)
{
    assert(plist);
    assert(plist->next != plist);
    ListNode* tail = plist->prev;
    ListNode* NewTail = tail->prev;
    plist->prev = NewTail;
    NewTail->next = plist;
    free(tail);
    tail = NULL;
}

尾插尾删，基本实现逻辑核头插头删大同小异，唯一需要注意的就是，如果没有头节点之外的节点我们是不是就不要删了，头节点对于双向链表来说相当重要，因此才在接口中加入 assert(plist->next != plist)，目的就在于如果只有头节点我们就断言在这里不让他删。

任意位置的插入删除，主要是指定位置之前插入，和指定位置删除，其实是不是就是头插头删中的head换成我们要删节点的前一个节点即可，逻辑完全一样，不再赘述，具体见下：

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
    assert(pos);
    ListNode* prev = pos->prev;
    ListNode* NewPrev = BuyListNode();
    NewPrev->data = x;
    NewPrev->next = pos;
    NewPrev->prev = prev;
    prev->next = NewPrev;
    pos->prev = NewPrev;

}
// 双向链表删除pos位置的结点
void ListErase(ListNode* pos, ListNode* phead)
{
    assert(pos);
    assert(pos != phead);
    ListNode* prev = pos->prev;
    ListNode* next = pos->next;
    prev->next = next;
    next->prev = prev;
    free(pos);
    pos = NULL;
}

还是需要注意的是，就是不能把头节点给我们删除了，因此有 assert(pos != phead)，如果不需要断言的话任意位置删除只需要把pos传过来即可。

🍁这世界上有各种各样的人，恰巧我们成为了朋友🍁

🌟这不是缘分，只仅仅是我们本就应该是朋友🌟