数据结构入门：带头双向循环链表实现

双链表概述

本篇介绍双链表，是一种链表数据结构。它的每个节点除了包含数据域（用于存储数据）之外，还包含两个指针域，一个指向前一个节点（prev），另一个指向后一个节点（next）。

1. 双链表接口实现

本次实现的是带头双向循环的链表。不仅有指向前一个节点的 prev 指针，还有指向下一个节点的 next 指针。最后一个节点有指向开头的指针 next，开头的节点有指向结尾的指针 prev，形成循环。

双链表定义

typedef int LTDataType;
typedef struct ListNode {
    struct ListNode* next;
    struct ListNode* prev;
    LTDataType data;
} LTNode;

为便于修改数据类型，建议统一使用 typedef 定义。

1.1 双链表节点创建

LTNode* BuyListNode(LTDataType x) {
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL) {
        perror("malloc failed");
        return NULL;
    }
    newnode->data = x;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

1.2 双链表初始化

LTNode* LTInit() {
    LTNode* phead = BuyListNode(-1);
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

通常会在主函数创建一个指针接收初始化指针。prev 和 next 都指向自己形成循环，也就是一个哨兵位，间接规避了链表为空的情况，可以直接 PushBack 节点。

1.3 双链表销毁

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;
}

head 是哨兵位需要开始时被访问，所以从 phead->next 开始。先保存下一个节点的指针，然后释放当前移动指针指向的节点，再把保存过的节点赋值给移动指针实现遍历节点，最后再释放哨兵位 head。

1.4 双链表打印

void LTPrint(LTNode* phead) {
    assert(phead);
    printf("<= head =>");
    LTNode* cur = phead->next;
    while (cur != phead) {
        printf(" %d =>", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

要根据双链表的特性来，双链表有哨兵位，所以打印要从哨兵位的下一个节点开始打印，直到遇到的节点的 next 指针指向哨兵位。

1.5 双链表检查是否为空

int LTEmpty(LTNode* phead) {
    assert(phead);
    return phead->next == phead ? 0 : 1;
}

为了方便在增删查改中避免链表为空的情况，且多处需使用到，所以特别写一个判空函数。因为是循环链表，所以指向自己表明链表只有一个哨兵位，则返回 0，否则返回 1。

1.6 双链表尾插

void LTPushBack(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    phead->prev->next = newnode;
    newnode->prev = phead->prev;
    newnode->next = phead;
    phead->prev = newnode;
}

由于是带头循环，所以每个节点都有逻辑线连接着。通常先修改两个节点间的链接，再修改循环的链接。

1.7 双链表头插

void LTPushFront(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    newnode->next = phead->next;
    phead->next->prev = newnode;
    phead->next = newnode;
    newnode->prev = phead;
}

无论是什么情况下，都要注意连接的顺序是否会影响到其他步骤的正常赋值，所以头插就需要先链接 newnode 的 next 指针，即通常先链接后面的节点。

1.8 双链表尾删

void LTPopBack(LTNode* phead) {
    assert(phead);
    assert(!LTEmpty(phead));
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;
    tailPrev->next = phead;
    phead->prev = tailPrev;
    free(tail);
    tail = NULL;
}

首先遇到删除就要注意是不是空链表，存不存在节点来删除，然后要分别存储最后一个节点和倒数第二个节点，方便进行链接释放的操作。

1.9 双链表头删

void LTPopFront(LTNode* phead) {
    assert(phead);
    assert(!LTEmpty(phead));
    LTNode* first = phead->next;
    phead->next = first->next;
    first->next->prev = phead;
    free(first);
    first = NULL;
}

相同的操作，无论是删除还是销毁，都要记得存储需要释放的节点相关指针，因为需要在删除之后将其连接的节点连接起来。

1.10 双链表查找

LTNode* LTFind(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) {
        if (cur->data == x) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

我们在查找时肯定是查找有效的数据，所以我们查找是从哨兵位后一个节点开始的。查找方法也很简单，遍历整个双链表，看看能否找到相应的数据，找得到就返回对应节点，找不到就返回空。

1.11 双链表在 pos 位置插入 x

void LTInsert(LTNode* pos, LTDataType x) {
    assert(pos);
    LTNode* newnode = BuyListNode(x);
    pos->prev->next = newnode;
    newnode->prev = pos->prev;
    pos->prev = newnode;
    newnode->next = pos;
}

因为双向链表有 prev，就不用在意是 pos 前还是 pos 后插入，这里用的是 pos 前插入。

1.12 双链表在 pos 位置删除 x

void LTErase(LTNode* phead, LTNode* pos) {
    assert(phead);
    assert(!LTEmpty(phead));
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
}

其实和头删尾删的原理是一样的，直接删除，然后将剩余两个断开的节点链接就行了。

2. 顺序表和链表对比

顺序表和链表各有各的好处。

顺序表： 适用于对随机访问性能要求高，元素数量可预估，且不需要频繁进行插入和删除操作的场景。

链表： 适用于需要频繁插入和删除元素，元素数量动态变化，难以预估元素数量的场景。

3. 代码展示

3.1 List.h

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

typedef int LTDataType;
typedef struct ListNode {
    struct ListNode* next;
    struct ListNode* prev;
    LTDataType data;
} LTNode;

LTNode* LTInit();
void LTDestroy(LTNode* phead);
void LTPrint(LTNode* phead);
LTNode* BuyListNode(LTDataType x);
int LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDataType x);
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* phead, LTNode* pos);

3.2 List.c

#define _CRT_SECURE_NO_WARNINGS
#include "List.h"

// 初始化
LTNode* LTInit() {
    LTNode* phead = BuyListNode(-1);
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

// 销毁
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;
}

// 打印
void LTPrint(LTNode* phead) {
    assert(phead);
    printf("<= head =>");
    LTNode* cur = phead->next;
    while (cur != phead) {
        printf(" %d =>", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// 创建节点
LTNode* BuyListNode(LTDataType x) {
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL) {
        perror("malloc failed");
        return NULL;
    }
    newnode->data = x;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

// 判空
int LTEmpty(LTNode* phead) {
    assert(phead);
    return phead->next == phead ? 0 : 1;
}

// 尾插
void LTPushBack(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* tail = phead->prev;
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = phead;
    phead->prev = newnode;
}

// 尾删
void LTPopBack(LTNode* phead) {
    assert(phead);
    assert(!LTEmpty(phead));
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;
    tailPrev->next = phead;
    phead->prev = tailPrev;
    free(tail);
    tail = NULL;
}

// 头插
void LTPushFront(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    newnode->next = phead->next;
    phead->next->prev = newnode;
    phead->next = newnode;
    newnode->prev = phead;
}

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

// 查找
LTNode* LTFind(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) {
        if (cur->data == x) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

// 在 pos 处插入 x
void LTInsert(LTNode* pos, LTDataType x) {
    assert(pos);
    LTNode* newnode = BuyListNode(x);
    pos->prev->next = newnode;
    newnode->prev = pos->prev;
    pos->prev = newnode;
    newnode->next = pos;
}

// 在 pos 处删除 x
void LTErase(LTNode* phead, LTNode* pos) {
    assert(phead);
    assert(!LTEmpty(phead));
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
}