数据结构（Doubly Linked List双向链表）

1.前言：

在计算机科学的广袤领域中，数据结构犹如构建高楼大厦的基石，它们为高效地组织、存储和处理数据提供了坚实的框架。而双向链表作为一种重要且功能强大的数据结构，在众多算法与程序设计场景中都展现出了独特的魅力与价值。

当我们踏入数据结构的学习之旅，单向链表已经向我们展示了一种灵活的链式存储方式，它通过节点间的单向链接，能够动态地管理数据元素。然而，双向链表在此基础上更进一步，为每个节点赋予了前后两个指针，这看似简单的改进，却带来了诸多卓越的特性。

双向链表的双向指针使得数据的遍历变得更加便捷与灵活。无论是从前往后还是从后往前，我们都能轻松地在链表中穿梭，如同在一条双向的信息高速公路上自由驰骋。这种特性在许多实际应用中具有显著优势，例如在文本编辑器中处理文本行的前后移动、浏览器的历史记录浏览（既可以向前查看之前访问的页面，也可以向后返回后续页面）以及某些图形界面库中对组件列表的双向操作等场景下，双向链表都能够高效地应对数据的双向访问需求。

与数组相比，双向链表在数据的插入和删除操作上表现出了更高的灵活性。在数组中，插入或删除一个元素往往需要移动大量后续元素，时间复杂度较高。而双向链表只需调整相关节点的指针，便可轻松完成这些操作，并且不会对链表的其他部分造成大规模的数据移动干扰，从而在频繁进行数据动态更新的场景中展现出卓越的性能。

此外，双向链表的结构也为一些复杂算法的实现提供了有力支持。例如，在某些高级排序算法或图数据结构的特定实现中，双向链表能够以其独特的方式协助数据的组织与处理，使得算法的逻辑更加清晰、高效。

在本章节中，我们将深入探索双向链表的奥秘。从它的基本概念与结构定义开始，逐步剖析其各种操作的实现细节，包括节点的创建、插入、删除、查找以及链表的遍历等核心功能。我们还将通过实际的代码示例与详细的注释，帮助读者透彻理解双向链表在内存中的存储方式以及操作过程中的指针变化逻辑。同时，为了让读者更好地领略双向链表在实际应用中的强大之处，我们会引入一些具体的案例分析，展示如何运用双向链表解决实际问题，并探讨在不同场景下双向链表与其他数据结构的优劣对比与选择策略。

无论你是数据结构与算法的初学者，渴望深入了解链式存储结构的精髓；还是有一定编程经验的开发者，希望进一步拓展自己在数据处理方面的技术能力，本章节关于双向链表的学习都将为你开启一扇通向高效数据管理与处理的新大门。让我们一同踏上这段充满挑战与惊喜的双向链表学习之旅，领略数据结构世界的奇妙与深邃。

2.双向链表的实现

2.1双向链表的基本概念

双向链表是一种链式存储的数据结构，它由一系列节点组成。每个节点除了存储数据元素本身之外，还包含两个指针：一个指向前一个节点（prev 指针），另一个指向后一个节点（next 指针）。这种双向的指针结构使得双向链表在数据的遍历、插入和删除操作上具有很高的灵活性。与单向链表相比，双向链表可以从任意节点开始向前或向后遍历整个链表，而单向链表只能沿着一个方向进行遍历。

2.2、双向链表的实现步骤框架

（一）节点类的定义：

成员变量：

• public int val：用于存储节点所代表的值，这个值可以是任何你想要在链表中存放的整型数据，比如整数类型的元素值等，它是节点的关键数据部分。
• public ListNode prev：是一个指向当前节点前一个节点的指针（引用），用于构建双向链表中向后的关联，使得可以从当前节点回溯到前面的节点，这也是双向链表区别于单向链表的重要特性体现。
• ListNode next：同样是一个指针（引用），不过它指向当前节点的下一个节点，用于构建链表向前的连接顺序，通过这个指针可以依次访问后续节点。

• 链表头和尾指针声明：
  head和last这两个变量都是ListNode类型，它们分别用于指向整个双向链表的头节点和尾节点。在双向链表的操作过程中，通过head可以从链表开头进行正向遍历（利用每个节点的next指针），而通过last可以从链表末尾进行反向遍历（利用每个节点的prev指针）。这两个指针方便了对整个链表的访问和操作，比如插入新节点到头部或者尾部、删除头部或者尾部节点等常见操作都依赖于它们准确地指向相应位置。

（二）双向链表实现的方法：

//头插法  

       public void addFirst(int data)；

//尾插法    

       public void addLast(int data)；

//任意位置插入,第一个数据节点为0号下标  

       public void addIndex(int index,int data)；

//查找是否包含关键字key是否在双链表当中    

       public boolean contains(int key)；

//删除第一次出现关键字为key的节点  

       public void remove(int key)；

//删除所有值为key的节点    

       public void removeAllKey(int key)；

 //得到单链表的长度    

       public int size()；  

 //清空链表

       public void clear()；    

 // 打印链表

       public void display() ；

（三）不同的方法实现：

1.头插法  

1.1分析：

1. 创建新节点：
   在方法内部，首先通过 ListNode node = new ListNode(data); 语句创建了一个新的 ListNode 类型的节点对象 node，并将传入的 data 值赋给这个新节点，用于存储相应的数据。
2. 链表为空的情况处理（初始化链表）：
   通过 if(head == null) 条件判断来检查链表是否为空。如果链表为空（即 head 指针为 null ，意味着还没有节点存在），那么将新创建的节点 node 同时赋值给链表的头指针 head 和尾指针 last（虽然 last 在这段代码中前面未完整定义，但从逻辑上推测是用于指向链表尾节点的变量），也就是让这个新节点成为链表唯一的节点，既是头节点也是尾节点。
3. 链表非空的情况处理（插入新节点到头部）：
   当链表不为空时（即 head 不为 null ），执行 else 分支中的代码：
   • 通过 node.next = head; 语句，将新节点 node 的 next 指针指向当前的头节点（原来的第一个节点），这样就把新节点和原来的链表头部连接起来了，新节点将成为新的头节点，而原来的头节点会成为新节点后面的节点。
   • 接着 head.prev = node; 语句，将原来头节点的 prev（前一个节点）指针指向新插入的节点 node，建立双向链表中反向的连接关系，使得从原来的头节点也能回溯到新插入的这个头节点。
   • 最后通过 head = node; 将链表的头指针 head 指向新插入的节点 node，完成新节点作为链表头部节点的更新操作，此时新节点正式成为链表新的头节点。

1.3静态演示：

顺序：     1 ---->2

                3----->4

2.尾插法

2.1分析：

1. 创建新节点：
   代码首先通过 ListNode node = new ListNode(data); 语句创建了一个新的 ListNode 类型的节点对象 node，把传入的 data 值赋给这个新节点，以此来承载要插入到链表尾部的数据信息。
2. 链表为空的情况处理（初始化链表）：
   利用 if(head == null) 条件判断链表是否为空。若链表为空（也就是 head 指针为 null，意味着链表中还不存在任何节点），那么将新创建的节点 node 同时赋值给链表的头指针 head 和尾指针 last。如此一来，这个新节点就成为了链表的第一个节点，同时担当头节点和尾节点的角色，完成了链表的初始化操作。
3. 链表非空的情况处理（插入新节点到尾部）：
   当链表不为空时（即 head 不为 null），执行 else 分支里的代码：
   • 通过 last.next = node; 语句，将当前链表尾节点（由 last 指向）的 next 指针指向新创建的节点 node，从而把新节点连接到链表的末尾，使其成为链表最后一个节点的后续节点。
   • 接着执行 node.prev = last; 语句，将新节点 node 的 prev（前一个节点）指针指向当前的尾节点（也就是 last 所指向的节点），这样就在双向链表中建立了反向的连接关系，确保从新的尾节点能够回溯到原来的尾节点。
   • 最后通过 last = last.next; 语句，将链表的尾指针 last 更新为指向新插入的这个节点 node（因为 last.next 此时就是新插入的节点），完成了将新节点设置为链表新尾节点的操作，使得链表的尾节点得到了正确的更新，新节点正式成为链表的最后一个节点。

2.3静态演示：

顺序：     1 ---->2

                3----->4

3 任意位置插入,第一个数据节点为0号下标

3.1 分析：

1. addIndex 方法逻辑分析

   • 参数合法性校验：
     首先通过 if(index <0 || index > size()) 条件判断来检查传入的索引 index 是否合法。如果索引小于 0 或者大于链表当前的长度（通过 size() 方法获取，虽然此处 size() 方法的具体实现未给出，但能推测出其作用是返回链表的节点个数），说明指定的插入位置不合理，那么直接使用 return 结束方法执行，不进行后续插入操作，以此避免出现数组越界之类的错误情况。
   • 边界情况处理（头部插入）：
     接着通过 if(index == 0) 判断是否要在链表头部插入节点。如果索引为 0，意味着需要将节点插入到链表的最开头，此时直接调用已有的 addFirst(data) 方法（前面应该已经定义了该方法用于向链表头部插入节点）来完成插入操作，然后使用 return 结束当前 addIndex 方法的执行，因为头部插入的逻辑已经在 addFirst 方法中实现好了。
   • 边界情况处理（尾部插入）：
     再通过 if(index == size()) 判断是否要在链表的末尾插入节点。如果索引等于链表的长度，那就相当于要在链表的最后添加节点，此时调用 addLast(data) 方法（同样前面应该已定义该方法用于向链表尾部插入节点）来完成相应的插入操作，随后使用 return 结束 addIndex 方法，因为尾插的逻辑在 addLast 方法中已经处理好了。
   • 一般情况插入（中间位置插入）：
     当要插入的索引既不是 0 也不是链表长度时，说明是要在链表中间的某个位置插入节点。首先通过 ListNode node = new ListNode(data); 创建一个新的 ListNode 类型的节点 node，用来承载要插入的数据 data。然后调用 findIndex(index) 方法获取到链表中指定索引位置对应的当前节点 cur。
     接下来进行插入节点的指针操作：
     • 通过 node.next = cur; 将新节点 node 的 next 指针指向当前找到的节点 cur，使得新节点与要插入位置的当前节点建立了正向的连接关系，后续遍历链表时能按照正确顺序访问到节点。
     • 通过 cur.prev.next = node; 将当前节点 cur 的前一个节点（即 cur.prev）的 next 指针指向新节点 node，这样就把新节点插入到了当前节点 cur 的前面，从链表的前向顺序角度完成了连接。
     • 通过 node.prev = cur.prev; 将新节点 node 的 prev 指针指向当前节点 cur 的前一个节点，建立了反向的连接关系，保证从新节点能回溯到前面的节点，符合双向链表的结构特点。
     • 最后通过 cur.prev = node; 将当前节点 cur 的 prev 指针指向新节点 node，进一步完善反向连接，至此新节点在链表中间位置的插入操作就完成了，新节点成功插入到了指定索引对应的位置。

2. findIndex 方法逻辑分析
   这个私有方法用于在链表中查找指定索引位置对应的节点。它首先将一个临时节点指针 cur 初始化为指向链表的头节点（通过 ListNode cur = head; 语句实现），然后通过一个循环，只要索引 index 不为 0，就不断地将 cur 指针向后移动（通过 cur = cur.next; 语句实现，即让 cur 指向当前节点的下一个节点），同时每次循环将 index 减 1。当循环结束时（也就是 index 变为 0 时），此时 cur 指针所指向的节点就是链表中指定索引位置对应的节点，最后将该节点返回，供 addIndex 方法用于后续的插入操作。

3.2 注意事项：

• 空链表的操作：

  • 在所有需要访问链表的操作中（如 addLast、remove、removeAllKey 等），必须考虑链表为空的情况，否则可能导致空指针异常。

• 链表长度不足时的处理：

  • 在方法 addIndex 中，访问指定索引时确保索引合法。
  • 例如：addIndex 方法中，if(index < 0 || index > size()) 检查了索引边界，但建议在边界不合法时，抛出异常（如 IllegalArgumentException），而不是仅仅返回，这样更符合实际开发中的错误处理习惯。

• 边界节点处理：

  • 删除头节点时，需要更新 head，并处理 head 的 prev。
  • 删除尾节点时，需要更新 last，并处理 last 的 next。
  • 删除中间节点时，需要正确更新前后节点的引用。

4.查找是否包含关键字key是否在双链表当中

4.1 分析

1. 初始化遍历指针：
   方法首先通过 ListNode cur = head; 语句，将一个临时的节点指针 cur 初始化为指向链表的头节点。这个指针将用于遍历整个链表，以查找是否存在值为 key 的节点。
2. 链表遍历及比较判断：
   接着进入一个 while 循环，循环的条件是 cur!= null，只要当前指针 cur 所指向的节点不为 null，就意味着还没有遍历完整个链表，需要继续进行查找操作。在循环体内部，通过 if(cur.val == key) 条件判断当前节点（由 cur 指向）存储的值（通过 cur.val 访问，这里推测 ListNode 类中有一个名为 val 的成员变量用于存储节点的数据）是否与传入的 key 值相等。如果相等，说明找到了目标值，此时直接使用 return true; 返回 true，表示链表中包含该值，结束方法的执行。如果当前节点的值与 key 不相等，那么通过 cur = cur.next; 语句将指针 cur 移动到下一个节点，继续下一轮的比较判断，如此循环，直至遍历完整个链表或者找到目标值为止。
3. 遍历结束返回结果：
   当 while 循环结束时（也就是 cur 指针指向 null，表示已经遍历完整个链表都没有找到值为 key 的节点），使用 return false; 返回 false，表明链表中不存在与 key 值相等的节点。

5.删除第一次出现关键字为key的节点  

5.1 分析

1. 初始化遍历指针：
   通过 ListNode cur = head; 语句，将一个临时的节点指针 cur 初始化为指向链表的头节点，后续将利用这个指针来遍历整个链表，查找值为 key 的节点。
2. 链表遍历及删除操作判断：
   进入 while 循环，只要 cur 指针所指向的节点不为 null，就持续遍历链表进行查找。在循环体中，通过 if(cur.val == key) 条件判断当前节点（由 cur 指向）存储的值是否等于要删除的 key 值。
   • 删除头节点情况：
     若 cur 指向的节点就是头节点（即 cur == head 条件成立），执行以下操作：
     • 首先通过 head = head.next; 将链表的头指针 head 指向当前头节点的下一个节点，实现把头节点从链表中移除的第一步操作。
     • 接着通过 if (head!=null) 条件判断新的头节点是否为空。若不为空，说明链表中还有其他节点，此时需要通过 head.prev = null; 将新头节点的 prev（前一个节点）指针置为 null，因为它现在已经成为了链表的第一个节点，之前的头节点已被删除，这样就正确更新了新头节点的前驱指针，完成头节点删除后的链表结构调整。
   • 删除中间或尾节点情况：
     若 cur 指向的节点不是头节点（即执行 else 分支），执行以下操作：
     • 通过 cur.prev.next = cur.next; 语句，将当前节点 cur 的前一个节点（由 cur.prev 指向）的 next 指针指向当前节点 cur 的下一个节点（由 cur.next 指向），从而跳过当前节点 cur，在链表的正向连接上实现了将该节点移除的操作。
     • 然后通过 if (cur.next == null) 条件判断当前节点 cur 是否为尾节点。如果 cur.next 为 null，意味着当前节点就是尾节点，此时需要通过 last = last.prev; 将链表的尾指针 last 更新为指向当前尾节点的前一个节点，因为当前尾节点即将被删除，这样就完成了尾节点删除后的链表尾指针更新操作。
     • 如果当前节点 cur 不是尾节点（即 cur.next!= null），则通过 cur.next.prev = cur.prev; 语句，将当前节点 cur 的下一个节点的 prev 指针指向当前节点 cur 的前一个节点，在链表的反向连接上完成了节点删除后的结构调整，保证链表双向连接的正确性。
   • 无论哪种情况，只要找到要删除的节点并完成相应操作后，就通过 return 结束 remove 方法的执行，因为已经完成了一个值为 key 的节点删除操作。
   • 若当前节点的值不等于 key ，则通过 cur = cur.next; 将指针 cur 移动到下一个节点，继续下一轮的查找和判断，直至遍历完整个链表为止。

6.删除所有值为key的节点

此和5.删除第一次出现关键字为key的节点的处处不大，因此我们只讲差别：

6.1分析差别：

1. 代码功能和对链表结构改变的影响不同

• <5>只删除一个值为 key 的节点：
  执行完代码后，链表中最多只会少一个节点，也就是第一个被查找到的那个值为 key 的节点会被移除，链表的其他部分保持不变，后续的节点顺序和连接关系依旧按照原有的结构（除了被删除节点相关的指针调整外）。例如，若链表原本是 1 -> 2 -> 2 -> 3 ，要删除值为 2 的节点，执行完代码后可能变为 1 -> 2 -> 3 （只删除了第一个 2 对应的节点）。
• <6>删除所有值为 key 的节点：
  执行完代码后，链表中所有值为 key 的节点都会被移除，链表结构会发生相应的较大改变，节点数量以及连接关系都会根据原链表中值为 key 的节点分布情况重新调整。比如，若链表原本是 1 -> 2 -> 2 -> 3 ，要删除值为 2 的节点，执行完代码后就变为 1 -> 3 ，所有值为 2 的节点都被成功删除了。

2. 代码在处理逻辑上的复杂程度及潜在问题关注点不同

• <5>只删除一个值为 key 的节点：
  相对来说逻辑较为简单直接，重点在于正确判断要删除的节点位置（头、中、尾）并进行准确的指针调整操作，保证删除一个节点后链表结构依然正确即可。主要潜在问题多集中在指针操作的异常处理上，比如要确保链表结构本身是完整的，在修改指针时不会出现空指针异常等情况。
• <6>删除所有值为 key 的节点：
  除了要保证每次删除节点时的指针操作正确外，还需要妥善处理好循环继续遍历的逻辑，避免出现遗漏查找或者重复操作等问题。而且由于可能会连续删除多个节点，对链表整体结构改变较大，更需要注意在多次删除操作过程中保证链表结构的完整性以及避免出现指针异常等错误情况，代码逻辑的复杂程度和对各种边界情况的把控要求相对更高一些。

7.得到单链表的长度

7.1分析

1. 初始化遍历指针与长度计数变量：
   首先通过 ListNode cur = head; 语句，将一个临时的节点指针 cur 初始化为指向链表的头节点，后续会利用这个指针来遍历整个链表。同时，定义了一个整型变量 len 并初始化为 0，这个变量将用于记录链表中节点的数量，每遍历到一个节点，len 的值就会相应地增加 1。
2. 链表遍历及长度计数：
   接着进入 while 循环，循环的条件是 cur!= null，只要当前指针 cur 所指向的节点不为 null，就意味着还没有遍历完整个链表，需要继续进行节点计数操作。在循环体内部，每次循环都会执行 len++; 语句，使得表示长度的变量 len 的值加 1，代表已经遍历到了一个新的节点。然后通过 cur = cur.next; 语句将指针 cur 移动到下一个节点，继续下一轮的遍历和计数，如此循环，直至遍历完整个链表为止。
3. 返回链表长度：
   当 while 循环结束时（也就是 cur 指针指向 null，表示已经遍历完整个链表），使用 return len; 将记录的链表长度 len 返回，这样调用该方法的地方就能获取到当前链表中节点的总个数了。

8.清空链表

8.1分析

1. 初始化遍历指针并准备临时指针：
   首先通过 ListNode cur = head; 语句，将一个临时的节点指针 cur 初始化为指向链表的头节点，后续会利用这个指针来遍历整个链表，依次处理每一个节点。同时在循环内部，定义了另一个临时节点指针 Ncur，通过 ListNode Ncur = cur.next; 语句将其初始化为指向当前节点 cur 的下一个节点，目的是在对当前节点 cur 进行相关操作断开其连接后，还能通过 Ncur 指针获取到下一个需要处理的节点，保证遍历能够持续进行下去。
2. 逐个节点处理及断开连接：
   在 while 循环中（循环条件是 cur!= null，意味着只要还有节点未处理完就继续循环），针对当前节点 cur 进行如下操作：
   • 通过 cur.prev = null; 语句，将当前节点 cur 的前一个节点指针置为 null，断开当前节点与前面节点在双向链表中的反向连接关系（如果是双向链表的话，从这里能推测出是双向链表相关操作，因为有 prev 属性）。
   • 通过 cur.next = null; 语句，将当前节点 cur 的下一个节点指针置为 null，断开当前节点与后面节点在双向链表中的正向连接关系，经过这两步操作，当前节点 cur 就完全从链表结构中脱离出来了，相当于释放了这个节点（虽然在 Java 中真正的内存回收由垃圾回收机制来处理，但这样断开连接的操作使得该节点不再参与链表的逻辑结构了）。
   • 然后通过 cur = Ncur; 语句，将指针 cur 更新为指向之前保存好的下一个节点（也就是 Ncur 所指向的节点），准备处理下一个节点，如此循环，对链表中的每一个节点都重复上述断开连接的操作，直至遍历完整个链表。
3. 重置链表头指针和尾指针：
   当 while 循环结束，意味着链表中的所有节点都已经被处理并从链表结构中断开连接了，此时通过 head = last = null; 语句，将链表的头指针 head 和尾指针 last 都置为 null，从整体上表明链表现在已经是空链表了，完成了清空链表的全部操作。

9.打印链表

9.1分析

1. 初始化遍历指针：
   通过 ListNode cur = head; 语句，将一个临时的节点指针 cur 初始化为指向链表的头节点。后续会利用这个指针来遍历整个链表，按顺序访问每一个节点。
2. 链表遍历及数据输出：
   接着进入 while 循环，循环条件为 cur!= null，只要当前指针 cur 所指向的节点不为 null，就意味着链表还未遍历完，需要继续操作。在循环体内部，使用 System.out.print(cur.val + " "); 语句，将当前节点（由 cur 指向）存储的数据（通过 cur.val 来访问，推测 ListNode 类中有名为 val 的成员变量用于存放节点的数据）输出到控制台，并且每个数据后面添加一个空格作为间隔，使输出的内容格式相对规整，更便于查看和区分不同节点的数据。输出当前节点数据后，通过 cur = cur.next; 语句将指针 cur 移动到下一个节点，以便在下一轮循环中输出下一个节点的数据，如此循环往复，直至遍历完整个链表。
3. 换行操作：
   当 while 循环结束，也就是已经遍历并输出了链表中所有节点的数据后，使用 System.out.println(); 语句进行换行操作。这样做的好处是，在多次调用 display() 方法输出不同链表或者同一链表不同状态的数据时，每次的输出内容会各自独占一行，避免不同次的输出内容在控制台显示时相互混淆，使得输出结果更加清晰易读。

3.全部代码展示

1.接口：

public interface MyList {//头插法public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点public void remove(int key);//删除所有值为key的节点public void removeAllKey(int key);//得到单链表的长度public int size();//清空链表public void clear();// 打印链表public void display();
}

2.java代码实现：

public class MyIList implements MyList{static  class ListNode {public int val;public ListNode prev;ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;public void addFirst(int data) {ListNode node = new ListNode(data);if(head == null){head = last = node;}else{node.next = head;head.prev = node;head = node;}}@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);if(head == null){head = last = node;}else{last.next = node;node.prev = last;last = last.next;}}@Overridepublic void addIndex(int index, int data) {if(index <0 || index > size()){return;}if(index == 0){addFirst(data);return;}if(index == size()){addLast(data);return;}ListNode node = new ListNode(data);ListNode cur = findIndex(index);node.next = cur;cur.prev.next = node;node.prev =cur.prev ;cur.prev = node;}private ListNode findIndex(int index){ListNode cur = head;while (index !=0){cur = cur.next;index--;}return cur;}@Overridepublic void remove(int key) {ListNode  cur = head;while (cur !=null){if(cur.val == key) {if (cur == head) {head = head.next;if (head!=null) {head.prev = null;}} else {cur.prev.next = cur.next;if (cur.next == null) {last = last.prev;} else {cur.next.prev = cur.prev;}}return;}else {cur = cur.next;}}}@Overridepublic void removeAllKey(int key) {ListNode cur = head;while (cur !=null){if(cur.val == key) {if (cur == head) {head = head.next;if (head!=null) {head.prev = null;}} else {cur.prev.next = cur.next;if (cur.next == null) {last = last.prev;} else {cur.next.prev = cur.prev;}}cur = cur.next;}else {cur = cur.next;}}}@Overridepublic void clear() {ListNode cur = head;while (cur != null){ListNode Ncur = cur.next;cur.prev = null;cur.next = null;cur = Ncur;}head = last = null;}@Overridepublic int size() {ListNode cur = head;int len = 0;while (cur !=null){len++;cur  = cur.next;}return len;}@Overridepublic boolean contains(int key) {ListNode cur = head;while (cur !=null){if(cur.val == key){return true;}cur  = cur.next;}return false;}@Overridepublic void display() {ListNode cur = head;while (cur !=null){System.out.print(cur.val + " ");cur  = cur.next;}System.out.println();}
}

4.结语：

在数据结构的浩瀚星空中，双向链表无疑是一颗璀璨的明星。通过对双向链表的深入学习与探索，我们犹如踏上了一段奇妙的编程之旅，领略到了它独特的魅力与强大的功能。

从最初对双向链表基本概念的理解，到亲手构建节点类、实现链表类中的各种操作方法，如插入、删除和遍历等，我们逐步揭开了双向链表神秘的面纱。每一个步骤都像是在精心雕琢一件艺术品，从定义节点的前驱与后继指针，到巧妙地处理在不同位置进行数据元素添加或移除时指针的变更，无不体现着数据结构设计的精妙与严谨。

双向链表的优势在诸多实际应用场景中得以彰显。它在浏览器历史记录管理里游刃有余，让用户能够轻松地在过往页面间穿梭回溯；于文本编辑器的撤销重做功能中发挥关键作用，精准地记录操作步骤的前后顺序，使得编辑过程更加灵活可控；在操作系统任务调度队列的构建上也大显身手，高效地协调任务的排队与执行顺序，保障系统的稳定运行。这些应用实例仅仅是双向链表广泛用途的冰山一角，它在更多复杂的软件系统和算法设计中都有着不可或缺的地位。

掌握双向链表不仅丰富了我们的数据结构知识宝库，更为我们解决实际编程问题提供了一把得力的钥匙。它教会我们在面对不同的数据处理需求时，如何权衡各种数据结构的利弊，选择最为合适的工具来打造高效、健壮的程序。无论是应对大规模数据的动态管理，还是处理具有复杂逻辑关系的数据序列，双向链表都能以其独特的双向遍历和灵活的节点操作能力，为我们开辟出一条优化与创新之路。

然而，数据结构的学习之路永无止境。双向链表只是众多数据结构中的一员，在它之外，还有诸如树、图等更为复杂和高深的数据结构等待我们去探索。但双向链表无疑为我们奠定了坚实的基础，它所培养的逻辑思维和编程技巧将伴随我们在后续的数据结构与算法学习旅程中不断前行，助力我们攻克一个又一个编程难关，攀登更高的技术巅峰。希望大家能够将在双向链表学习过程中所积累的知识与经验融会贯通，在未来的编程世界里创造出更多精彩的可能。