C语言双向链表的表示与实现实例详解

一、概述

双向链表（doubly linked list）是一种链式存储结构，与单向链表类似，但每个节点不仅包含了一个指向下一个节点的指针，还包含了一个指向前一个节点的指针。这样可以方便地在链表的前后进行遍历和操作。

本篇攻略将详细讲解C语言双向链表的表示与实现。包括链表的结构定义、操作实现和两个示例说明。

二、结构定义

在C语言中定义一个双向链表节点的结构体如下：

typedef struct node {
  int data;
  struct node *prev; // 上一个节点指针
  struct node *next; // 下一个节点指针
} Node;

其中，data代表节点的数据部分，prev和next分别代表上一个节点和下一个节点的指针。

同时，为了方便操作链表，需要定义一个指向链表头部的指针和链表长度的变量：

typedef struct {
  Node *head; // 链表头部指针
  int length; // 链表长度
} LinkedList;

其中，head为指向链表头部的指针，length为链表长度。

三、操作实现

3.1 初始化操作

初始化一个双向链表需要分配内存，这里定义一个initLinkedList函数：

LinkedList *initLinkedList() {
  LinkedList *list = (LinkedList *) malloc(sizeof(LinkedList));
  list->head = (Node *) malloc(sizeof(Node));
  list->head->prev = NULL;
  list->head->next = NULL;
  list->length = 0;
  return list;
}

其中，malloc函数分配了两段内存，一段存放LinkedList结构体，一段存放节点的数据内容。

3.2 插入操作

在一个双向链表中插入一个节点需要指定插入位置和后继节点。这里定义一个insertNode函数，实现将新节点插入到指定位置。

void insertNode(LinkedList *list, int index, int data) {
  if (index < 0 || index > list->length) {
    printf("Invalid index\n");
    return;
  }
  Node *newNode = (Node *) malloc(sizeof(Node));
  newNode->data = data;
  Node *p = list->head;
  for (int i = 0; i < index; i++) {
    p = p->next;
  }
  newNode->prev = p;
  newNode->next = p->next;
  if (p->next != NULL) {
    p->next->prev = newNode;
  }
  p->next = newNode;
  list->length++;
}

以上代码中，如果输入的index超出了链表长度或小于0，那么会输出Invalid index。否则创建一个新的节点，将其插入在指定位置，同时更新链表长度。

3.3 删除操作

在一个双向链表中删除一个节点需要指定删除位置。这里定义一个deleteNode函数，实现删除指定位置的节点。

void deleteNode(LinkedList *list, int index) {
  if (index < 0 || index >= list->length) {
    printf("Invalid index\n");
    return;
  }
  Node *p = list->head;
  for (int i = 0; i < index; i++) {
    p = p->next;
  }
  p->prev->next = p->next;
  if (p->next != NULL) {
    p->next->prev = p->prev;
  }
  free(p);
  list->length--;
}

以上代码中，如果输入的index超出了链表长度或小于0，那么会输出Invalid index。否则找到需要删除的节点，使其前后两个节点互相指向，然后释放该节点的内存，同时更新链表长度。

四、示例说明

4.1 实例一

在这个示例中，创建了一个包含4个节点的链表，并依次插入了两个节点，最后删除了第三个节点。

int main() {
  LinkedList *list = initLinkedList();

  insertNode(list, 0, 1);
  insertNode(list, 1, 2);
  insertNode(list, 2, 3);
  insertNode(list, 3, 4);
  printf("Before delete, the length of the linkedlist is: %d\n", list->length);

  deleteNode(list, 2);
  printf("After delete, the length of the linkedlist is: %d\n", list->length);

  return 0;
}

运行结果：

Before delete, the length of the linkedlist is: 4
After delete, the length of the linkedlist is: 3

4.2 实例二

在这个示例中，创建了一个包含10个节点的链表，并使用循环插入节点，最后打印出所有节点的数据。

int main() {
  LinkedList *list = initLinkedList();

  for (int i = 1; i <= 10; i++) {
    insertNode(list, i - 1, i);
  }

  Node *p = list->head->next;
  while (p != NULL) {
    printf("%d ", p->data);
    p = p->next;
  }
  printf("\n");

  return 0;
}

运行结果：

1 2 3 4 5 6 7 8 9 10

五、总结

本篇攻略详细讲解了C语言双向链表的表示与实现，包括结构定义、操作实现和两个示例说明。这种数据结构可以应用于需要快速查找、插入和删除节点的场景，具有一定的实用价值。