[已解决]数据结构

zsxxn · 发表于 2023-11-13 17:20:49

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

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

最佳答案

月排行榜 / 总排行榜

isdkz

2023-11-13 17:21:06

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 来测试这些功能。

跳转到最佳答案楼层

isdkz · 发表于 2023-11-13 17:21:06

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 来测试这些功能。

Mike_python小 · 发表于 2023-11-13 17:25:55

以下是一个基于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泛型类的基本功能。

账号		自动登录	找回密码
密码			立即注册