Java - вставка/удаление в отсортированный список 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 
}