Question

Consider the following code to insert an item in a sorted linked list without a dummy node.

 60  public void insert(T t) {
 61    Node p;
 62    for (p = head; head != null; p = p.next)
 63      if (p.data.compareTo(t) > 0) break;
 64    if (p == head) p = new Node(t, head);
 65    else p.next = new Node(t,p);
 66  }

1. If we insert the value 5 into an empty list, nothing happens. The list stays empty. Why did we get this problem? Fix the bug.
2. Now assume we have successfully inserted 5 into an empty sequence. If we then try to insert the value 7, it crashes with a “null pointer exception” on line 63. In the debugger it says that p is null. There's a simple thing wrong with the loop header on line 62. What? Fix it. (This doesn't fix the full problem, of course.)
3. Once we fix that problem, it still crashes when we attempt to insert 7 into the list, this time on the `else' line (line 65). Again the debugger says that p is null. What happened? Fix the bug. This will require a bigger change.
4. Depending on how you fixed the previous bug, there may still be nasty bugs.

Answer 1

Here is the corrected code for this method. Fixes are highlighted in bold text. Let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

Explanation: The first bug (inserted element not getting displayed) was because the head node wasn’t getting updated, the next bug was due to the error in for loop condition, and all the remaining bugs were due to the incorrect logic (related to the Node object p)

public void insert(T t) {

                Node p;

                // creating another Node to store the previous node of p

                Node prev = null;

                // updated for loop (condition has been fixed)

                for (p = head; p != null; p = p.next) {

                                if (p.data.compareTo(t) > 0)

                                               break;

                                // storing p in prev, before moving to next iteration

                                prev = p;

                }

                if (p == head) {

                                p = new Node(t, head);

                                head = p; // updating head to fix the error

                } else {

                                // simple fix to solve all the nasty bugs

                                //adding the new node between prev and p

                                prev.next = new Node(t, p);

                }

}