【双向链表的实现】

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

世上有两种耀眼的光芒，一种是正在升起的太阳，一种是正在努力学习编程的你!一个爱学编程的人。各位看官，我衷心的希望这篇博客能对你们有所帮助，同时也希望各位看官能对我的文章给与点评，希望我们能够携手共同促进进步，在编程的道路上越走越远!

提示：以下是本篇文章正文内容，下面案例可供参考

1. 双向链表的结构

注意：这里的“带头”跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严谨，但是为了同学们更好的理解就直接称为单链表的头节点。

带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”

“哨兵位”存在的意义：遍历循环链表避免死循环。

2. 双向链表的实现

2.1 头文件 ——双向链表的创建及功能函数的定义

List.h

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

//定义双向链表的节点的结构
typedef int STDataType;

typedef struct ListNode
{
    STDataType data;
    struct ListNode* next;//保存下一个节点的地址
    struct ListNode* prev;//保存前一个节点的地址
}LTNode;

//链表的初始化
//void LTInit(LTNode** pphead);//前提：我们要传入一个头节点

//我们更倾向于第二种初始化的方法
//因为双向链表为空（只有一个哨兵位：哨兵位节点是不能被操作的，即不能被改变）
LTNode* LTInit();//不需要传入参数，调用该方法之后给我们返回一个头节点

//在双向链表中不会改变哨兵位，所以可以传一级指针
//尾插入操作
void LTPushBack(LTNode* phead, STDataType x);

//头插
void LTPushFront(LTNode* phead, STDataType x);

//链表的打印
void LTPrint(LTNode* phead);

//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);

//在pos位置之后插入的数据
void LTInsert(LTNode* pos, STDataType x);
//删除pos位置的节点
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, STDataType x);

//链表的销毁
void LTDestroy(LTNode* phead);

2.2 源文件 ——双向链表的功能函数的实现

List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

//链表的初始化
//前提：我们要传入一个头节点
//void LTInit(LTNode** pphead)
//{
//    *pphead = (LTNode*)malloc(sizeof(LTNode));
//    if (*pphead == NULL)
//    {
//        perror("malloc");
//        return;
//    }
//    //节点有三部分内容：数据 前驱指针 后继指针
//    (*pphead)->data = -1;//哨兵位
//    (*pphead)->next = (*pphead)->prev = *pphead;
//}

//链表初始化
//不需要传入参数，调用该方法之后给我们返回一个头节点
LTNode* LTInit()
{
    LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
    if (phead == NULL)
    {
        perror("malloc");
        return;
    }
    phead->data = -1;
    phead->next = phead->prev = phead;
    return phead;
}

//申请一个新的节点
LTNode* ListBuyNode(STDataType x)
{
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    node->data = x;
    node->next = node->prev = NULL;
    return node;
}

//链表的打印
void LTPrint(LTNode* phead)
{
    LTNode* cur = phead->next;

    while (cur != phead)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

//尾插入操作
void LTPushBack(LTNode* phead, STDataType x)
{
    assert(phead);
    LTNode* node = ListBuyNode(x);

    //先处理新节点node的前驱和后继指针
    node->prev = phead->prev;
    node->next = phead;

    //在处理phead->prev（之前的尾节点）和phead
    phead->prev->next = node;
    phead->prev = node;
}

//头插
void LTPushFront(LTNode* phead, STDataType x)
{
    assert(phead);
    LTNode* node = ListBuyNode(x);
    //node的节点 next prev
    node->prev = phead;
    node->next = phead->next;
    //处理phead phead->next
    phead->next->prev = node;
    phead->next = node;
}

//尾删
void LTPopBack(LTNode* phead)
{
    assert(phead);
    //链表不能为空链表：链表中只有一个哨兵位节点
    assert(phead->next != phead);

    LTNode* del = phead->prev;
    //先处理del->prev节点
    del->prev->next = phead;
    //处理phead
    phead->prev = del->prev;

    free(del);
    del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
    assert(phead&& phead->next != phead);
    LTNode* del = phead->next;

    //phead del->next
    del->next->prev = phead;
    phead->next = del->next;
    free(del);
    del = NULL;
}

//在pos位置之后插入的数据
void LTInsert(LTNode* pos, STDataType x)
{
    assert(pos);
    LTNode* node = ListBuyNode(x);
    //node的prev 和 next
    node->next = pos->next;
    node->prev = pos;
    //pos的next 和 pos->next的prev
    pos->next = node;
    node->next->prev = node;
}
//删除pos位置的节点
void LTErase(LTNode* pos)
{
    assert(pos);
    //pos->prev:next pos pos->next:prev
    pos->next->prev = pos->prev;
    pos->prev->next = pos->next;
    free(pos);
    pos = NULL;
}
//查找数据
LTNode* LTFind(LTNode* phead, STDataType x)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

//链表的销毁
void LTDestroy(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        LTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    //除了循环之后，还有哨兵位没有被释放
    free(phead);
    phead = NULL;
    //我们将phead指向的空间释放掉，plist实参的空间也被释放掉了，phead置为空
    //但是此时plist实参为野指针，还需要我们手动置为空
}

2.3 源文件 ——双向链表功能的测试

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "List.h"

void ListTest()
{
    //第一种初始化方法：
    /*LTNode* plist = NULL;
    LTInit(&plist);*/

    //第二种初始化方法;
    LTNode* plist = LTInit();

    //尾插
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    //打印
    LTPrint(plist);

    头插
    //LTPushFront(plist, 5);
    //LTPushFront(plist, 6);
    //LTPushFront(plist, 7);
    //LTPrint(plist);

    //尾删
    //LTPopBack(plist);

    //头删
    /*LTPopFront(plist);
    LTPopFront(plist);*/

    //测试指定位置之后插入
    //LTNode* find = LTFind(plist, 1);
    //LTInsert(find, 11);
    /*LTErase(find);
    LTPrint(plist);*/

    //销毁链表
    LTDestroy(plist);
    //传一级指针的要手动将plist置为空
    plist = NULL;
}
int main()
{
    ListTest();
    return 0;
}