How does insert and delete method of SortedList in Java work

Question

This is more about my lack of ability to understand the SortedList Class. The ListNode I understand: it is a node made up of 2 things: A comparable object and a ListNode object which itself has the same 2 things.

I do not understand how the insert and delete method work in the SortedList Class down below. It's very complex to understand. In the SortedList Class, if the head which is null, points to curr. Shouldn't curr be null? Then the while loop should not execute, but it in fact does execute when I use println to test execution.

Code for ListNode Class:

public class ListNode {

    private Comparable data;
    private ListNode next;

    public ListNode() {
        data = null;
        next = null;
    }

    public ListNode(Comparable x) {
        data = x;
        next = null;
    }

    public ListNode(Comparable x, ListNode nextListNode) {
        data = x;
        next = nextListNode;
    }

    public Comparable getData() {
        return data;
    }

    public ListNode getNext() {
        return next;
    }

    public void setData(Comparable x) {
        data = x;
    }

    public void setNext(ListNode nextListNode) {
        next = nextListNode;
    }

}

Code for SortedList:

public class SortedList {

    private ListNode head;

    public SortedList() {
        head = null;
    }

    public void insert(Comparable x) {
        ListNode curr = head, prev = null;
        while (curr != null && x.compareTo(curr.getData()) > 0) {
            prev = curr;
            curr = curr.getNext();
        }
        if (prev == null) {
            head = new ListNode(x, curr);
        } else {
            prev.setNext(new ListNode(x, curr));
        }
    }

    public boolean delete(Comparable x) {
        if (head == null) {
            return false;
        }
        ListNode curr = head, prev = null;
        while (curr != null && x.compareTo(curr.getData()) > 0) {
            prev = curr;
            curr = curr.getNext();
        }
        if (curr == null || x.compareTo(curr.getData()) != 0) {
            return false;
        }
        if (prev == null) {
            head = curr.getNext();
        } else {
            prev.setNext(curr.getNext());
        }
        return true;
    }

    public void output() {
        for (ListNode curr = head; curr != null; curr = curr.getNext()) {
            System.out.println(curr.getData());
        }
    }

}

Code for TestSortedList:

public class TestSortedList {

    public static void main(String[] args) {
        SortedList list = new SortedList();
        list.insert(5);
        list.insert(1);
        list.insert(10);
        list.insert(3);
        list.insert(7);
        list.output();
        System.out.println(list.delete(5));
        System.out.println(list.delete(5));
        System.out.println(list.delete(1));
        System.out.println(list.delete(10));
        System.out.println(list.delete(11));
    }

}

Answer 1

curr is null when the first call to insert is made. So while gets ignored for this time.

But as prev == null evaluates to true, if block gets executed, essentially executing this line:

head = new ListNode(x, curr);

With that, head no more remains null, and any further calls to insert may result in while loop getting executed. Whether the while loop will be executed depends on this expression:

x.compareTo(curr.getData()) > 0

If true, while gets executed, else not.

Answer 2

You need to need to break down the function of (say) the insert method.

• The new node will (typically) be inserted between two nodes ... except when you end up inserting at the start and end of the list.

• The local variable initialization sets things up so that we start looking at the beginning of the loop. The prev variable will point to the node before the insertion point. The curr variable will point to the node after the insertion point.

• The while loop finds the insertion point. It walks through the list nodes until it finds one that is greater than or equal x. The insertion point is before that node. If the list is empty (i.e. head is null), the insertion point is the start of the list. When it completes (including the case where it never runs), prev and curr will have the values needed for the final part ...

• The code after the while loop does the insertion, inserting the new node between the prev node and the curr node. If prev is null, it has to handle things differently.

---

So to answer your question:

But which code makes curr not null then?

No code does that. It does not need to be not null.

At the point you are acttually doing the insertion, curr is the node after the insertion point. If you are inserting at the end of the list (or into an empty list), there is no node after the insertion point, and curr will (and should) be null.

---

Insertion into singly linked lists is a little bit tricky to get your head around, but the key thing to remember is that any algorithm needs to find and update the node before the place you want to insert the new node. The same goes for deletion.

Answer 3

In the first statement, your while loop you have:

while(curr != null && x.compareTo(curr.getData()) >0 )

When you call x.compareTo(curr.getData()), you are comparing 5 to null, which returns 1. Which is greater than 0, so half the requirements are true, but it still skips the while loop and proceeds to

 if (prev == null) {
        head = new ListNode(x, curr);

This action gives head a value, and it is no longer null. So when you do you second insertion, you do

ListNode curr = head;

This time, curr is not null, alowing it to enter the loop