Java, LinkedList of Strings. Insert in alphabetical order

Question

I have a simple linked list. The node contains a string (value) and an int (count).

In the linkedlist when I insert I need to insert the new Node in alphabetical order. If there is a node with the same value in the list, then I simply increment the count of the node.

I think I got my method really screwed up.

 public void addToList(Node node){
        //check if list is empty, if so insert at head
        if(count == 0 ){
            head = node;
            head.setNext(null);
            count++;
        }
        else{
            Node temp = head;
            for(int i=0; i<count; i++){
                //if value is greater, insert after
                if(node.getItem().getValue().compareTo(temp.getItem().getValue()) > 0){
                    node.setNext(temp.getNext());
                    temp.setNext(node);                   
                }
                //if value is equal just increment the counter
                else if(node.getItem().getValue().compareTo(temp.getItem().getValue()) == 0){
                    temp.getItem().setCount(temp.getItem().getCount() + 1);
                }
                //else insert before
                else{
                    node.setNext(temp);
                }
            }
        }      

    }

Ok so this is inserting all my strings, but not in alphabetical order. Do you see any error?

 public Node findIsertionPoint(Node head, Node node){
        if( head == null)
            return null;

        Node curr = head;
        while( curr != null){
            if( curr.getValue().compareTo(node.getValue()) == 0)
                return curr;
            else if( curr.getNext() == null || curr.getNext().getValue().compareTo(node.getValue()) > 0)
                return curr;
            else
                curr = curr.getNext();
        }

        return null;
    }

    public void insert(Node node){
        Node newNode = node;
        Node insertPoint = this.findIsertionPoint(this.head, node);
        if( insertPoint == null)
            this.head = newNode;
        else{
            if( insertPoint.getValue().compareTo(node.getValue()) == 0)
                insertPoint.getItem().incrementCount();
            else{
                newNode.setNext(insertPoint.getNext());
                insertPoint.setNext(newNode);
            }
        }
        count++;
    }

Answer 1

There are a few bugs with your code:

• Inserting at/before head actually needs to happen in two different scenarios:
  • If the list is empty, head becomes node
  • If the list is not empty, but node is less than the first element, head also becomes node
    • In either case, node links to whatever head was pointing to before (null or a real node), and head now points to node.
• If you're not inserting before head, then you must be inserting after some node. We just need to find where this place is. There are two scenarios:
  • node.getValue() > temp.getValue(), and node.getValue() < temp.getNext().getValue()
  • node.getValue() > temp.getValue() and temp.getNext() == null
    • In either case, node is inserted between temp and temp.getNext()

I suggest encapsulating the after insertion point search in its own function. That is, given the list and a value, it needs to return a node. If that node has the same value as the search value, then simply increment; otherwise, insert after. As a special case, return null to indicate that the insertion point is before head.

---

In pseudocode, it'll look like this:

FUNCTION findInsertionPoint(Node head, V value) RETURNS Node
  // return null if value needs to be inserted before head
  IF head == null OR value < head.getValue()
     RETURN null;

  // otherwise, either return a node with the given value,
  // or return a node after which value should be inserted
  Node curr = head;
  REPEAT
     IF curr.value == value
        RETURN curr;
     ELSEIF curr.getNext() == null OR curr.getNext().getValue() > value
        RETURN curr;
     ELSE
        curr = curr.getNext();

PROCEDURE insert(V value) {
  Node newNode = NEW Node(value);
  Node insertPoint = findInsertionPoint(this.head, value);
  IF insertPoint == null // insert before head
     newNode.setNext(this.head);
     this.head = newNode;
  ELSE
     IF insertPoint.getValue() == value
        insertPoint.incrementCounter();
     ELSE // insert after insertPoint
        newNode.setNext(insertPoint.getNext());
        insertPoint.setNext(newNode);

---

Update: I see that you've translated my pseudocode to Java, but for some reason you've omitted codes that deals with inserting before head when head is not empty. Specifically, you have inexplicably omitted this part:

IF head == null OR value < head.getValue()
             // ^^^^^^^^^^^^^^^^^^^^^^^^^^

and this part:

IF insertPoint == null 
   newNode.setNext(this.head); // <<<<<<<<<<<
   this.head = newNode;

Both of these are essential; it's what allows "A" to be inserted before the head in [ "B", "C", "D" ].

You need to understand why they're important, and really ask yourself why you chose to remove them. Explain to us, to me, to yourself, why you did that; realize the mistake and learn from it.

Answer 2

Since this is homework I'm not going to give you any source code. There is one big issue I see with the code:

Suppose your list already has two distinct items, and you're inserting a new item. In your code, you are checking whether node is greater than head, and if so inserting it immediately after, ignoring the rest of the items in the list.

You code do something like this. There are some missing details which you can fill in yourself.

1. If list is empty, set head = node, head->next = NULL, and you're done.

2. Otherwise if node->value < head->value, set node->next = head, head = node.

3. Otherwise, if node->value == head->value, head->count++;

4. Otherwise, set tmp = head. While tmp->next->value < node->value, set tmp=tmp->next. (check for nulls!).

5. If tmp->next == NULL, (i.e. you reached end of list) then set tmp->next = node, and you're done.

6. Otherwise if tmp->next->value == node->value, (i.e. you reached a node with same value) tmp->next->count++.

7. Otherwise, if node->next = tmp->next, tmp->next = node, and exit

Answer 3

For making this, instead of developing from scratch my own sorted list I would implement the Queue interface or extend the already existing PriorityQueue (or any other sorted collection that may apply better). I would define the Node class as an implementation of the Comparable interface or instantiate my queue with a Comparator instance and override the PriorityQueue add method to add the new Node only if another object is not already in the queue, incrementing the counter otherwise. If using java >5.0 for type safety I would use generic to allow just Node objects in the Queue.

Answer 4

• You've taken care of the case when the list is initially empty. You should also take care of the special case when the new node goes at be beginning of the list. If your list is B->C->D and you are inserting A.
• Its good to set node.next to null(If not already done). So that if the node gets inserted at the end, we have null as the next of the last node.
• You need to update the temp to move to the next node if no insertion is possible. So you are missing a temp = temp.next;

Answer 5

Without seeing the complete code it's hard to do debugging. I think the problem is that you set

 Node temp = head; 

before the loop, but you need to reassign temp while while traversing the list to the current element. In this case you continue to compare against head.

Answer 6

I think you want to use one of Multiset implementations from Google Collections.

A Multiset works similar to a Set, but allows for duplicates (and counts them!). Look at TreeMultiset:

A multiset which maintains the ordering of its elements, according to either their natural order or an explicit Comparator.