CODEWITHSUNDEEP
javalinked-listqueue
user4642421
user4642421

Reputation:

What is the error in the following Queue implementation using linked list?

I wrote the following implementation of the queue using a linked list that does not maintain a reference to the tail node. When I try to print the queue, it outputs only the head i.e. only one node. What is the error? Thanks in advance!

package DataStructures;

import java.util.Scanner;

class Node {
    int x;
    Node nextNode;

    public Node(int x) {
        this.x = x;
        nextNode = null;
    }
}

class Queue {
    Node head = null;
    int n = 0;

    public void enqueue(int x) {
        if (n==0){
            head = new Node(x);
            n++;
            return;
        }
        Node tempHead = head;
        while (tempHead != null){
            tempHead = tempHead.nextNode;
        }
        tempHead = new Node(x);
        tempHead.nextNode = null;
        n++;
    }

    public int dequeue() {
        if (head == null) {
            throw new Error("Queue under flow Error!");
        } else {
            int x = head.x;
            head = head.nextNode;
            return x;
        }
    }

    public void printTheQueue() {
        Node tempNode = head;
        System.out.println("hi");
        while (tempNode != null){
            System.out.print(tempNode.x + "  ");
            tempNode = tempNode.nextNode;
        }

    }

}

public class QueueTest {

    private static Scanner in = new Scanner(System.in);

    public static void main(String[] args) {
        Queue queue = new Queue();
        while (true){
            int x = in.nextInt();
            if (x == -1){
                break;
            } else{
                queue.enqueue(x);
            }
        }

        queue.printTheQueue();
    }

}

Upvotes: 1

Views: 76

Answers (2)

wero
wero

Reputation: 33000

You never assign a node to nextNode, so your list is either empty or consists of one node.

Here is a solution:

public void enqueue(int x) {
    n++;
    if (head == null) {
        head = new Node(x);
    else {
        Node last = head;
        while (last.nextNode != null)
            last = last.nextNode;
        last.nextNode = new Node(x);
    }
}

Technically you don't need n but you could use it as cache for the size of the list. And you should decrease it in deque().

Upvotes: 2

hermit
hermit

Reputation: 1107

Make your enqueue to this:

public void enqueue(int x) {
 if (n==0){
        head = new Node(x);
        head.nextNode=null;
        n++;
        return;
    }
    Node tempHead = head;
    while (tempHead.nextNode!= null){
        tempHead = tempHead.nextNode;
    }
    Node newNode = new Node(x);
    tempHead.nextNode=newNode;
    newNode.nextNode = null;
    n++;
}

Upvotes: 0

Related Questions