Insert items in ascending order in a singly linked list in Java

Question

I need to modify the insert method of my program so that it inserts items into a singly linked list in ascending order. I understand what a linked list is but have no clue how to insert the items in order. Here are my programs so far(not the entire program):

public class SinglySortedLinkedList
{  private Node h;  // list header
    public SinglySortedLinkedList()
    {  h = new Node();  // dummy node
        h.l = null;
        h.next = null;
    }



    public boolean insert(Listing newListing)
    {  Node n = new Node();
        if(n == null) // out of memory
           return false;
        else
        { 
           n.next = h.next;
           h.next = n;
           n.l = newListing.deepCopy();
           return true;

        }
   }

here is the tester method:

public class MainSinglyLinkedList
{ public static void main(String[] args)
 {  SinglySortedLinkedList boston = new SinglySortedLinkedList();
    Listing l1 = new Listing("Bill", "1st Avenue", "123 4567" );
    Listing l2 = new Listing("Al", "2nd Avenue", "456 3232");
    Listing l3 = new Listing("Mike", "3rd Avenue", "333 3333");
    boston.insert(l1);  // test insert
    boston.insert(l2);
    boston.insert(l3);
    boston.showAll();
    l3 = boston.fetch("Mike"); // test fetch of Mike
    System.out.println(l3.toString());
    boston .delete("Al");  // test delete of Al
    boston.showAll();
    boston.update("Mike", l2); // test update of Mike to Al
    boston.showAll();
    System.exit(0);
  }
}

Any ideas of some pseudocode of how to insert in ascending order by the names would be so great, thanks

Why not just insert at the end and sort the collection (assuming you can implement the compareTo function — Mark W, Apr 02 '14 at 15:16
that would make sense but the way my professor needs it to be done is having it sorted as it is entered not after — Jess Anastasio, Apr 02 '14 at 15:18

Joffrey · Answer 1 · 2014-04-02T15:56:52.897

I don't want to do your homework, but I'll give you hints. If you have more specific questions then, you will probably find answers in SO. In the unlikely situation where you don't, feel free to ask a new question ;)

First, you need to find the point in the list where you want to insert, and then insert your Node n (containing the new Listing) at that point. This can be done using a while loop, with a comparison between listings as a condition, which in english would be said:

while the listing of the current node is inferior to the listing I want to insert, I keep on going

For how to do this kind of comparison on Strings in Java, have a look at the compareTo method.

Then, use your former piece of code to insert n there. See the note below to see what I have to say about it and your dummy Node.

Side note

You're using a "dummy node" for your list header, and always insert after that one. This is probably not necessary, you could insert each new Node in place of h and make it point to the former h, which would be both cleaner and easier to read IMHO.

Instead of:

n.next = h.next;
h.next = n;
n.l = newListing.deepCopy();

You could have:

n.next = h; // here n's next points to the former head h
h = n;      // now n in the new head referenced by h
n.l = newListing.deepCopy();

This way, you don't even need a dummy node anymore, null is fine to set the n.next field. It'll also probably simplify your fetch method.

Insert items in ascending order in a singly linked list in Java

1 Answers1

Side note