java - inserting/removing into a sorted list recursivey

Question

I have this abstract class I'm implementing, where all the functions implemented must be done using recursion:

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

Below is my implementation so far. I believe I've done the search and retrieve methods correctly, and most of the remove method properly. One of my concerns are my mistake with the insert method (I don't particularly need working code, but maybe a pseudocode like explanation of how you would insert when the abstract class only takes a data argument, resulting in the need of a private class). The other issue is in this condition of the remove method:

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

        }

I'm not sure how I'm supposed to remove the head node, given there's only access to the current and next node. Any help would be appreciated!

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

Removing from the head:

Since you know your list should always be sorted, if you remove the (current) head value then the next head should be the "next" in line. You initially only have access to the "head" node and must move down the list one by one.

So in this case assume you have a bunch of people waiting in line in ordered by first name. If they all hold hands and form a chain to the next person in order and you remove the first person in line. You can logically assume the person holding their hand is the new 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. 
}

Inserting and removing in middle:

Use the same analogy of holding hands earlier. If I need to "insert" a person in the middle of two people, I would first have to find where they belong, then have them link hands with the person before and after them "current" and "next".

For your insert code, you'll have to search until you find correct insert position, which can be in between two nodes, rather than assuming that you'll just insert if the next value is 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);
    }
}

You'll want to check if the current value and the next value are correct in the sorted order.

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
}