手搓双向链表代码全解析：从零开始实现双向链表数据结构（附注释与实战步骤）

胡志明t

一、简介和特点

双向链表（Double Linked List）是一种基础的数据结构，它由多个节点组成，每个节点包含数据域、指向下一个节点的指针（next）和指向前一个节点的指针（last）。与单向链表相比，双向链表允许从任意节点向前或向后遍历，因此在需要频繁插入、删除或双向遍历的场景中具有优势。本文将通过您手写的双向链表代码，详细解析其实现原理与操作步骤。

二、与其他数据结构的优点对比

1. 对比单向链表：单向链表只能单向遍历，删除或插入时需要先找到前驱节点，而双向链表通过last指针可直接定位前驱，操作效率更高。

2. 对比数组：双向链表插入和删除元素时不需要移动大量数据，时间复杂度为O(1)（找到位置后），而数组在插入或删除中间元素时需要移动后续元素，时间复杂度为O(n)。

3. 灵活性：动态分配内存，无需提前确定容量，适合数据量动态变化的场景。

三、实现步骤

1. 定义节点结构：包含数据（data）、指向下一个节点（next）和指向前一个节点（last）的指针。

2. 初始化链表头节点：head指向头节点，头节点不存储数据，仅作为链表起始标志。

3. 添加节点（add方法）：从head开始遍历至末尾，创建新节点并插入到末尾，连接next和last指针。

4. 插入节点（insert方法）：根据索引idx找到目标位置，调整前后节点的指针关系，插入新节点。

5. 删除节点（delnode方法）：根据索引找到目标节点，断开其前后节点的指针连接，释放内存。

6. 修改节点数据（change方法）：定位到索引对应的节点，直接修改data值。

7. 选择节点数据（select方法）：根据索引返回对应节点的数据。

四、代码及注释

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. // 节点结构定义
   
5. struct node {
   
6.     int data = 0;          // 数据域（默认初始化为0）
   
7.     node* next = nullptr;  // 指向下一个节点的指针
   
8.     node* last = nullptr;  // 指向前一个节点的指针
   
9. };
   
10. 
    
11. class linklist {
    
12.     node* head = new node;  // 头节点，不存储数据，仅作为链表入口
    
13. 
    
14. public:
    
15.     // 1. 添加节点到链表末尾
    
16.     void add(int data) {
    
17.         node* tmp = head;   // 临时指针从head开始遍历
    
18.         while (tmp->next!= nullptr) {  // 遍历至末尾节点
    
19.             tmp = tmp->next;
    
20.         }
    
21.         node* datanode = new node;  // 创建新节点
    
22.         datanode->data = data;     // 赋值数据
    
23.         tmp->next = datanode;      // 末尾节点的next指向新节点
    
24.         datanode->last = tmp;      // 新节点的last指向末尾节点
    
25.     }
    
26. 
    
27.     // 2. 在指定索引位置插入节点
    
28.     void insert(int data, int idx) {
    
29.         node* tmp = head;         // 从head开始遍历
    
30.         for (int i = 0; i < idx; i++) {  // 定位到目标位置的前一个节点
    
31.             tmp = tmp->next;
    
32.         }
    
33.         node* datanode = new node;  // 创建新节点
    
34.         datanode->data = data;
    
35.         // 调整指针关系：
    
36.         // (1) 新节点的last指向当前节点的前一个节点
    
37.         datanode->last = tmp->next->last;  
    
38.         // (2) 新节点的next指向当前节点的下一个节点
    
39.         datanode->next = tmp->next;  
    
40.         // (3) 当前节点的next指向新节点
    
41.         tmp->next = datanode;  
    
42.         // (4) 原下一个节点的last指向新节点
    
43.         datanode->next->last = datanode;
    
44.     }
    
45. 
    
46.     // 3. 删除指定索引的节点
    
47.     void delnode(int idx) {
    
48.         node* tmp = head;         // 从head开始遍历
    
49.         for (int i = 0; i < idx; i++) {  // 定位到目标节点
    
50.             tmp = tmp->next;
    
51.         }
    
52.         // 跳过目标节点，连接前后节点：
    
53.         // (1) 当前节点的next跳过目标节点
    
54.         tmp->next = tmp->next->next;  
    
55.         // (2) 原下一个节点的last指向当前节点
    
56.         tmp->next->last = tmp;  
    
57.     }
    
58. 
    
59.     // 4. 修改指定索引节点的数据
    
60.     void change(int data, int idx) {
    
61.         node* tmp = head;         // 遍历到目标节点
    
62.         for (int i = 0; i <= idx; i++) {  
    
63.             // 注意：i <= idx（包括索引位置）
    
64.             tmp = tmp->next;
    
65.         }
    
66.         tmp->data = data;         // 直接赋值
    
67.     }
    
68. 
    
69.     // 5. 获取指定索引节点的数据
    
70.     int select(int idx) {
    
71.         node* tmp = head;         // 遍历到目标节点
    
72.         for (int i = 0; i <= idx; i++) {
    
73.             tmp = tmp->next;
    
74.         }
    
75.         return tmp->data;         // 返回数据
    
76.     }
    
77. };

复制代码

五、总结

通过手搓双向链表代码，我们深入理解了其核心原理：利用双向指针实现灵活的数据操作，尤其在插入和删除时避免了单向链表需要查找前驱节点的开销。对于新手来说，掌握双向链表的设计思路有助于加深对指针操作和数据结构逻辑的理解。在实际开发中，双向链表常用于需要双向遍历的场景（如LRU缓存淘汰算法、双向队列等）。持续练习基础数据结构的实现，将为算法设计与优化打下坚实基础。

链接：双向链表