爪哇 - 插入/删除到一个排序列表recursivey

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; 
} 

下面是我执行至今。我相信我已经正确地完成了搜索和检索方法，并且正确地执行了大部分删除方法。我的一个担心是我的错误与插入方法（我并不特别需要工作的代码，但也许就像当抽象类只需要一个数据参数，导致需要私有类的你将如何插入解释伪）。另一个问题是在remove方法的这种情况：

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

从头部取下：

既然你知道你的列表应始终进行排序，如果删除了（当前）水头值那么接下来的头部应当符合“下一步”。您最初只能访问“head”节点，并且必须逐个向下移动列表。

因此，在这种情况下，假设你有一堆人排队等候在按名字排序。如果他们都握住手并按顺序与下一个人形成链条，并且您将第一个人排队。你可以合理地认为握着他的手是新的头。

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 
}