java双向链表（java双向链表继承单向链表代码）

# 简介双向链表是一种常见的数据结构，它允许在每个节点中存储两个指针，一个指向链表的前一个节点（称为前驱），另一个指向链表的下一个节点（称为后继）。与单向链表相比，双向链表提供了更多的操作灵活性，特别是在需要频繁地进行向前和向后的遍历时。本文将详细介绍如何在Java中实现双向链表，并讨论其基本操作。# 双向链表的基本概念## 节点设计双向链表中的每个节点包含三个部分： 1. 数据域：用于存储实际的数据。 2. 前驱指针（prev）：指向当前节点的前一个节点。 3. 后继指针（next）：指向当前节点的后一个节点。```java class Node {int data;Node prev;Node next;public Node(int data) {this.data = data;this.prev = null;this.next = null;} } ```## 头尾节点为了方便管理双向链表，通常会使用头尾节点（也称作哨兵节点）： -

头节点

：不存储数据，仅作为链表的起点。 -

尾节点

：同样不存储数据，仅作为链表的终点。```java class DoublyLinkedList {private Node head;private Node tail;public DoublyLinkedList() {head = new Node(0); // 创建一个不存储数据的头节点tail = new Node(0); // 创建一个不存储数据的尾节点head.next = tail; // 初始时，头节点的next指向尾节点tail.prev = head; // 初始时，尾节点的prev指向头节点} } ```# 双向链表的基本操作## 插入节点### 在指定位置插入节点在双向链表中插入一个新节点需要更新四个指针： 1. 新节点的`prev`指向前一个节点。 2. 新节点的`next`指向后一个节点。 3. 前一个节点的`next`指向新节点。 4. 后一个节点的`prev`指回新节点。```java public void insert(int index, int data) {if (index < 0 || index > size()) {throw new IndexOutOfBoundsException("Invalid index");}Node newNode = new Node(data);Node current = head;for (int i = 0; i < index; i++) {current = current.next;}Node prevNode = current.prev;newNode.prev = prevNode;newNode.next = current;prevNode.next = newNode;current.prev = newNode; } ```### 在头部或尾部插入节点在头部插入节点时，只需调整头节点的`next`指针和新节点的`prev`指针。在尾部插入节点时，则需调整尾节点的`prev`指针和新节点的`next`指针。```java public void addFirst(int data) {Node newNode = new Node(data);Node oldHead = head.next;head.next = newNode;newNode.prev = head;newNode.next = oldHead;oldHead.prev = newNode; }public void addLast(int data) {Node newNode = new Node(data);Node oldTail = tail.prev;oldTail.next = newNode;newNode.prev = oldTail;newNode.next = tail;tail.prev = newNode; } ```## 删除节点删除节点时，需要更新被删除节点前后节点的指针，以确保链表的连续性。```java public void remove(int index) {if (index < 0 || index >= size()) {throw new IndexOutOfBoundsException("Invalid index");}Node current = head;for (int i = 0; i <= index; i++) {current = current.next;}Node prevNode = current.prev;Node nextNode = current.next;prevNode.next = nextNode;nextNode.prev = prevNode;current.prev = null;current.next = null; } ```## 获取节点获取节点可以通过遍历链表找到目标节点并返回其数据。```java public int get(int index) {if (index < 0 || index >= size()) {throw new IndexOutOfBoundsException("Invalid index");}Node current = head;for (int i = 0; i <= index; i++) {current = current.next;}return current.data; } ```## 遍历双向链表双向链表的遍历可以从前到后或从后到前进行。```java public void traverseForward() {Node current = head.next;while (current != tail) {System.out.print(current.data + " ");current = current.next;}System.out.println(); }public void traverseBackward() {Node current = tail.prev;while (current != head) {System.out.print(current.data + " ");current = current.prev;}System.out.println(); } ```# 总结双向链表作为一种重要的数据结构，在许多应用场景中都有着广泛的应用，如缓存系统、文件系统等。通过合理的设计和实现，我们可以充分利用双向链表的优势，提高程序的效率和性能。希望本文能帮助读者更好地理解和掌握双向链表的相关知识。

简介双向链表是一种常见的数据结构，它允许在每个节点中存储两个指针，一个指向链表的前一个节点（称为前驱），另一个指向链表的下一个节点（称为后继）。与单向链表相比，双向链表提供了更多的操作灵活性，特别是在需要频繁地进行向前和向后的遍历时。本文将详细介绍如何在Java中实现双向链表，并讨论其基本操作。

双向链表的基本概念

节点设计双向链表中的每个节点包含三个部分： 1. 数据域：用于存储实际的数据。 2. 前驱指针（prev）：指向当前节点的前一个节点。 3. 后继指针（next）：指向当前节点的后一个节点。```java class Node {int data;Node prev;Node next;public Node(int data) {this.data = data;this.prev = null;this.next = null;} } ```

头尾节点为了方便管理双向链表，通常会使用头尾节点（也称作哨兵节点）： - **头节点**：不存储数据，仅作为链表的起点。 - **尾节点**：同样不存储数据，仅作为链表的终点。```java class DoublyLinkedList {private Node head;private Node tail;public DoublyLinkedList() {head = new Node(0); // 创建一个不存储数据的头节点tail = new Node(0); // 创建一个不存储数据的尾节点head.next = tail; // 初始时，头节点的next指向尾节点tail.prev = head; // 初始时，尾节点的prev指向头节点} } ```

双向链表的基本操作

插入节点

在指定位置插入节点在双向链表中插入一个新节点需要更新四个指针： 1. 新节点的`prev`指向前一个节点。 2. 新节点的`next`指向后一个节点。 3. 前一个节点的`next`指向新节点。 4. 后一个节点的`prev`指回新节点。```java public void insert(int index, int data) {if (index < 0 || index > size()) {throw new IndexOutOfBoundsException("Invalid index");}Node newNode = new Node(data);Node current = head;for (int i = 0; i < index; i++) {current = current.next;}Node prevNode = current.prev;newNode.prev = prevNode;newNode.next = current;prevNode.next = newNode;current.prev = newNode; } ```

在头部或尾部插入节点在头部插入节点时，只需调整头节点的`next`指针和新节点的`prev`指针。在尾部插入节点时，则需调整尾节点的`prev`指针和新节点的`next`指针。```java public void addFirst(int data) {Node newNode = new Node(data);Node oldHead = head.next;head.next = newNode;newNode.prev = head;newNode.next = oldHead;oldHead.prev = newNode; }public void addLast(int data) {Node newNode = new Node(data);Node oldTail = tail.prev;oldTail.next = newNode;newNode.prev = oldTail;newNode.next = tail;tail.prev = newNode; } ```

删除节点删除节点时，需要更新被删除节点前后节点的指针，以确保链表的连续性。```java public void remove(int index) {if (index < 0 || index >= size()) {throw new IndexOutOfBoundsException("Invalid index");}Node current = head;for (int i = 0; i <= index; i++) {current = current.next;}Node prevNode = current.prev;Node nextNode = current.next;prevNode.next = nextNode;nextNode.prev = prevNode;current.prev = null;current.next = null; } ```

获取节点获取节点可以通过遍历链表找到目标节点并返回其数据。```java public int get(int index) {if (index < 0 || index >= size()) {throw new IndexOutOfBoundsException("Invalid index");}Node current = head;for (int i = 0; i <= index; i++) {current = current.next;}return current.data; } ```

遍历双向链表双向链表的遍历可以从前到后或从后到前进行。```java public void traverseForward() {Node current = head.next;while (current != tail) {System.out.print(current.data + " ");current = current.next;}System.out.println(); }public void traverseBackward() {Node current = tail.prev;while (current != head) {System.out.print(current.data + " ");current = current.prev;}System.out.println(); } ```

总结双向链表作为一种重要的数据结构，在许多应用场景中都有着广泛的应用，如缓存系统、文件系统等。通过合理的设计和实现，我们可以充分利用双向链表的优势，提高程序的效率和性能。希望本文能帮助读者更好地理解和掌握双向链表的相关知识。