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

}

Brion · Accepted Answer · 2016-10-10 16:39:03Z

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
}

edited Oct 10, 2016 at 16:39

answered Oct 10, 2016 at 16:11

Brion

7463 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

witcheR Over a year ago

Psuedo code would be appreciated for insert. For the remove condition you mentioned, I do understand that logic, but my issue is with this sortedlist class implementation, there is no previous node, and the way we'd "remove" a node is to set node.next to node.next.next. In this case, there is no ".next" that points to the head node, which is where I'm lost.

Brion Over a year ago

With the current node, you can check any amount of nodes you want as long as you know how many to check by chaining "next". I can check curr.next.next. If I want 3 down the line. There is no need to have a "previous" node if use temp nodes wisely and do checks down the line.

Brion Over a year ago

@abdi why do you need a next node that points to the head? If you need to insert at the head, then just set the Node ref node to you new node, which I believe you are currently doing correctly. For deleting head, you'll just point temp.next = head.next. Then head = temp. There's no way to access this old head value and it will be cleared out with the gc.

witcheR Over a year ago

I believe I've done the insert method correctly now, but when trying to run the program (it compiles fine) using the main method I put in the original post, it gives me a null pointer exception: gyazo.com/49cf251d5c7d70872513949ae12760d1 Isn't this handled my the first condition in the insert?

Brion Over a year ago

It's because you've called insert when curr is null. This happens if the head node is null. You do, curr = head; (which is null if the list is empty). Then although you set the new head, you don't fix curr and do insert(curr,data). You need to place the insert(curr,data) as the else statement.

|

Collectives™ on Stack Overflow

java - inserting/removing into a sorted list recursivey

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related