java - 递归插入/删除排序列表

Question

我正在实现这个抽象类，其中实现的所有函数都必须使用递归来完成:

public abstract class List<E> implements Iterable<E> {
protected class Node<T> {

    protected Node(T data) {
        this.data = data;
    }

    protected T data;
    protected Node<T> next;
}

public abstract void insert(E data);
public abstract void remove(E data);
public abstract E retrieve(int index);
public abstract boolean search(E data);

protected Node<E> head;
}

下面是我迄今为止的实现。我相信我已经正确地完成了搜索和检索方法，并且正确地完成了大部分删除方法。我担心的一个问题是我对插入方法的错误(我并不特别需要工作代码，但也许是一个伪代码，解释当抽象类只接受数据参数时如何插入，从而需要一个私有(private)类)。另一个问题是在删除方法的这种情况下:

if (key.compareTo(temp.data) == 0){

        }

我不确定如何删除头节点，因为只能访问当前和下一个节点。任何帮助将不胜感激!

import java.util.Iterator;
import java.util.Random;

public class SortedList<E extends Comparable<? super E>> extends List<E> {

public static void main(String[] args) {

    Random rand = new Random(1);
    SortedList<Integer> list = new SortedList<Integer>();

    list.insert(1);
    System.out.println(list.search(1));
}
 public Iterator<E> iterator() {

        return new Iterator<E>() {
            public boolean hasNext() {
                return curr != null;
            }
            public E next() {
                E temp = curr.data;
                curr = curr.next;
                return temp;
            }
            public void remove() {
                throw new UnsupportedOperationException();
            }
            private Node<E> curr = (Node<E>)head;
        };
    }


public void insert(E data) {
    Node<E> temp = new Node<E>(data);
    Node<E> curr = head;
     if (head == null || data.compareTo(head.data) < 0) {
            temp.next = head;
            head = temp;
        }
    insert(curr, data);
}
    private void insert(Node<E> curr, E data){
        if (curr.next == null) {
            curr.next.data = data;
        } else {
            curr.next.insert(curr, data);
        }
    }


public void remove(E data) {
    Node<E> curr = head;
    remove(curr, data);
}
    private void remove(Node<E> temp, E key){
        if (temp == null){
            return;
        }
        if (key.compareTo(temp.data) == 0){

        }
        if (key.compareTo(temp.next.data) == 0){
            temp.next = temp.next.next;
            return;
        }
        if (key.compareTo(temp.next.data) < 0){
            remove(temp.next, key);
        }

    }




public E retrieve(int index) 
{
    Node<E> curr = head;
    int counter = 0;
    return retrieve(curr, index, counter);
}
 private E retrieve(Node<E> temp, int idx, int c)
   {
      if (idx == c){
          return temp.data;
      }
      return retrieve(temp.next, idx, c++);
   }


 public boolean search(E data)
   {
     Node<E> curr = head;
     return search(curr, data);
   }
   private boolean search(Node<E> temp, E key)
   {
      if (temp == null){
         return false;
      }
      if (key.compareTo(temp.data) == 0){
        return true;
      }
      if (key.compareTo(temp.data) < 0){
         return search(temp.next, key);
      }
      return false;
   }

}

Answer 1

从头部移除:

由于您知道列表应始终排序，因此如果删除(当前) header value ，则下一个头应该是行中的“下一个”。您最初只能访问“头”节点，并且必须在列表中逐个向下移动。

因此，在这种情况下，假设您有一群人按名字顺序排队等候。如果他们都手拉手并按顺序形成一条链到下一个人，那么您将排在第一位的人移走。你可以从逻辑上假设握着他们手的人是新任领导。

Node<E> temp = new Node<E>(data);
if(check to see if you want to remove head){
     temp.next = head.next; //current head points to next in line so so shall new head(temp);
     head = temp; //head ref variable points to only new head and old one is inaccessible and will be cleared out during garbage collection. 
}

在中间插入和删除:

使用之前牵手的相同比喻。如果我需要将一个人“插入”两个人中间，我首先必须找到他们所属的位置，然后让他们与“当前”和“下一个”之前和之后的人握手。

对于插入代码，您必须进行搜索，直到找到正确的插入位置，该位置可以位于两个节点之间，而不是假设如果下一个值为 null，则只插入。

private void insert(Node<E> curr, E data){
    if (curr.next == null) {
        curr.next.data = data; //only inserts if next value is null
    } else { // what about inserting 3, into a list of {1,5}. 
        curr.next.insert(curr, data);
    }
}

您需要检查当前值和下一个值的排序顺序是否正确。

else if(curr.data <= data && curr.next.data > data){
        // you've found the nodes you want to insert in between
}else{
  ... keep searching until you hit a null
}