数据结构学习笔记：双向链表详解

一、双向链表基础

结构定义
节点结构：每个节点包含三个部分：
data：存储数据。
next：指向下一个节点的指针。
prev：指向前一个节点的指针。
结构体定义（C语言示例）：

      typedef struct node {
     data_t data;
     struct node *next; // 指向后继节点
     struct node *prev; // 指向前驱节点
 } node_t;
 

双向链表的特点
双向遍历：既可以从头节点向尾节点遍历（通过next指针），也可以从尾节点向头节点遍历（通过prev指针）。
插入/删除操作更灵活：由于每个节点都有前驱和后继指针，插入和删除时可以更方便地调整指针，减少遍历次数。

二、双向链表的基本操作

创建链表
创建头节点：
分配内存给头节点。
初始化prev和next指针为NULL。
代码示例：

   node_t *creat_doublist(void) {
     node_t *head = (node_t *)malloc(sizeof(node_t));
     if (head == NULL) {
         // 处理内存分配失败的情况
         return NULL;
     }
     head->prev = NULL;
     head->next = NULL;
     return head;
 }
 

插入操作
头插法：
步骤：
创建新节点p_new，填充数据。
调整指针：

  p_new->next = phead->next;
  p_new->prev = phead;
  phead->next = p_new;

如果原头节点的next不为NULL，则原头节点的next的prev指向p_new。
代码示例：

       void doublisr_insert_head(node_t *phead, data_t data) 
   {
       node_t *p_new = (node_t *)malloc(sizeof(node_t));
       if (p_new == NULL) 
       {
           // 处理内存分配失败的情况
           return;
       }
       p_new->data = data;
       p_new->next = phead->next;
       p_new->prev = phead;
       phead->next = p_new;
       if (p_new->next != NULL) 
       {
           p_new->next->prev = p_new;
       }
   }

尾插法：
步骤：
创建新节点p_new，填充数据。
找到尾节点（通过遍历链表，直到next为NULL）。
调整指针：
尾节点的next指向p_new。
p_new的prev指向尾节点。
p_new的next指向NULL。
代码示例：

        void doublisr_insert_tail(node_t *phead, data_t data) {
       node_t *p_new = (node_t *)malloc(sizeof(node_t));
       if (p_new == NULL) {
           // 处理内存分配失败的情况
           return;
       }
       p_new->data = data;
       p_new->next = NULL;
       node_t *p = phead;
       while (p->next != NULL) {
           p = p->next;
       }
       p->next = p_new;
       p_new->prev = p;
   }
   

查找操作
查找某个值：
从头节点开始遍历链表，比较每个节点的data与目标值，如果相等则返回该节点的指针，否则返回NULL。
代码示例：

      node_t *doublisr_find_key(node_t *phead, data_t data) {
     node_t *p = phead->next; // 从第一个数据节点开始
     while (p != NULL) {
         if (p->data == data) {
             return p;
         }
         p = p->next;
     }
     return NULL; // 未找到
 }
 

更新操作
更新某个值：
先通过查找操作找到目标节点，然后修改其data。
代码示例：

      node_t *doublisr_update_key(node_t *phead, data_t old_data,
       data_t new_data)
 {
     node_t *p = doublisr_find_key(phead, old_data);
     if (p != NULL) 
     {
         p->data = new_data;
         return p;
     }
     return NULL; // 未找到
 }
 

统计长度
统计链表长度：
从头节点的下一个节点开始遍历，直到next为NULL，统计节点个数。
代码示例：

    int length(node_t *phead) {
     int len = 0;
     node_t *p = phead->next; // 从第一个数据节点开始
     while (p != NULL) {
         len++;
         p = p->next;
     }
     return len;
 }

三、双向链表的其他操作

逆序打印
从尾节点开始，通过prev指针向前遍历，直到遇到头节点，打印每个节点的data。
代码示例：

      void print_reverse(node_t *phead) {
     node_t *p = phead;
     while (p->next != NULL) {
         p = p->next; // 找到尾节点
     }
     while (p != phead) {
         printf("%d ", p->data);
         p = p->prev; // 通过prev指针向前遍历
     }
     printf("n");
 }
 

删除操作（图中未详细展示，但属于基本操作）
删除某个节点：
找到要删除的节点p_del。
调整其前驱节点的next指针和后继节点的prev指针：
p_del->prev->next = p_del->next;
p_del->next->prev = p_del->prev;
释放p_del的内存。

四、双向链表的应用场景

需要频繁双向遍历的场景：如浏览器的前进/后退功能，双向链表可以方便地向前或向后移动。
需要频繁在头部或尾部插入/删除的场景：如队列、栈的实现，双向链表可以在O(1)时间内完成头尾操作。
需要快速查找前驱或后继的场景：如某些缓存算法（LRU），需要快速调整节点的位置。

五、总结

双向链表通过增加prev指针，实现了双向遍历和更灵活的插入/删除操作，但同时也增加了内存开销（每个节点需要额外存储一个指针）。在实际应用中，需要根据具体需求选择合适的数据结构。