数据结构
请编程完成泛型类DoubleLinkedList（双向链表），DoubleLinkedList的基本功能设计要求：创建双向链表、插入新的结点、删除指定元素结点、查找指定元素结点、修改指定位置结点、遍历循环链表，并写一个全部测试类 public class DoubleLinkedList<T> {private Node<T> head;
private Node<T> tail;
public void insert(T data) {
Node<T> newNode = new Node<>(data);
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
public void delete(T data) {
Node<T> current = head;
while (current != null) {
if (current.data.equals(data)) {
if (current.prev != null) {
current.prev.next = current.next;
} else {
head = current.next;
}
if (current.next != null) {
current.next.prev = current.prev;
} else {
tail = current.prev;
}
return;
}
current = current.next;
}
}
public Node<T> search(T data) {
Node<T> current = head;
while (current != null) {
if (current.data.equals(data)) {
return current;
}
current = current.next;
}
return null;
}
public void modify(int index, T newData) {
Node<T> current = head;
int i = 0;
while (current != null && i < index) {
current = current.next;
i++;
}
if (current != null) {
current.data = newData;
}
}
public void traverse() {
Node<T> current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
}
private static class Node<T> {
private T data;
private Node<T> prev;
private Node<T> next;
public Node(T data) {
this.data = data;
}
}
}
public class DoubleLinkedListTest {
public static void main(String[] args) {
DoubleLinkedList<Integer> list = new DoubleLinkedList<>();
list.insert(1);
list.insert(2);
list.insert(3);
list.insert(4);
list.traverse(); // 输出：1 2 3 4
list.delete(3);
list.traverse(); // 输出：1 2 4
System.out.println(list.search(2).data); // 输出：2
list.modify(1, 5);
list.traverse(); // 输出：1 5 4
}
}
在上面的代码中，我们定义了一个泛型类 DoubleLinkedList ，它实现了双向链表的基本功能。我们可以通过 insert 方法插入新的结点，通过 delete 方法删除指定元素结点，通过 search 方法查找指定元素结点，通过 modify 方法修改指定位置结点，以及通过 traverse 方法遍历循环链表。同时，我们编写了一个测试类 DoubleLinkedListTest 来测试这些功能。 以下是一个基于Java语言的泛型双向链表类DoubleLinkedList的实现，以及一个测试类DoubleLinkedListTest。
java
// 双向链表节点类
class Node<T> {
T data;
Node<T> prev;
Node<T> next;
public Node(T data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
// 泛型双向链表类
public class DoubleLinkedList<T> {
private Node<T> head;
private Node<T> tail;
// 创建空链表
public DoubleLinkedList() {
head = null;
tail = null;
}
// 在链表末尾插入新节点
public void insert(T data) {
Node<T> newNode = new Node<>(data);
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
// 删除指定元素节点
public void delete(T data) {
Node<T> current = head;
while (current != null) {
if (current.data.equals(data)) {
if (current.prev != null) {
current.prev.next = current.next;
} else {
head = current.next;
}
if (current.next != null) {
current.next.prev = current.prev;
} else {
tail = current.prev;
}
return;
}
current = current.next;
}
}
// 查找指定元素节点
public Node<T> search(T data) {
Node<T> current = head;
while (current != null) {
if (current.data.equals(data)) {
return current;
}
current = current.next;
}
return null;
}
// 修改指定位置节点的值
public void modify(int position, T newData) {
Node<T> current = head;
for (int i = 0; i < position; i++) {
if (current == null) {
throw new IndexOutOfBoundsException();
}
current = current.next;
}
if (current != null) {
current.data = newData;
} else {
throw new IndexOutOfBoundsException();
}
}
// 遍历链表并打印元素
public void traverse() {
Node<T> current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
以下是测试类DoubleLinkedListTest：
java
public class DoubleLinkedListTest {
public static void main(String[] args) {
// 创建双向链表
DoubleLinkedList<String> list = new DoubleLinkedList<>();
// 插入新节点
list.insert("A");
list.insert("B");
list.insert("C");
list.insert("D");
// 遍历链表并打印元素
System.out.println("链表元素：");
list.traverse();
// 查找指定元素节点
String target = "B";
Node<String> foundNode = list.search(target);
if (foundNode != null) {
System.out.println("'" + target + "' 在链表中");
} else {
System.out.println("'" + target + "' 不在链表中");
}
// 修改指定位置节点的值
int position = 2;
String newValue = "E";
list.modify(position, newValue);
// 遍历链表并打印元素
System.out.println("修改后链表元素：");
list.traverse();
// 删除指定元素节点
String toRemove = "C";
list.delete(toRemove);
// 遍历链表并打印元素
System.out.println("删除后链表元素：");
list.traverse();
}
}
在上述代码中，我们首先定义了一个泛型类DoubleLinkedList，它包含一个内部类Node作为链表的节点。该类实现了双向链表的基本功能，包括创建空链表、插入新节点、删除指定元素节点、查找指定元素节点、修改指定位置节点、遍历循环链表等操作。然后，我们编写了一个测试类DoubleLinkedListTest，用于测试DoubleLinkedList泛型类的基本功能。
页:
[1]