Java, LinkedList of Strings. Paste in alphabetical order

Question

Java, LinkedList of Strings. Paste in alphabetical order

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

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

I think my method really messed 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);
                }
            }
        }      

    }

So this inserts all my lines, but not alphabetically. 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++;
    }

+2

java linked-list insert

user69514 Apr 24 '10 at 9:41

a source to share

6 answers

To do this, instead of developing my own sorted list from scratch, I would implement the Queue interface or extend the existing PriorityQueue (or any other sorted collection that might be better suited). 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 a new Node only if another object is not already in the queue, incrementing the counter otherwise. If you are using java> 5.0 for type safety, I would use generic to only allow queued Node objects.

+1

Marcos carceles Apr 24 10:01 am

a source to share

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

Multiset works like a set, but allows duplicates (and counts them!). Have a look at TreeMultiset :

A multiset that maintains the ordering of its elements according to either their natural ordering or an explicit comparator.

0

Roman Apr 24 '10 at 9:45

a source to share

Without seeing the complete code, it is difficult to debug. I think the problem is that you have installed

 Node temp = head;

before the loop, but you need to reassign temp

while while moving the list to the current element. In this case, you keep comparing with head

.

0

stacker Apr 24 10 at 9:53 am

a source to share

You have taken care of when is list

initially empty. You should also take care of the special case when the new node goes to the beginning of the list. If your list B->C->D

and you insert A

.
Good to install node.next

in null

(if not already done). So if a node is inserted at end, we have null

as the next from the last node.
You need to update temp to move to next node if insertion is missing possible. So you are missingtemp = temp.next;

0

codaddict Apr 24 10 at 9:57 am

a source to share

Since this is homework, I won't give you any source code. There is one big problem I see with the code:

Suppose you already have two different elements in your list and you are inserting a new element. In your code, you check node

head

if it is greater and if it inserts it immediately afterwards, ignoring the rest of the elements in the list.

You are coding something like this. There are some missing details that you can fill in yourself.

If the list is empty, install head = node

, head->next = NULL

and you're done.
Otherwise, if node->value < head->value

, install node->next = head, head = node

.
Otherwise, if node->value == head->value

, head->count++

;
Otherwise, install tmp = head

. For now tmp->next->value < node->value

, install tmp=tmp->next

. (mark the zeros!).
If tmp->next == NULL

(i.e. you've reached the end of the list), install tmp->next = node

and you're done.
Otherwise, if tmp->next->value == node->value

(i.e. you reached a node with the same value) tmp->next->count++

.
Otherwise if node->next = tmp->next, tmp->next = node

u quit

0

Il-Bhima Apr 24 At 10:06

a source to share

polygenelubricants · Accepted Answer · 2010-04-24T09:55:29+0000

There are several errors in your code:

Insertion in / before head

really needs to happen in two different scenarios:
- If the list is empty it head
  
  becomesnode
- If the list is not empty, but node
  
  less than the first element, it head
  
  also becomesnode
  - In any case, node
    
    references to what head
    
    was previously pointed to ( null
    
    or the real node) and is head
    
    now pointing to node
    
    .
If you don't insert before head

, then you should insert after some node. We just need to find where the place is. There are two scenarios:
- node.getValue() > temp.getValue()
  
  and node.getValue() < temp.getNext().getValue()
- node.getValue() > temp.getValue()
  
  and temp.getNext() == null
  - Anyway node
    
    inserted between temp
    
    andtemp.getNext()

I suggest to encapsulate the post-insert search in your own function. That is, given the list and the value, it needs to return node. If this node has the same value as the search value, just just increase; otherwise insert after. As a special case, return null

to indicate that the insertion point is before head

.

In pseudocode, it looks 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 have translated my pseudocode to Java, but for some reason you missed codes that deal with inserting before head

when head

not empty. In particular, you inexplicably missed this part:

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

and this part:

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

Both are required; this is what allows "A"

insertion before head

in [ "B", "C", "D" ]

.

You need to understand why they are important and really ask yourself why you chose to remove them. Explain to us, to me, for yourself why you did it; recognize the mistake and learn from it.

Java, LinkedList of Strings. Paste in alphabetical order

More articles: