This discussion is archived
10 Replies Latest reply: Jul 7, 2009 9:52 AM by 843789 RSS

Help PLEASE with linked list. Inserting a string in the middle of

843789 Newbie
Currently Being Moderated
I'm trying to insert new strings to a linked list but it seem i cant never insert. the following code has the instructions. What i'm I not doing right? If i try to use the code, the new strings don't go through

please help someone
// This method should insert a new node containing the string newString immediately after the first
    // occurrence of the string aString in the list. If aString is not in the list, the method should add a node
    // containing newString to the tail of the list.

    public void insertAfter(String newString, String aString)
    {
        StringLLNode newNode = new StringLLNode();
        newNode.setData(newString);
        
        //Check if HeadNode == aString
        if (headNode.getData().equalsIgnoreCase(aString))
            headNode = newNode;
        //rest of the nodes
        StringLLNode currNode = headNode;
        while(currNode != null)
        {
            if (currNode.getData().equalsIgnoreCase(aString))
                {
                    newNode.setNext(currNode);
                    //System.out.println("It went THROUGH");
                }
            currNode = currNode.getNext();
        }
        //Last Node
        if (currNode != null)
        {
            newNode.setNext(headNode);
        }
    }
  • 1. Re: Help PLEASE with linked list. Inserting a string in the middle of
    843789 Newbie
    Currently Being Moderated
    if (headNode.getData().equalsIgnoreCase(aString))
                headNode = newNode;
    The first thing I can see wrong is that you are supposed to insert the newString after aString. But all that code does is make newString the head and tosses away the rest of the list.
  • 2. Re: Help PLEASE with linked list. Inserting a string in the middle of
    843789 Newbie
    Currently Being Moderated
    Thanks flounder, i will fix that and get back at you
  • 3. Re: Help PLEASE with linked list. Inserting a string in the middle of
    843789 Newbie
    Currently Being Moderated
    Flounder, or anyone. I just changed the code you were referring to this
    if (headNode.getData().equalsIgnoreCase(aString))
                headNode.setNext(newNode);
    I tested but the code still does not fix the problem
  • 4. Re: Help PLEASE with linked list. Inserting a string in the middle of
    843789 Newbie
    Currently Being Moderated
    Imagine your linked list has three nodes. First node links to second node which links to third node (at least I hope that is what you have). Now you want to insert a new node after the first node, so you get first node to link to the new node (which is what you have). What happened to second and third nodes? They are now lost because nothing links to them anymore.

    If you are struggling to visualise what is happening then the best thing to do is grab a piece of paper and draw a bunch of squares representing your nodes. Then draw arrows between the boxes to indicate which node is link to which. Then you can erase arrows and redraw them to indicate any changes you make.

    Also, that if statement is not needed anyway as you should be able to do all the work in your while loop.
  • 5. Re: Help PLEASE with linked list. Inserting a string in the middle of
    699554 Newbie
    Currently Being Moderated
    I have to agree with flounder, go grab a pen and paper and logically work thru the code snippet you posted.
    public void insertAfter(String newString, String aString)
    {
            StringLLNode newNode = new StringLLNode();
            newNode.setData(newString);
            
            //Check if HeadNode == aString
            if (headNode.getData().equalsIgnoreCase(aString))
                headNode = newNode;
            //rest of the nodes
            StringLLNode currNode = headNode;
            while(currNode != null)
            {
                if (currNode.getData().equalsIgnoreCase(aString))
                    {
                        newNode.setNext(currNode);
                        //System.out.println("It went THROUGH");
                    }
                currNode = currNode.getNext();
            }
            //Last Node
            if (currNode != null)
            {
                newNode.setNext(headNode);
            }
    }
    Given a linked list [A-E] we have: A => B => C => D => E. Each Node is referencing the node to it's right, so A references B, D references E etc.
    For example take aString = "A" and newString = "AB". Your code suggests the following:

    1. Create new_node "AB"
    2. if head[A] equals aString[A], TRUE
    2.a head = new_ node

    Now the resulting linkedlist is the following:
    AB => Null
    what happened to the rest of the list?

    Now we go on to your updated example, we result in the following list:
    A => AB => Null
    hmm do you see a pattern here? when inserting a new node we are disregarding any reference to the tail of the list.

    Extending on that idea we have the following pseudo code
    1. if node to be inserted
    1.a new_node.next = list_tail
    1.b current_node.next = new_node

    A => B => C => D => E, where newnode=AA
    AA => B => C => D => E //using 1.a
    A => AA => B => C => D => E //using 1.b

    Mel
  • 6. Re: Help PLEASE with linked list. Inserting a string in the middle of
    843789 Newbie
    Currently Being Moderated
    Ok folks thanks for the input. I drew the images and i just need to know something. First of all, this is the first time i'm doing this and some of the codes the instructor provided.
    Let me get this bit by bit instead of the whole thing coz i'm getting much more confused and unfortunately i dont have anywhere to get help and the thing is due today, plus i have lots of other methods to transverse.

    1. I will check if the head node equals the the string i need to insert another string after: and I think this code should do it
    StringLLNode newNode = new StringLLNode();
            newNode.setData(newString);
    //Check if HeadNode == aString
            if (headNode.getData().equalsIgnoreCase(aString))
                headNode.setNext(newNode);
    Then I will check for the rest. After i drew the boxes i figured out that if the next (or subsequent) nodes equals what i want, then I will need to:
    got through this while loop
    while(currNode != null)
            {
                if (currNode.getData().equalsIgnoreCase(aString))
                    {
                        newNode.setNext(currNode.getNext());//links the new node to the next node after what was equal
                        currNode.setNext(newNode);
                    }
                currNode = currNode.getNext();
            }
    But it seems that this turns out to be an infinite loop!
    Guys please help, i'm so disparate.

    Edited by: deyiengz on Jul 7, 2009 5:33 AM
  • 7. Re: Help PLEASE with linked list. Inserting a string in the middle of
    699554 Newbie
    Currently Being Moderated
    deyiengz wrote:
    1. I will check if the head node equals the the string i need to insert another string after: and I think this code should do it
    StringLLNode newNode = new StringLLNode();
    newNode.setData(newString);
    //Check if HeadNode == aString
    if (headNode.getData().equalsIgnoreCase(aString))
    headNode.setNext(newNode);
    Why are you treating the headNode differently to any other node? All you are doing is setting the heads next node to equal the new node.
    E..g. headNode => newNode => null

    Keep it simple, set the currentNode to equal the headNode then iterate over the nodes until either of two outcomes happen:
    1. [match] -
    newNode.setNext(currNode.getNext());//links the new node to the next node after what was equal
    currNode.setNext(newNode);
    //YOU INSERTED THE NEW NODE!!! STOP ITERATING OVER THE LOOP
    2. [newNode equals null] - no match found, do nothing

    Mel
  • 8. Re: Help PLEASE with linked list. Inserting a string in the middle of
    843789 Newbie
    Currently Being Moderated
    Mel I thought I go through the head node first and do the simple code if it equals what i'm looking for.
    I don't see why you say the new node is null after this code
    StringLLNode newNode = new StringLLNode();  newNode.setData(newString);
  • 9. Re: Help PLEASE with linked list. Inserting a string in the middle of
    699554 Newbie
    Currently Being Moderated
    deyiengz wrote:
    Mel I thought I go through the head node first and do the simple code if it equals what i'm looking for.
    The simple code? Explain to me, what is the simple code? This is exactly my point why are you treating the head differently if you always insert after a match.
    I don't see why you say the new node is null after this code
    StringLLNode newNode = new StringLLNode();  newNode.setData(newString);
    I am not saying that, I am saying your "simple code" sets heads next node to equal the new node and disregards the rest of the list. What you want to do is if a match is found with the currentNode, set the newNodes next() to equal the currentNodes next(), then set the currentNodes next() to equal the new node. Exactly what you do here:
    while(currNode != null){
      if (currNode.getData().equalsIgnoreCase(aString)){
        newNode.setNext(currNode.getNext());//links the new node to the next node after what was equal
        currNode.setNext(newNode);
      }
      currNode = currNode.getNext();
    }
    Again don't treat the head differently, initially set the currNode to equal the head, then use your loop above. You will need to break or return from the while loop when a match is found unless the linkedlist contains non unique values. In which case if the linkedlist contains non unique values you will need to create a newNode with the newString each time you insert, otherwise you are referencing the same object.

    Mel
  • 10. Re: Help PLEASE with linked list. Inserting a string in the middle of
    843789 Newbie
    Currently Being Moderated
    [http://forums.devshed.com/java-help-9/please-help-with-linked-list-anyone-622781.html]

    Stack overflow error.

    ~