引言
在计算机科学中，链表是一种基础的数据结构，而双向链表是链表的一种扩展形式。本文将介绍双向链表的基本概念、特点以及在Java中的实现。
双向链表简介
双向链表（Doubly Linked List）是一种链表，每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。这使得双向链表可以从两个方向遍历，相比单向链表更加灵活。
双向链表的节点定义
在Java中，我们可以使用类来定义双向链表的节点。
class Node { int data; Node prev; Node next; public Node(int data) { this.data = data; this.prev = null; this.next = null; } }
双向链表的基本操作
1. 插入操作
在双向链表中，插入操作相对简单，只需要调整相邻节点的指针即可。
class DoublyLinkedList { Node head; // 在双向链表头部插入新节点 public void insertAtFront(int data) { Node newNode = new Node(data); newNode.next = head; if (head != null) { head.prev = newNode; } head = newNode; } // 在双向链表尾部插入新节点 public void insertAtEnd(int data) { Node newNode = new Node(data); Node last = head; while (last.next != null) { last = last.next; } last.next = newNode; newNode.prev = last; } }
2. 删除操作
删除操作同样只需要调整相邻节点的指针。
class DoublyLinkedList { // ...（前面的代码） // 从双向链表中删除指定值的节点 public void delete(int data) { Node current = head; // 找到要删除的节点 while (current != null && current.data != data) { current = current.next; } // 调整相邻节点的指针 if (current != null) { if (current.prev != null) { current.prev.next = current.next; } else { head = current.next; } if (current.next != null) { current.next.prev = current.prev; } } } }
总结
双向链表是链表的一种扩展形式，相比单向链表，它允许从两个方向遍历链表，更加灵活。在实际应用中，根据具体的需求选择合适的链表结构是非常重要的。
