Results 1 to 13 of 13
  1. #1
    plasticfood is offline Member
    Join Date
    Sep 2010
    Posts
    32
    Rep Power
    0

    Default understanding implemention of a queue linked list

    i've reading this code for awhile, and i'm still not convinced how it works. this code is from my textbook:
    -----------------------------------
    Java Code:
    public void enqueue(String s)
        {
            if (rear != null)//if NOT empty
            {
               rear.next = new Node(s, null);
               rear = rear.next;
            }
            else//if empty
            {
                rear = new Node(s, null);
                front = rear;
            }
        }
    
     public String dequeue()
        {
           if (empty()) 
               throw new EmptyQueueException();
           else
           {
               String value = front.value;
               front = front.next;
               if (front == null) rear = null;    
               return value;
           }
        }
    --------------------------------------------------
    the part that i'm confused about is when front is set equal to rear. So front is basically a node with a string value, and it is pointing to a NULL node. front is never updated to point to the next node when the next node is added (unless i am unaware that it dynamically changes its pointer when rear is changed). so when one uses the dequeue method, first the string value is extracted from the front node which is fine, but then it tries to move front up to the next node by calling its next node value, which i believe it is still null b/c again the front node was never updated to know that it should be pointing immediately to the next node that is added right after the first node.

    am i missing something here? i've tried explaining this to many people and they don't get what i'm saying most of the time. this is really bothering me.
    Last edited by plasticfood; 05-10-2011 at 11:23 PM.

  2. #2
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,785
    Rep Power
    7

    Default

    Quote Originally Posted by plasticfood View Post
    front is never updated to point to the next node when the next node is added
    Of course it doesn't. You want "front" to always point to the first item in the queue. It doesn't make sense to have "front" point at the third item (at least it doesn't make sense to me. I don't know about you).

    What that code is doing is when the queue is empty and a new item is added "front" and "rear" both point to the same item. Since there is only one item it is both the first and last item in the queue.

    so when one uses the dequeue method, first the string value is extracted from the front node which is fine, but then it tries to move front up to the next node by calling its next node value, which i believe it is still null b/c again the front node was never updated to know that it should be pointing immediately to the next node that is added right after the first node.
    What you are missing is what I explained above, that when there is only one item in the queue both "front" and "rear" point at the same item. When it does "rear.next = ....." it is also changing what "front.next" points at.

    If all this confuses you I suggest grabbing a pencil and some paper. Draw some boxes to represent the items in the queue and then draw lines from "front" and "rear" to the boxes. Try adding and removing some items and changing where "front" and "rear" point to.

  3. #3
    plasticfood is offline Member
    Join Date
    Sep 2010
    Posts
    32
    Rep Power
    0

    Default

    when i said "point", i meant front's next node value, not the actual front node itself. what i meant was i don't get how front.next was changed from null to the next node without actual code.

    say, you have 4 items in the linked list (A,B,C,D). when A was added, front = rear, so front has a string element and a null node as the next node, right? but when B is added, how did the front.next node became B? only the rear value was changed, and not the front. i guess that's the part i need explaining on.

  4. #4
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,785
    Rep Power
    7

    Default

    As I explained above, when there is only one item in the queue both front and rear point at the same item. When you add a second item and the code updates rear.next it is exactly the same as updating front.next because they point at the same thing.

    I'll use a String example to illustrate. There is an empty queue, both front and rear are null. Add "Hello", both front and rear point at "Hello" and "Hello".next is null. Add "World", update rear.next, since rear points at "Hello" it makes "Hello".next point at "World". Then rear is updated to point at "World". Now you have front pointing at "Hello" and rear pointing at "World" and "Hello".next pointing at "World" and "World.next is null. Add "Woohoo". Update rear.next to point at "WooHoo". Since rear is pointing at "World", "World".next points at "WooHoo" and "WooHoo".next is null. Since front is still pointing at "Hello" you now have a queue(linked list) of front -> "Hello" -> "World" -> "Woohoo" -> null.

    Now do you understand?

  5. #5
    plasticfood is offline Member
    Join Date
    Sep 2010
    Posts
    32
    Rep Power
    0

    Default

    Quote Originally Posted by Junky View Post
    When you add a second item and the code updates rear.next it is exactly the same as updating front.next because they point at the same thing.
    sorry but i still don't understand how front.next was changed. front and rear are both different objects initially pointing at the same thing, ok i get that. when you said "the code updates rear.next it is exactly the same as updating front.next," if so then this is also true when more and more items are added, so with this, front.next is ever changing, and that of course doesn't happen. you're saying front.next changes once the 2nd item is added, how is this possible?? i mean there is no code saying:

    if(items == 2){
    front.next = rear;
    }

    had the code been written like that, then it would make sense to me b/c i can see that front.next has changed to point to the 2nd item in the list. but nowhere in the code updates front.next. that kind of bothers me, and i still don't see how it just magically changed to be pointing to its neighboring item in the list when rear.next was updated. how does rear.next affects front.next?? they're 2 different objects, right? changing one of them shouldn't affect the other, or at least i don't see how it does :(
    Last edited by plasticfood; 05-11-2011 at 04:30 AM.

  6. #6
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,785
    Rep Power
    7

    Default

    I stongly urge you to follow my advice earlier to draw this out on paper with a pencil. this allows you to draw lines between "things" and then erase and redraw those lines when things change. It helps a great deal when you can visually see what is happening.

    when you said "the code updates rear.next it is exactly the same as updating front.next," if so then this is also true when more and more items are added, so with this, front.next is ever changing
    No, it only happens when there is only one item in the queue and both front and rear are pointing at the same item. After "World" is added front is still pointing at "Hello" but rear is now pointing at "World". After this point front and rear never point at the same item again.

  7. #7
    plasticfood is offline Member
    Join Date
    Sep 2010
    Posts
    32
    Rep Power
    0

    Default

    i drew this on paper many times...

    yes i realized that after the 2nd item is inserted, front and rear is pointing at 2 different things. what i am confused about is what front.next is pointing at. front.next should be pointing at rear after the 2nd item, but initially, it was pointing at null. my question is how was that value changed from null to rear without writing any code like i did above?
    Last edited by plasticfood; 05-11-2011 at 04:43 AM.

  8. #8
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,785
    Rep Power
    7

    Default

    OK stop thinking about front.next, all you need to worry about is what front is pointing at. Do you understand everything else about what I said above?

    When the queue is empty front points at null.
    When I added "Hello" a new Node is created. "Hello".next is null.
    Then front and rear are pointed at "Hello".
    Since front points at "Hello" what is front.next? It is null.

    Now I add "World", a new Node is created.
    rear.next = "World". Since rear is pointing at "Hello", "Hello".next = "World"
    rear is now pointed at "World" but front is still pointing at "Hello"
    Now the important question what is front.next?

  9. #9
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,785
    Rep Power
    7

    Default

    I think I have just realised what you misunderstanding is. You are thinking that first is an object (Node). It isn't. It is just a variable that can reference a Node in the queue. The actual Node is the object that contains the word "Hello" and front simply references that Node.

  10. #10
    plasticfood is offline Member
    Join Date
    Sep 2010
    Posts
    32
    Rep Power
    0

    Default

    front.next is world. i get that. i understand the procedure part, i know what the program is supposed to do. i just don't know how it does it. the value of rear.next and rear are constantly changing because there is actual code that changes it (rear.next = new Node(s, null), rear = rear.next). since there is no code for changing front.next in the enqueue method, i just can't see how it was changed (so you're saying changing rear.next also changes what front.next is pointing at, how is this possible???). i know this is getting frustrating, and i appeciate your effort. maybe i am unaware of some things.

    so this is my understanding of the code:

    i know that it supposed to do this:
    (after all 4 nodes are added) those dots don't mean anything, i just needed space
    A > B > C > D > null
    Front.........Rear

    but i think it does this:
    A > null B > C > D > null
    Front...............Rear

    simply b/c of the reasons stated above...
    Last edited by plasticfood; 05-11-2011 at 03:12 PM.

  11. #11
    plasticfood is offline Member
    Join Date
    Sep 2010
    Posts
    32
    Rep Power
    0

    Default

    Quote Originally Posted by Junky View Post
    I think I have just realised what you misunderstanding is. You are thinking that first is an object (Node). It isn't. It is just a variable that can reference a Node in the queue. The actual Node is the object that contains the word "Hello" and front simply references that Node.
    if so, how does changing rear.next affects front.next? they're two different variables, right? how does changing one of them affects the other??

  12. #12
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,785
    Rep Power
    7

    Default

    I have tried explaining this as simply as I can but you are still not getting it. the difficulty maybe doing this over the net. Try talking in person to a tutor or a teacher. I'll try once more.

    You are still worried about how changing rear.next also changes front.next. What you have to realise is that you are not really changing rear.next. You are change "whatever rear points at".next. Since rear and front both point at the same object/Node, they both see the same change. After the second item is added rear is no longer pointing at the same Node as front so front never sees any more changes.

    Take a look at this code:
    Java Code:
    class Foo {
        public String text;
    
        Foo(String t) {
            text = t;
        }
    
        public void setText(String s) {
            text = s;
        }
    }
    
    class Bar {
        public static void main(String[] args) {
            Foo f1 = new Foo("Hello");
            Foo f2 = f1;
            f2.setText("World");
            System.out.println(f1.text);
            System.out.println(f2.text);
        }
    }
    The output will be "World World" and not "Hello World". The reason is both f1 and f2 point at the same object. Using one variable to make a change to the object makes the other variable see the same change. I hope that clears it up. If not I strongly urge you to make time to see the teacher.

  13. #13
    plasticfood is offline Member
    Join Date
    Sep 2010
    Posts
    32
    Rep Power
    0

    Default

    thanks i've talked to my teacher and he explained it. i guess i didn't realize that what they point at is at the same memory address. finally i got it. thanks so much!!

Similar Threads

  1. Replies: 4
    Last Post: 02-21-2011, 09:34 AM
  2. Trouble with circular singly linked queue
    By somewierdguy in forum New To Java
    Replies: 2
    Last Post: 12-06-2010, 01:48 AM
  3. Linked list inside a linked list
    By viperlasson in forum New To Java
    Replies: 5
    Last Post: 07-26-2010, 11:15 PM
  4. Linked Lists Queue
    By bdario1 in forum New To Java
    Replies: 0
    Last Post: 04-28-2010, 04:40 AM
  5. Queue List
    By nahid in forum Advanced Java
    Replies: 4
    Last Post: 10-08-2008, 08:50 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •