详解C语言中双向循环链表的实现

什么是双向循环链表？

双向循环链表是一种链表类型，与单向链表不同，它的每个节点不仅包含着向后指针next，还有向前指针prev。这种链表类型通常用于需要快速查找、插入、删除元素等操作的场合，例如在数据结构和算法中经常被用到。

双向循环链表的实现步骤

下面我们来一步步实现双向循环链表的数据结构。

1. 定义节点结构

双向循环链表的节点结构需要包含元素的值和向前和向后的指针。定义节点结构体如下：

typedef struct _double_linked_node {
  int value; // 元素的值
  struct _double_linked_node* prev; // 指向前一个节点的指针
  struct _double_linked_node* next; // 指向后一个节点的指针
} double_linked_node;

2. 定义链表结构

链表结构需要包含指向头节点和尾节点的指针以及节点个数信息。定义链表结构体如下：

typedef struct _double_linked_list {
  double_linked_node* head; // 链表头
  double_linked_node* tail; // 链表尾
  int length; // 链表长度
} double_linked_list;

3. 实现节点的插入和删除操作

双向循环链表的插入和删除节点操作需要考虑到链表的头和尾，以及节点的前后指针。下面分别是节点的插入和删除操作。

节点插入操作

void double_linked_list_insert(double_linked_list* list, int value) {
  double_linked_node* new_node = (double_linked_node*)malloc(sizeof(double_linked_node));
  new_node->value = value;

  if (list->length == 0) {
    new_node->prev = new_node;
    new_node->next = new_node;
    list->head = new_node;
    list->tail = new_node;
  } else {
    new_node->prev = list->tail;
    new_node->next = list->head;
    list->tail->next = new_node;
    list->head->prev = new_node;
    list->tail = new_node;
  }

  list->length++;
}

节点删除操作

void double_linked_list_remove(double_linked_list* list, double_linked_node* node) {
  if (list->length == 0) {
    return;
  } else if (list->length == 1) {
    list->head = NULL;
    list->tail = NULL;
  } else {
    if (node == list->head) {
      list->head = list->head->next;
    } else if (node == list->tail) {
      list->tail = list->tail->prev;
    }

    node->prev->next = node->next;
    node->next->prev = node->prev;
  }

  free(node);
  list->length--;
}

4. 实现其他操作

根据需要我们还可以实现以下操作：

• 获取链表长度：遍历整个链表，返回链表长度。
• 查找节点：遍历整个链表，查找指定节点。
• 输出链表：遍历整个链表，以逗号分隔并打印链表中所有的值。

示例说明

示例1：向链表中插入元素

int main() {
  double_linked_list list;
  list.head = NULL;
  list.tail = NULL;
  list.length = 0;

  double_linked_list_insert(&list, 1);
  double_linked_list_insert(&list, 2);
  double_linked_list_insert(&list, 3);
  double_linked_list_insert(&list, 4);

  return 0;
}

在上面的示例中，我们首先创建一个空的双向循环链表，然后分别向链表中插入四个元素。这四个元素会依次插入到链表的尾部，并且链表的头指针和尾指针也会被更新。

示例2：从链表中删除元素

int main() {
  double_linked_list list;
  list.head = NULL;
  list.tail = NULL;
  list.length = 0;

  double_linked_list_insert(&list, 1);
  double_linked_list_insert(&list, 2);
  double_linked_list_insert(&list, 3);

  double_linked_node* node = list.head;
  double_linked_list_remove(&list, node);

  return 0;
}

在上面的示例中，首先创建一个双向循环链表，并向其中插入3个元素。然后我们取出链表的头节点，并删除它。删除之后，链表的头节点会被更新为原来的第二个节点，同时链表长度会减一。