编写Java代码实现双向链表 ?
参考答案:
下面是一个简单的Java实现双向链表的例子。这个实现定义了一个双向链表节点类Node
和一个双向链表类DoublyLinkedList
。
public class DoublyLinkedList {
Node head; // 链表头节点
// 链表节点类
static class Node {
int data;
Node next;
Node prev;
Node(int d) {
data = d;
next = null;
prev = null;
}
}
// 在链表末尾添加新节点
public void append(int new_data) {
Node new_node = new Node(new_data);
Node last = head;
// 如果链表为空,新节点就是头节点
if (head == null) {
head = new_node;
return;
}
// 否则,找到最后一个节点
while (last.next != null) {
last = last.next;
}
// 添加新节点到链表末尾
last.next = new_node;
new_node.prev = last;
}
// 打印链表
public void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
// 在链表头部添加新节点
public void prepend(int new_data) {
Node new_node = new Node(new_data);
new_node.next = head;
// 如果链表不为空,更新头节点的prev指针
if (head != null) {
head.prev = new_node;
}
head = new_node;
}
// 在给定位置插入新节点
public void insertAfter(Node prev_node, int new_data) {
if (prev_node == null) {
System.out.println("给定的前一个节点不能为null");
return;
}
Node new_node = new Node(new_data);
new_node.next = prev_node.next;
new_node.prev = prev_node;
// 如果prev_node是最后一个节点,新节点就是新的最后一个节点
if (prev_node.next != null) {
prev_node.next.prev = new_node;
}
prev_node.next = new_node;
}
// 删除节点
public void deleteNode(Node del) {
if (del == null) {
System.out.println("要删除的节点不能为null");
return;
}
// 如果要删除的节点是头节点
if (del == head) {
head = del.next;
// 如果链表不为空,更新新头节点的prev指针
if (head != null) {
head.prev = null;
}
return;
}
// 如果要删除的节点不是最后一个节点
if (del.next != null) {
del.next.prev = del.prev;
}
// 如果要删除的节点不是头节点
if (del.prev != null) {
del.prev.next = del.next;
}
}
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList();
dll.append(5);
dll.append(10);
dll.append(15);
dll.printList(); // 输出: 5 10 15
dll.prepend(20);
dll.printList(); // 输出: 20 5 10 15
dll.insertAfter(dll.head, 25);
dll.printList(); // 输出: 20 25 5 10 15
dll.deleteNode(dll.head.next);
dll.printList(); // 输出: 20 5 10 15
}
}
这个双向链表实现提供了append
(在链表末尾添加新节点)、prepend
(在链表头部添加新节点)、insertAfter
(在给定节点后插入新节点)和deleteNode
(删除给定节点)等方法。printList