[已解决]数据结构

zsxxn

请编程完成泛型类DoubleLinkedList（双向链表），DoubleLinkedList的基本功能设计要求：创建双向链表、插入新的结点、删除指定元素结点、查找指定元素结点、修改指定位置结点、遍历循环链表，并写一个全部测试类

最佳答案

月排行榜 / 总排行榜

isdkz

2023-11-13 17:21:06

1. public class DoubleLinkedList<T> {
   
2.     private Node<T> head;
   
3.     private Node<T> tail;
   
4. 
   
5.     public void insert(T data) {
   
6.         Node<T> newNode = new Node<>(data);
   
7.         if (head == null) {
   
8.             head = newNode;
   
9.             tail = newNode;
   
10.         } else {
    
11.             tail.next = newNode;
    
12.             newNode.prev = tail;
    
13.             tail = newNode;
    
14.         }
    
15.     }
    
16. 
    
17.     public void delete(T data) {
    
18.         Node<T> current = head;
    
19.         while (current != null) {
    
20.             if (current.data.equals(data)) {
    
21.                 if (current.prev != null) {
    
22.                     current.prev.next = current.next;
    
23.                 } else {
    
24.                     head = current.next;
    
25.                 }
    
26.                 if (current.next != null) {
    
27.                     current.next.prev = current.prev;
    
28.                 } else {
    
29.                     tail = current.prev;
    
30.                 }
    
31.                 return;
    
32.             }
    
33.             current = current.next;
    
34.         }
    
35.     }
    
36. 
    
37.     public Node<T> search(T data) {
    
38.         Node<T> current = head;
    
39.         while (current != null) {
    
40.             if (current.data.equals(data)) {
    
41.                 return current;
    
42.             }
    
43.             current = current.next;
    
44.         }
    
45.         return null;
    
46.     }
    
47. 
    
48.     public void modify(int index, T newData) {
    
49.         Node<T> current = head;
    
50.         int i = 0;
    
51.         while (current != null && i < index) {
    
52.             current = current.next;
    
53.             i++;
    
54.         }
    
55.         if (current != null) {
    
56.             current.data = newData;
    
57.         }
    
58.     }
    
59. 
    
60.     public void traverse() {
    
61.         Node<T> current = head;
    
62.         while (current != null) {
    
63.             System.out.print(current.data + " ");
    
64.             current = current.next;
    
65.         }
    
66.     }
    
67. 
    
68.     private static class Node<T> {
    
69.         private T data;
    
70.         private Node<T> prev;
    
71.         private Node<T> next;
    
72. 
    
73.         public Node(T data) {
    
74.             this.data = data;
    
75.         }
    
76.     }
    
77. }
    

复制代码

1. public class DoubleLinkedListTest {
   
2.     public static void main(String[] args) {
   
3.         DoubleLinkedList<Integer> list = new DoubleLinkedList<>();
   
4.         list.insert(1);
   
5.         list.insert(2);
   
6.         list.insert(3);
   
7.         list.insert(4);
   
8.         list.traverse(); // 输出：1 2 3 4
   
9.         list.delete(3);
   
10.         list.traverse(); // 输出：1 2 4
    
11.         System.out.println(list.search(2).data); // 输出：2
    
12.         list.modify(1, 5);
    
13.         list.traverse(); // 输出：1 5 4
    
14.     }
    
15. }
    

复制代码

在上面的代码中，我们定义了一个泛型类 DoubleLinkedList ，它实现了双向链表的基本功能。我们可以通过 insert 方法插入新的结点，通过 delete 方法删除指定元素结点，通过 search 方法查找指定元素结点，通过 modify 方法修改指定位置结点，以及通过 traverse 方法遍历循环链表。同时，我们编写了一个测试类 DoubleLinkedListTest 来测试这些功能。

跳转到最佳答案楼层

isdkz

1. public class DoubleLinkedList<T> {
   
2.     private Node<T> head;
   
3.     private Node<T> tail;
   
4. 
   
5.     public void insert(T data) {
   
6.         Node<T> newNode = new Node<>(data);
   
7.         if (head == null) {
   
8.             head = newNode;
   
9.             tail = newNode;
   
10.         } else {
    
11.             tail.next = newNode;
    
12.             newNode.prev = tail;
    
13.             tail = newNode;
    
14.         }
    
15.     }
    
16. 
    
17.     public void delete(T data) {
    
18.         Node<T> current = head;
    
19.         while (current != null) {
    
20.             if (current.data.equals(data)) {
    
21.                 if (current.prev != null) {
    
22.                     current.prev.next = current.next;
    
23.                 } else {
    
24.                     head = current.next;
    
25.                 }
    
26.                 if (current.next != null) {
    
27.                     current.next.prev = current.prev;
    
28.                 } else {
    
29.                     tail = current.prev;
    
30.                 }
    
31.                 return;
    
32.             }
    
33.             current = current.next;
    
34.         }
    
35.     }
    
36. 
    
37.     public Node<T> search(T data) {
    
38.         Node<T> current = head;
    
39.         while (current != null) {
    
40.             if (current.data.equals(data)) {
    
41.                 return current;
    
42.             }
    
43.             current = current.next;
    
44.         }
    
45.         return null;
    
46.     }
    
47. 
    
48.     public void modify(int index, T newData) {
    
49.         Node<T> current = head;
    
50.         int i = 0;
    
51.         while (current != null && i < index) {
    
52.             current = current.next;
    
53.             i++;
    
54.         }
    
55.         if (current != null) {
    
56.             current.data = newData;
    
57.         }
    
58.     }
    
59. 
    
60.     public void traverse() {
    
61.         Node<T> current = head;
    
62.         while (current != null) {
    
63.             System.out.print(current.data + " ");
    
64.             current = current.next;
    
65.         }
    
66.     }
    
67. 
    
68.     private static class Node<T> {
    
69.         private T data;
    
70.         private Node<T> prev;
    
71.         private Node<T> next;
    
72. 
    
73.         public Node(T data) {
    
74.             this.data = data;
    
75.         }
    
76.     }
    
77. }
    

复制代码

1. public class DoubleLinkedListTest {
   
2.     public static void main(String[] args) {
   
3.         DoubleLinkedList<Integer> list = new DoubleLinkedList<>();
   
4.         list.insert(1);
   
5.         list.insert(2);
   
6.         list.insert(3);
   
7.         list.insert(4);
   
8.         list.traverse(); // 输出：1 2 3 4
   
9.         list.delete(3);
   
10.         list.traverse(); // 输出：1 2 4
    
11.         System.out.println(list.search(2).data); // 输出：2
    
12.         list.modify(1, 5);
    
13.         list.traverse(); // 输出：1 5 4
    
14.     }
    
15. }
    

复制代码

在上面的代码中，我们定义了一个泛型类 DoubleLinkedList ，它实现了双向链表的基本功能。我们可以通过 insert 方法插入新的结点，通过 delete 方法删除指定元素结点，通过 search 方法查找指定元素结点，通过 modify 方法修改指定位置结点，以及通过 traverse 方法遍历循环链表。同时，我们编写了一个测试类 DoubleLinkedListTest 来测试这些功能。

Mike_python小

以下是一个基于Java语言的泛型双向链表类DoubleLinkedList的实现，以及一个测试类DoubleLinkedListTest。

[/code]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();
    }
}
[/code]

以下是测试类DoubleLinkedListTest：

[/code]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();
    }
}
[/code]

在上述代码中，我们首先定义了一个泛型类DoubleLinkedList，它包含一个内部类Node作为链表的节点。该类实现了双向链表的基本功能，包括创建空链表、插入新节点、删除指定元素节点、查找指定元素节点、修改指定位置节点、遍历循环链表等操作。然后，我们编写了一个测试类DoubleLinkedListTest，用于测试DoubleLinkedList泛型类的基本功能。