双向链表(Doubly Linked List)是一种链表的数据结构,在每个节点中除了指向下一个节点的指针之外,还有一个指向前一个节点的指针。这样的结构使得双向链表可以在两个方向上遍历。
以下是使用 Java 代码实现的双向链表的基本结构:
public class Node {
public int data;
public Node prev;
public Node next;
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
public class DoublyLinkedList {
public Node head;
public Node tail;
public DoublyLinkedList() {
this.head = null;
this.tail = null;
}
public void insertAtHead(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
}
public void insertAtTail(int data) {
Node newNode = new Node(data);
if (tail == null) {
head = newNode;
tail = newNode;
} else {
newNode.prev = tail;
tail.next = newNode;
tail = newNode;
}
}
public void delete(int data) {
if (head == null) {
return;
}
Node currentNode = head;
while (currentNode != null) {
if (currentNode.data == data) {
if (currentNode == head) {
head = head.next;
if (head != null) {
head.prev = null;
}
} else if (currentNode == tail) {
tail = tail.prev;
if (tail != null) {
tail.next = null;
}
} else {
currentNode.prev.next = currentNode.next;
currentNode.next.prev = currentNode.prev;
}
return;
}
currentNode = currentNode.next;
}
}
public void printForward() {
Node currentNode = head;
while (currentNode != null) {
System.out.print(currentNode.data + " ");
currentNode = currentNode.next;
}
System.out.println();
}
public void printBackward() {
Node currentNode = tail;
while (currentNode != null) {
System.out.print(currentNode.data + " ");
currentNode = currentNode.prev;
}
System.out.println();
}
}
通过以上代码,我们可以创建一个双向链表的实例,并进行插入、删除和打印等操作。例如:
public class Main {
public static void main(String[] args) {
DoublyLinkedList dList = new DoublyLinkedList();
dList.insertAtHead(3);
dList.insertAtHead(5);
dList.insertAtTail(7);
dList.printForward(); // Output: 5 3 7
dList.printBackward(); // Output: 7 3 5
dList.delete(3);
dList.printForward(); // Output: 5 7
}
}
在上述示例中,我们向双向链表中插入了三个元素,然后分别打印了正向和逆向的链表内容。接下来,我们删除了一个节点,并再次打印了链表内容。