Java链表实现详解：从单向链表到双向链表及应用29

链表是一种常用的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表的内存空间可以不连续，因此在插入和删除元素时具有更高的效率。Java没有内置的链表类，但我们可以通过自定义类来实现各种类型的链表。本文将详细讲解Java中单向链表和双向链表的实现，并探讨其应用场景。

一、单向链表

单向链表是最简单的链表类型，每个节点只包含数据和指向下一个节点的指针。其结构简单，实现容易，但只能单向遍历。

首先，我们需要定义一个`Node`类来表示链表的节点：```java
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
```

接下来，我们定义一个`SinglyLinkedList`类来表示单向链表：```java
class SinglyLinkedList {
Node head;
SinglyLinkedList() {
head = null;
}
// 添加节点到链表尾部
public void append(int new_data) {
Node new_node = new Node(new_data);
if (head == null) {
head = new_node;
return;
}
Node last = head;
while ( != null) {
last = ;
}
= new_node;
}
// 打印链表
public void printList() {
Node tnode = head;
while (tnode != null) {
( + " ");
tnode = ;
}
}
// 在指定位置插入节点
public void insertAt(int index, int new_data){
Node newNode = new Node(new_data);
if(index == 0){
= head;
head = newNode;
return;
}
Node current = head;
int count = 0;
while(count < index -1 && current != null){
current = ;
count++;
}
if(current == null){
("Index out of bounds");
return;
}
= ;
= newNode;
}
// 删除指定位置的节点
public void deleteAt(int index){
if(head == null){
return;
}
if(index == 0){
head = ;
return;
}
Node current = head;
int count = 0;
while(count < index -1 && current != null){
current = ;
count++;
}
if(current == null || == null){
("Index out of bounds");
return;
}
= ;
}
}
```

这段代码实现了单向链表的基本操作，包括添加节点、打印链表、在指定位置插入节点和删除指定位置的节点。你可以根据需要添加其他操作，例如查找节点、反转链表等。

二、双向链表

双向链表比单向链表更复杂，每个节点包含数据、指向下一个节点的指针和指向前一个节点的指针。它允许双向遍历，提高了某些操作的效率。```java
class NodeDouble {
int data;
NodeDouble prev;
NodeDouble next;
NodeDouble(int d) {
data = d;
prev = null;
next = null;
}
}
class DoublyLinkedList {
NodeDouble head;
DoublyLinkedList() {
head = null;
}
// 添加节点到链表尾部
void append(int new_data) {
NodeDouble new_node = new NodeDouble(new_data);
if (head == null) {
head = new_node;
return;
}
NodeDouble last = head;
while ( != null)
last = ;
= new_node;
= last;
}
// 打印链表
void printList() {
NodeDouble node = head;
("Traversal in forward direction");
while (node != null) {
( + " ");
node = ;
}
}

// 在指定位置插入节点
public void insertAt(int index, int new_data){
NodeDouble newNode = new NodeDouble(new_data);
if(index == 0){
= head;
if(head != null){
= newNode;
}
head = newNode;
return;
}
NodeDouble current = head;
int count = 0;
while(count < index -1 && current != null){
current = ;
count++;
}
if(current == null){
("Index out of bounds");
return;
}
= ;
= current;
if( != null){
= newNode;
}
= newNode;
}
// 删除指定位置的节点
public void deleteAt(int index){
if(head == null){
return;
}
if(index == 0){
head = ;
if(head != null){
= null;
}
return;
}
NodeDouble current = head;
int count = 0;
while(count < index && current != null){
current = ;
count++;
}
if(current == null){
("Index out of bounds");
return;
}
if( != null){
= ;
}
if( != null){
= ;
}
}
}
```