Linux C语言实现双向链表

1. 双向链表介绍

双向链表是一种常用的数据结构，它与单向链表相比，每个节点除了保存下一个节点的指针，还保存了上一个节点的指针，这样可以方便地在链表中进行前插和后插操作。

在C语言中，可以使用结构体来表示链表的节点，每个节点包含一个数据域和两个指针域，分别指向前一个节点和后一个节点。

2. 双向链表的基本操作

2.1 初始化链表

在使用链表之前，通常需要先初始化链表，将链表头节点的指针置为空。

typedef struct Node {
  int data;
  struct Node* prev;
  struct Node* next;
} Node;
// 初始化链表
void initList(Node** head) {
  *head = NULL;
}

在初始化链表之后，可以使用指针head来操作链表。

2.2 在链表头插入节点

要在链表的头部插入一个新节点，需要先创建一个新节点，然后将其指针域指向原来的第一个节点，再将原来的第一个节点的prev指针域指向新节点。最后，将链表头节点的指针指向新节点。

// 在链表头插入节点
void insertAtHead(Node** head, int data) {
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = data;
  newNode->prev = NULL;
  newNode->next = *head;
  
  if (*head != NULL) {
    (*head)->prev = newNode;
  }
  
  *head = newNode;
}

2.3 在链表尾插入节点

在链表的尾部插入一个新节点的操作相对简单，只需要找到链表中的最后一个节点，将其指针域指向新节点，再将新节点的prev指针域指向原来的最后一个节点即可。

// 在链表尾插入节点
void insertAtTail(Node** head, int data) {
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = data;
  newNode->prev = NULL;
  newNode->next = NULL;
  
  if (*head == NULL) {
    *head = newNode;
  } else {
    Node* temp = *head;
    while (temp->next != NULL) {
      temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
  }
}

2.4 删除链表中的节点

要删除链表中的一个节点，需要先找到要删除的节点，然后将其前后两个节点的指针域连接起来。最后，释放要删除的节点所占用的内存。

// 删除链表中的节点
void deleteNode(Node** head, int data) {
  Node* temp = *head;
  
  while (temp != NULL) {
    if (temp->data == data) {
      if (temp->prev != NULL) {
        temp->prev->next = temp->next;
      } else {
        *head = temp->next;
      }
      if (temp->next != NULL) {
        temp->next->prev = temp->prev;
      }
      free(temp);
      break;
    }
    temp = temp->next;
  }
}

3. 测试双向链表

为了验证双向链表的功能是否正确，可以编写一个简单的测试程序来进行测试。

int main() {
  Node* list;
  initList(&list);
  
  // 在链表头插入节点
  insertAtHead(&list, 1);
  insertAtHead(&list, 2);
  
  // 在链表尾插入节点
  insertAtTail(&list, 3);
  
  // 删除链表中的节点
  deleteNode(&list, 2);
  
  // 打印链表中的元素
  Node* temp = list;
  while (temp != NULL) {
    printf("%d ", temp->data);
    temp = temp->next;
  }
  
  return 0;
}

运行以上代码，输出结果为：1 3。

4. 总结

通过本文的介绍和代码示例，我们了解了如何使用C语言实现双向链表，并对双向链表的基本操作进行了详细的讲解和演示。双向链表作为一种常见的数据结构，能够方便地进行节点的插入和删除操作，适用于各种场景。