Writing dequeue() function by traversing linked list in Java

Question

A queue is implemented using a singly linked list.

The variable back "points" at the first node in the linked list. New elements are added (enqueued) at the back.

The variable front "points" at the last node in the linked list. Elements are removed (dequeued) from the front.

This implementation is the opposite of a usual queue where the back is the last node and the front is the first node. I know this is not a good way of implementing a queue, but it is good practice coding with linked lists.

I have written the enqueue() function however am not sure what I am doing wrong with the dequeue(). I have to get to the front, which is the last node, to dequeue it. So I must traverse the Node to remove and return the item at the front of the queue.

 //Node stuff
private Node front, back;
static class Node {
    public Node (char item, Node next) { this.item = item; this.next = next; }
    public char item;
    public Node next;
    }

dequeue function: needs work

public char dequeue() {

    char item;

    if (back.item == front.item) {
    item = front.item; 
    back = null;
    }
    for (Node tmp = back; tmp != null; tmp= tmp.next){
    if (tmp.next == null){ 
        item = tmp.item; 
        back.next = null; 
    }
    }
    return item; 
}

I created a char to store the value of the item I am going to remove...My problem is removing the last node from the list. I am not sure how to do it without getting a Null Pointer Exception. Any input would be much appreciated!

FYI: A singly linked list is a lousy data structure for implementing a queue, since you need access to both the head and the tail. Unless this is an exercise/assignment in futility, just to see if you can do it, you should use a doubly linked list, otherwise performance will be bad. — Andreas

ethandjay ethandjay · Accepted Answer · 2020-02-27T20:55:56

The if conditions fires when you're at the last node, in which case you want to save that node's value and remove it from the list. You're saving the value, but then why are you setting back.net to null? Wouldn't you want to set the previous tmp node's next to null? Wouldn't setting back.next to null sever the whole list?

And sorry for that first comment, guy clearly didn't read your question. StackOverflow, amiright?

Writing dequeue() function by traversing linked list in Java

1 Answers