C语言中带头双向循环链表基本操作的实现详解

什么是带头双向循环链表

带头双向循环链表是一种常见的数据结构，在实际开发中也经常会用到。带头双向循环链表可以看作是一种特殊的链表，相对于普通链表，它具有以下特点：

1. 它有一个头结点，头结点不存储数据，它的作用是指向链表中的第一个节点。

2. 每个节点都有一个前驱指针prev和一个后继指针next，用于指向前一个节点和后一个节点。

3. 最后一个节点的后继指针指向头结点，第一个节点的前驱指针也指向头结点，从而形成一个循环链表。

带头双向循环链表的结构如下：

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode, *DLinkList;

typedef struct DNodeWithHead {
    int length; //存储链表的长度
    struct DNode *header;
} DList, *DLinkedList;

基本操作及其实现

1. 初始化链表

初始化带头双向循环链表，需要为链表分配内存空间，并且将头结点的prev和next都指向自身。

DLinkedList init() {
    DLinkedList list = (DLinkedList)malloc(sizeof(DList));
    list->length = 0;
    list->header = (DNode *)malloc(sizeof(DNode));
    list->header->prev = list->header;
    list->header->next = list->header;

    return list;
}

2. 插入节点

向带头双向循环链表中插入节点，需要先判断插入的位置是否合法，然后才能进行插入操作。这里以在指定位置p后插入一个新节点为例。

int insert(DLinkedList list, int p, int data) {
    if (p < 1 || p > list->length + 1) {
        return 0; //插入位置不合法
    }

    DNode *node = (DNode *)malloc(sizeof(DNode));
    node->data = data;

    DNode *pre = list->header; //pre指向头节点
    while (p-- > 1) {
        pre = pre->next; //pre指向要插入位置的前一个节点
    }

    node->next = pre->next; //新节点的后继指向插入位置的后一个节点
    pre->next->prev = node; //插入位置的后一个节点的前驱指向新节点
    pre->next = node; //插入位置的前一个节点的后继指向新节点
    node->prev = pre; //新节点的前驱指向插入位置的前一个节点

    list->length++; //链表长度加一
    return 1;
}

3. 删除节点

在带头双向循环链表中删除节点，需要先判断删除的位置是否合法，然后才能进行删除操作。这里以删除指定位置p上的节点为例。

int deleteNode(DLinkedList list, int p) {
    if (p < 1 || p > list->length) {
        return 0; //删除位置不合法
    }

    DNode *pre = list->header; //pre指向头节点
    while (p-- > 1) {
        pre = pre->next; //pre指向要删除的节点的前一个节点
    }

    DNode *del = pre->next; //del指向要删除的节点
    pre->next = del->next; //删除节点的前驱指向删除节点的后继
    del->next->prev = pre; //删除节点的后继指向删除节点的前驱
    free(del); //释放要删除的节点的内存

    list->length--; //链表长度减一
    return 1;
}

示例

下面给出两个例子来说明带头双向循环链表的使用。

示例1：循环队列

带头双向循环链表可以用来实现循环队列。在循环队列中，队列的队尾指针需要满足环形的特性，因此我们可以借助带头双向循环链表的结构来实现循环队列。以下是循环队列的代码实现：

typedef struct {
    DLinkedList list; //带头双向循环链表
    int rear; //队尾指针
} Queue, *QueuePtr;

QueuePtr initQueue() {
    QueuePtr queue = (QueuePtr)malloc(sizeof(Queue));
    queue->list = init();
    queue->rear = 0;
    return queue;
}

int isEmpty(QueuePtr queue) {
    return queue->list->length == 0;
}

int enqueue(QueuePtr queue, int data) {
    if (insert(queue->list, queue->list->length + 1, data)) {
        queue->rear = (queue->rear + 1) % queue->list->length; //更新队尾指针
        return 1;
    }

    return 0;
}

int dequeue(QueuePtr queue) {
    if (isEmpty(queue)) {
        return 0;
    }

    int data = queue->list->header->next->data;
    deleteNode(queue->list, 1);
    queue->rear--; //更新队尾指针
    return data;
}

示例2：LRU缓存

LRU（Least Recently Used）是一种缓存淘汰算法，其原理是根据数据最后一次被访问的时间来决定何时从缓存中淘汰数据。带头双向循环链表可以用来实现LRU缓存，我们可以将链表的头部作为最近访问的数据，尾部作为最久未访问的数据。以下是LRU缓存的代码实现：

typedef struct {
    DLinkedList list; //带头双向循环链表
    int capacity; //缓存大小
} LRUCache, *LRUCachePtr;

LRUCachePtr initCache(int capacity) {
    LRUCachePtr cache = (LRUCachePtr)malloc(sizeof(LRUCache));
    cache->list = init();
    cache->capacity = capacity;
    return cache;
}

int get(LRUCachePtr cache, int key) {
    DNode *node = cache->list->header->next;
    while (node != cache->list->header) {
        if (node->data == key) {
            deleteNode(cache->list, getPos(cache->list, key));
            insert(cache->list, 1, key); //将访问的数据移动到链表头部
            return key;
        }

        node = node->next;
    }

    return -1; //如果缓存中不存在该数据，则返回-1
}

int put(LRUCachePtr cache, int key) {
    int pos = getPos(cache->list, key);
    if (pos > 0) { //如果缓存中已经存在该数据，则将其移动到链表头部
        deleteNode(cache->list, pos);
        insert(cache->list, 1, key);
        return key;
    }

    if (cache->list->length >= cache->capacity) { //如果缓存已满，则淘汰最久未被访问的数据
        deleteNode(cache->list, cache->list->length);
    }

    insert(cache->list, 1, key);
    return key;
}

总结

带头双向循环链表是一种常用的数据结构，在实际开发中也经常会用到。本文详细讲解了带头双向循环链表的基本操作及其实现，并通过两个示例简单介绍了带头双向循环链表的应用。希望本文能够对大家理解带头双向循环链表的使用和原理有所帮助。