java实现双向链表（java双向链表类）

## Java实现双向链表### 简介链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表的节点不一定是连续存储的，这使得链表在插入和删除元素方面具有更高的效率。双向链表是链表的一种变体，它的每个节点除了指向下一个节点的指针外，还包含指向前一个节点的指针。这种结构使得双向链表可以方便地进行双向遍历，并且在某些操作（例如删除指定节点）时更加高效。### 一、节点结构```java public class Node {public T data; // 节点数据public Node prev; // 指向前一个节点public Node next; // 指向下一个节点public Node(T data) {this.data = data;} } ```每个节点包含三个部分：

`data`: 存储节点的数据。

`prev`: 指向前一个节点的指针。

`next`: 指向下一个节点的指针。### 二、双向链表类```java public class DoublyLinkedList {private Node head; // 头节点private Node tail; // 尾节点private int size; // 链表长度// 构造函数public DoublyLinkedList() {head = null;tail = null;size = 0;}// ... 其他方法 ... } ```双向链表类包含以下成员变量：

`head`: 指向链表头节点的指针。

`tail`: 指向链表尾节点的指针。

`size`: 记录链表中节点的数量。### 三、基本操作#### 3.1 插入操作

在头部插入节点:

```java public void addFirst(T data) {Node newNode = new Node<>(data);if (isEmpty()) {head = newNode;tail = newNode;} else {newNode.next = head;head.prev = newNode;head = newNode;}size++; } ```

在尾部插入节点:

```java public void addLast(T data) {Node newNode = new Node<>(data);if (isEmpty()) {head = newNode;tail = newNode;} else {tail.next = newNode;newNode.prev = tail;tail = newNode;}size++; } ```

在指定位置插入节点:

```java public void add(int index, T data) {if (index < 0 || index > size) {throw new IndexOutOfBoundsException();}if (index == 0) {addFirst(data);} else if (index == size) {addLast(data);} else {Node current = head;for (int i = 0; i < index - 1; i++) {current = current.next;}Node newNode = new Node<>(data);newNode.next = current.next;newNode.prev = current;current.next.prev = newNode;current.next = newNode;size++;} } ```#### 3.2 删除操作

删除头部节点:

```java public T removeFirst() {if (isEmpty()) {throw new NoSuchElementException();}Node temp = head;if (head == tail) { // 只有一个节点head = null;tail = null;} else {head = head.next;head.prev = null;}size--;return temp.data; } ```

删除尾部节点:

```java public T removeLast() {if (isEmpty()) {throw new NoSuchElementException();}Node temp = tail;if (head == tail) { // 只有一个节点head = null;tail = null;} else {tail = tail.prev;tail.next = null;}size--;return temp.data; } ```

删除指定位置节点:

```java public T remove(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException();}if (index == 0) {return removeFirst();} else if (index == size - 1) {return removeLast();} else {Node current = head;for (int i = 0; i < index; i++) {current = current.next;}current.prev.next = current.next;current.next.prev = current.prev;size--;return current.data;} } ```#### 3.3 其他操作

获取链表长度:

```java public int size() {return size; } ```

判断链表是否为空:

```java public boolean isEmpty() {return size == 0; } ```

遍历链表:

```java public void printList() {Node current = head;while (current != null) {System.out.print(current.data + " ");current = current.next;}System.out.println(); } ```### 四、总结本文详细介绍了Java中如何实现双向链表，包括节点结构、链表类的定义以及基本的插入、删除和遍历操作。双向链表相较于单向链表，能够更方便地进行双向遍历，并且在某些操作上效率更高，但同时也需要更多的内存空间来存储指向前一个节点的指针。

Java实现双向链表

简介链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表的节点不一定是连续存储的，这使得链表在插入和删除元素方面具有更高的效率。双向链表是链表的一种变体，它的每个节点除了指向下一个节点的指针外，还包含指向前一个节点的指针。这种结构使得双向链表可以方便地进行双向遍历，并且在某些操作（例如删除指定节点）时更加高效。

一、节点结构```java public class Node {public T data; // 节点数据public Node prev; // 指向前一个节点public Node next; // 指向下一个节点public Node(T data) {this.data = data;} } ```每个节点包含三个部分：* `data`: 存储节点的数据。 * `prev`: 指向前一个节点的指针。 * `next`: 指向下一个节点的指针。

二、双向链表类```java public class DoublyLinkedList {private Node head; // 头节点private Node tail; // 尾节点private int size; // 链表长度// 构造函数public DoublyLinkedList() {head = null;tail = null;size = 0;}// ... 其他方法 ... } ```双向链表类包含以下成员变量：* `head`: 指向链表头节点的指针。 * `tail`: 指向链表尾节点的指针。 * `size`: 记录链表中节点的数量。

三、基本操作

3.1 插入操作* **在头部插入节点:**```java public void addFirst(T data) {Node newNode = new Node<>(data);if (isEmpty()) {head = newNode;tail = newNode;} else {newNode.next = head;head.prev = newNode;head = newNode;}size++; } ```* **在尾部插入节点:**```java public void addLast(T data) {Node newNode = new Node<>(data);if (isEmpty()) {head = newNode;tail = newNode;} else {tail.next = newNode;newNode.prev = tail;tail = newNode;}size++; } ```* **在指定位置插入节点:**```java public void add(int index, T data) {if (index < 0 || index > size) {throw new IndexOutOfBoundsException();}if (index == 0) {addFirst(data);} else if (index == size) {addLast(data);} else {Node current = head;for (int i = 0; i < index - 1; i++) {current = current.next;}Node newNode = new Node<>(data);newNode.next = current.next;newNode.prev = current;current.next.prev = newNode;current.next = newNode;size++;} } ```

3.2 删除操作* **删除头部节点:**```java public T removeFirst() {if (isEmpty()) {throw new NoSuchElementException();}Node temp = head;if (head == tail) { // 只有一个节点head = null;tail = null;} else {head = head.next;head.prev = null;}size--;return temp.data; } ```* **删除尾部节点:**```java public T removeLast() {if (isEmpty()) {throw new NoSuchElementException();}Node temp = tail;if (head == tail) { // 只有一个节点head = null;tail = null;} else {tail = tail.prev;tail.next = null;}size--;return temp.data; } ```* **删除指定位置节点:**```java public T remove(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException();}if (index == 0) {return removeFirst();} else if (index == size - 1) {return removeLast();} else {Node current = head;for (int i = 0; i < index; i++) {current = current.next;}current.prev.next = current.next;current.next.prev = current.prev;size--;return current.data;} } ```

3.3 其他操作* **获取链表长度:**```java public int size() {return size; } ```* **判断链表是否为空:**```java public boolean isEmpty() {return size == 0; } ```* **遍历链表:**```java public void printList() {Node current = head;while (current != null) {System.out.print(current.data + " ");current = current.next;}System.out.println(); } ```

四、总结本文详细介绍了Java中如何实现双向链表，包括节点结构、链表类的定义以及基本的插入、删除和遍历操作。双向链表相较于单向链表，能够更方便地进行双向遍历，并且在某些操作上效率更高，但同时也需要更多的内存空间来存储指向前一个节点的指针。