爪哇 - 插入/刪除到一個排序列表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 
}