Java - issue with assigning Node

Question

I have an interesting situation: When I add a node into a queue, only two nodes added.

Here's how I add nodes into a queue:

Queue queue = new Queue();
Node a = new Node("1");
Node b = new Node("2");
Node c = new Node("3");
Node d = new Node("4");

queue.add(a);
queue.add(b);
queue.add(c);
queue.add(d);

Now, here's the add method:

public void add(Node newNode)
{
    // assigning first Node
    if (head == null){
        head = newNode;
    return;
    }

    // since first Node assigned, assigning second one
    if (head.next == null){
        head.next = newNode;
    }
}

It prints:

1
2

I want to print all of them, but only first two are printed. Also, it is like stack, but FIFO, not LIFO.

Here's the print if it helps:

public void print()
{
    Node p;
    // Display all the nodes in the stack
    for( p = head; p != null; p = p.next )
        p.print();
}

Please let me know if additional info needed. Thanks!

// since first Node assigned, assigning second one. Does that ever change after the 2nd node added? — Sotirios Delimanolis
– Sotirios Delimanolis, Commented Feb 16, 2014 at 6:08
Yes, it should get added all the time when new Node added, not only second one, but third, fourth... — Nurgul Alshyn
– Nurgul Alshyn, Commented Feb 16, 2014 at 6:10
You say assigning second one. How is that assigning third, fourth? — Sotirios Delimanolis
– Sotirios Delimanolis, Commented Feb 16, 2014 at 6:10
That is the mistake, please disregard and take as adder, so that it should add further Node additions. — Nurgul Alshyn
– Nurgul Alshyn, Commented Feb 16, 2014 at 6:12
If your queue already has two elements, it will check the head, not enter the if, then check the second element, and not enter the second if, and exit. You need to somehow always get to the end of the queue, not just to the second element. — trutheality
– trutheality, Commented Feb 16, 2014 at 6:16

Ankur Shanbhag · Accepted Answer · 2014-02-16 06:21:41Z

1

Queue is a FIFO data structure, the first element added to the queue will be the first one to be removed. In a Queue, you add elements from rear end while you remove elements from the head. Every time you add an element, you just need to move the rear pointer, while you remove an element, you need to move the head pointer.

Try this:

public void add(Node newNode)
{
    // assigning first Node
    if (head == null){
        head = newNode;
        rear = newNode;
        return;
    }

    // since first Node assigned, use rear pointer for assignment
    rear.next=newNode;
    rear = newNode;
}

answered Feb 16, 2014 at 6:21

Ankur Shanbhag

7,8042 gold badges31 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Bohemian · Accepted Answer · 2014-02-16 06:20:13Z

1

You need a recursive approach:

public void add(Node newNode) {
    // assigning first Node
    if (next == null) {
        next = newNode;
    } else {
        next.add(newNode); // recursive call
    }
}

This method walks along the chain of nodes until it finds the tail, then adds the node there.

The first call is to the head:

head.add(newNode);

The recursive form of the method will take care of the rest.

You only update the head when you take from the head of the queue - you take the head and update the reference to be head.next.

answered Feb 16, 2014 at 6:20

Bohemian♦

427k103 gold badges603 silver badges750 bronze badges

Comments

DanGar · Accepted Answer · 2014-02-16 06:19:57Z

0

If you look at the code carefully, you are only updating the head and its next pointer.

A solution would be to include a secondary pointer called current where you can update current.next to the newNode and set current to newNode after doing so.

edited Feb 16, 2014 at 6:19

answered Feb 16, 2014 at 6:14

DanGar

3,0781 gold badge20 silver badges17 bronze badges

Comments

Joshua Kissoon · Accepted Answer · 2014-02-16 06:26:30Z

The problem is this code

// since first Node assigned, assigning second one
if (head.next == null){
    head.next = newNode;
}

You're always only going to assign the second node when there isn't a second node, and it won't work for the third node and so on, change it to:

// since first Node assigned, assigning next one
Node x = head;    // Start from head
while(x.next != null){
    x = x.next;   // Find the last node in the queue
}
x.next = newNode;  // Link the new node to the last node

Another simplification is to always keep a pointer to the last node in the queue. So you can replace the above code with:

public void add(Node newNode)
{
    // assigning first Node
    if (head == null){
        head = last = newNode;
        return;
    }

    // since first Node assigned, assigning to end of queue
    last.next = newNode
    last = last.next;
}

This will be much faster

Collectives™ on Stack Overflow

Java - issue with assigning Node

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related