java - 在用户定义的 Java 双链表中添加和删除元素

Question

这个问题不太可能对任何 future 的访客有帮助；它只与一个较小的地理区域、一个特定的时间点或一个非常狭窄的情况相关，通常不适用于全世界的互联网受众。如需帮助使此问题更广泛适用， visit the help center 。

已关闭 10 年前。

我正在准备下周的考试，我希望有人能帮助我在双向链表中添加和删除元素。这个逻辑对我来说很有意义，不幸的是我还不太擅长编码(这只是我的第二门计算机科学类(class))。我已经浏览了整个网络和我的文本，但我似乎找不到足够接近我的问题的示例。下面我将发布我的教授要求我完成的任务，以及我当前的代码。预先感谢您的帮助。

更新

我在添加时也遇到了问题，但有人能够帮助我，但我的删除方法仍然存在问题。我觉得很奇怪，我的教授有一个返回类型不是 void 的删除方法。有人可以解释一下吗？无论如何，我更新的代码如下。

来自教授:

将 CS401DblLinkedListImpl.java 中缺少的代码填写为在类讲授中指出。

要测试您的代码，请创建一个双向链表并输入其中包含以下 String 类型的元素:

比尔、罗汉、詹姆斯、克里希纳、哈维尔、丽莎

(a) 从头开始​​打印链接列表。

(b) 从末尾开始打印链接列表。

(c) 删除 Bill 并从头开始打印链接列表。

(d) 删除 Lisa 并从末尾开始打印链表。

(e) 删除 Krishna 并打印从开始。

以下代码集是我的用户定义的类，我将测试的方法是 boolean add(E e)、E remove(int n)、void print_from_beginning() 和 void print_from_end():

package week6;

import java.util.Iterator;

public class CS401DblLinkedListImpl<E> //implements CS401CollectionInterface<E> 
{
   private LinkEntry<E> head = null;
   private LinkEntry<E> tail = null;
   private int size = 0;

   public CS401DblLinkedListImpl()
   {
      head = tail = null;
   }

   public boolean is_empty()
   {
      if (head == null) 
          return true;

      return false;
   }

   public int size()
   {
       int count = 0;
       for (LinkEntry<E> current = head; current != null; current = current.next)
           count++;
       return count;
   }

   /*
    * Add e to the end of the doubly linked list.
    * Returns true - if e was successfully added, false otherwise.
    */
   public boolean add(E e)
   {   
      LinkEntry<E> new_element = new LinkEntry<E>();
      new_element.element = e;

          if (head == null)
          {
          new_element.next = head;
          head = new_element;
          tail = head;
      }
      else
      {
          tail.next = new_element;
          new_element.previous = tail;
          tail = new_element;
      }
      return true;
   }

   /*
    * Remove the nth element in the list.  The first element is element 1.
    * Return the removed element to the caller.
    */
   public E remove(int n)
   {
      LinkEntry<E> current = new LinkEntry<E>();
      int i = 0;

      while (n == i++)
      {
          current.previous.next = current.next;
          if (current.next == null)
          {
              current.next.previous = current.previous;
          }
      }
      return (E) current;
   }

  /*
   * Print the doubly linked list starting at the beginning.
   */
   public void print_from_beginning()
   {
      LinkEntry<E> current = new LinkEntry<E>();
      for (current = head; current != null; current = current.next)
      {
          System.out.print(current.element + " ");
      }
   }

   /*
    * Print the doubly linked list starting the end.
    */
   public void print_from_end()
   {
      LinkEntry<E> current = new LinkEntry<E>();
      for (current = tail; current != null; current = current.previous)
      {
          System.out.print(current.element + " ");
      }
   }

   /* ------------------------------------------------------------------- */
   /* Inner classes                                                      */
   protected class LinkEntry<E>
   {
      protected E element;
      protected LinkEntry<E> next;
      protected LinkEntry<E> previous;

      protected LinkEntry() { element = null; next = previous = null; }
   }
   /* ------------------------------------------------------------------- */
   protected class CS401DblLinkedListImplIterate<E> implements Iterator<E>
   {

       protected LinkEntry<E> next;

       protected CS401DblLinkedListImplIterate()
       {
           next = (LinkEntry<E>) head;
       }

       @Override
       public boolean hasNext() {
           // TODO Auto-generated method stub
           return false;
       }

       @Override
       public E next() {
       // TODO Auto-generated method stub
       return null;
       }

       @Override
       public void remove() {
       // TODO Auto-generated method stub
       }
      }
} /* CS401LinkedListImpl<E> */

下面是我测试方法的主类:

package week6;

import java.util.*;

public class App {

    public static <E> void main(String[] args) {

    /*
     * Part 1 of lab 6: Testing CS401DblLinkedListImpl
     */
    System.out.println("Testing Lab 6: Part 1...");
    CS401DblLinkedListImpl<String> list = new CS401DblLinkedListImpl<String>();

    list.add("Bill");
    list.add("Rohan");
    list.add("James");
    list.add("Krishna");
    list.add("Javier");
    list.add("Lisa");

    System.out.println("List size after all names are added: " + list.size());

    //a. Print the linked list starting at the beginning.
    System.out.println("\nPrint the linked list starting at the beginning:");
    list.print_from_beginning();

    //b. Print the linked list starting at the end.
    System.out.println("\nPrint the linked list starting at the end:");
    list.print_from_end();

    //c. Remove Bill and print the linked list starting from beginning.
    System.out.println("\nRemove Bill and print the linked list starting from beginning:");
    list.remove(0);
    list.print_from_beginning();

    //d. Remove Lisa and print the linked list starting from end.
    System.out.println("\nRemove Lisa and print the linked list starting from end:");
    list.remove(4);
    list.print_from_end();

    //e. Remove Krishna and print the linked list starting from the beginning.
    System.out.println("\nRemove Krishna and print the linked list starting from the beginning:");
    list.remove(2);
    list.print_from_beginning();

    System.out.println("\nList size: " + list.size());
    }
}

最后，下面是我运行程序时得到的结果:

Testing Lab 6: Part 1...
List size after all names are added: 6

Print the linked list starting at the beginning:
Bill Rohan James Krishna Javier Lisa 
Print the linked list starting at the end:
Lisa Javier Krishna James Rohan Bill 
Remove Bill and print the linked list starting from beginning:
Exception in thread "main" java.lang.NullPointerException
    at week6.CS401DblLinkedListImpl.remove(CS401DblLinkedListImpl.java:67)
    at week6.App.main(App.java:34)

仅供引用，CS40​​1DblLinkedListImpl.java:67 指的是我的删除方法中的以下代码行:

      current.previous.next = current.next;

对此的任何帮助将不胜感激。我觉得我已经接近答案了，只是需要一些澄清。谢谢。

Answer 1

您当前的代码将无法处理删除索引 0 的操作。

LinkEntry<E> current = head;
if (n == 0) {
    // something like this maybe...
    head = head.next;
    if (head != null) { head.previous = null; }
    return current;
}

您从 i = 0 开始，但执行 i++，这样您就处于领先地位，但索引为 1。

而且你的删除逻辑对我来说看起来很奇怪。

 current.previous.next == current (is true)
 current.next.previous == current (is true)

所以它应该是这样的:

if (n == i++) {
    // We're at the spot so let's remove it.
    current.previous.next = current.next;
    if (current.next != null) { current.next.previous = current.previous; }
    return current;
}

另外我相信你添加的逻辑也是错误的，应该是这样的。

LinkEntry<E> new_element = new LinkEntry<E>();
new_element.element = e;
if (head == null) {
    head = new_element;
    tail = head;
} else {
    tail.next = new_element;
    new_element.previous = tail;
    tail = new_element;
}

size++;  // You don't use size it looks like...  and your size starts at 1 which is 
         // wrong, it should start at 0 since it's empty, also remove would have to
         // update size.
return true;