Linked list based implementation of queue in Java

Linked list-based implementation of queue

A Queue is an abstract data structure which follows the First In First Out FIFO principle. It means the element which came into the queue first will leave the queue first. This ordering is very helpful in a lot of solutions. Two things are important for a queue: front and rear or tail.

linked list based implementation of queue

A new element is added into the queue at the rear or at the tail, which is called enqueue operation.

queue implemented using linked list
enqueue operation on linked list based queue

The front is the point from where an element of a queue is taken out. This operation is called dequeue operation.

Dequeue operation on queue implemented using linked list

Interface for a queue would be as shown below. This interface can be implemented in multiple ways. There are different ways in which an abstract data structure can be implemented using concrete data structures, for example, a queue can be implemented using arrays or linked lists. Limitation in array-based implementation is that we have to allocate array size beforehand which restricts the number of elements that can be accommodated. Another issue is to correctly tell if the queue is empty or full. We have to maintain an extra counter for that purpose.

package com.company;

/**
 * Created by sangar on 8.10.18.
 */
public interface Queue<E> {
    public ListNode<E> peek();
    public ListNode<E> remove();
    public ListNode<E> enqueue(E data);
    public boolean isEmpty();
    public int size();
}

Let’s discuss how to implement a queue using linked lists.

Single linked list based implementation of queue

A linked list a collection of nodes where each node has two components, first component store the data for the node and second component points to the next node in the linked list. In the last node, the second component points to NULL, which signifies the end of the linked list.

singly linked list based implementation of queue
singly linked list based implementation of queue

If we use a linked list, we solve the first problem of statically allocating memory beforehand for the queue. The linked list is a dynamic data structure, we can allocate memory at the runtime based on our requirements. Also, to find if a queue is empty, check if linked list empty, which is a simple operation to check if the head of linked list NULL.

The time complexity to remove an element out to the singly linked list based queue is O(1), remove the head and make the next node of the head new head. However, to add an element into the singly linked list, we have to go the end of the lists which has a time complexity of O(n).

This problem can be easily be solved by keeping a tail pointer, which points to the last node of the linked list. When we have to enqueue an element in the queue, we update the next of tail to point to the new node and make new node has the tail of the queue. The complexity of enqueue operation is also O(1).

The singly linked list seems to be working for the queue implementation, with dynamic size, dequeue and enqueue operation with O(1) complexity.

One more operation performed on queues to solve certain problems like LRU Cache, non repeated characters in a stream etc. This operation is to delete a random node in queue. Given a random node in the queue, remove that node from the queue.

This problem is tricky in a singly linked list. Brute force solution is to traverse the linked list, go till the previous node and the do the pointer rearrangement and then free the memory of the given node. This operation in the worst case requires O(n) operations. There is a trick method, which is to copy the data of the next node of the given node to the given node and then delete the next node. Caveat to this trick, which I have discussed in delete a node from linked list.

To delete a node from a linked list, two pointers are required: the previous node of the node and the next node of the node. All we do is to make the next pointer of the previous node point to the next node of the given node and free the given node.

Doubly linked list based implementation of queues

From the above discussion, it is easy to guess which type of linked list implementation will give us previous and next node of a given node without traversing the list. It is doubly linked list.

doubly linked list based implementation of queues
doubly linked list based implementation of queues

All the operations remain the same, with same time complexity. With the doubly linked list, delete operation also becomes O(1). So, whenever you have a use case where you may have to delete a random node from the queue, always go for the doubly linked list based implementation. The only overhead is that we have to store double the number of pointers than a singly linked list.

package com.company;

/**
 * Created by sangar on 8.10.18.
 */
public interface Queue<E> {
    public ListNode<E> peek();
    public ListNode<E> remove();
    public ListNode<E> enqueue(E data);
    public ListNode<E> deleteNode(ListNode<E> node);
    public boolean isEmpty();
    public int size();
}
package com.company;

/**
 * Created by sangar on 8.10.18.
 */
public class QueueImplementation<E> implements Queue<E>{
    ListNode<E> head;
    ListNode<E> tail;
    int size;

    public QueueImplementation(){
        head = null;
        tail = null;
        this.size = 0;
    }

    @Override
    public ListNode<E> deleteNode(ListNode<E> node){
        if(this.isEmpty()) {
            return null;
        }

        if(this.head == node){
            if(this.head.getNext() != null) 
                this.head.getNext().setPrev(null);
            this.head = this.head.getNext();
            this.size--;
            return node;
        }

        if(this.tail == node){
            if(this.tail.getPrev() != null)
                this.tail.getPrev().setNext(null);
            this.tail = this.tail.getPrev();
            this.size--;
            return node;
        }
        /*
            We are deleting node in between. So following things happen
            1. If node has prev, set node.prev.next = node.next.
            2. If node has next, set node.next.prev = node.prev
        */
        if(node.getPrev() != null) node.getPrev().setNext(node.getNext());
        if(node.getNext() != null) node.getNext().setPrev(node.getPrev());

        this.size--;
        return node;
    }


    @Override
    public ListNode peek() {
        if(this.isEmpty()) {
            return null;
        }
        return this.head;
    }

    @Override
    public ListNode remove() {
        if(this.isEmpty()) {
            return null;
        }
        /*
            We are deleting node at head. So following things happen
            1. Set temporary node point to head.
            2. Move head to next of node.
            3. Set prev of new head to NULL.
            4. Free the temp node.
          */
        ListNode<E> tempNode = this.head;
        this.head.setPrev(null);
        this.head = this.head.getNext();

        this.size--;
        return tempNode;
    }

    @Override
    public ListNode enqueue(E data) {
        if(this.isEmpty()) {
            this.head = new ListNode<E>(data);
            this.tail = this.head;
            this.size++;
            return this.head;
        }
        ListNode<E> newNode = new ListNode<E>(data,null, this.tail);
        this.tail.setNext(newNode);
        this.tail = newNode;

        this.size++;
        return newNode;
    }

    @Override
    public boolean isEmpty() {
        return this.head == null;
    }

    @Override
    public int size() {
        return this.size;
    }
}

Circular linked list base implementation of queue

Sometimes, the interviewer asks to you solve a trick question like this: Implement queue using only one pointer, either front or rear

The correct answer to it is to use a circular linked list, where the last pointer points back to the head or front pointer. In that case, we will use only the rear pointer.

Enqueue operation:
We create a new node, point the next of new node to the next of tail node, make it next of the tail node and new node becomes the tail node. This whole operation is in constant time, hence the complexity of this operation is O(1).

implementation of queue using only one pointer
implementation of queue using only one pointer
   newNode.next=tail.next; 
   tail.next=newNode;
   tail=newNode; 

Dequeue operation:

   node = tail.next //node to be removed
   tail.next =  node.next // point to the next of front node.

We learned different ways to implement a queue using linked lists. Based on the requirements and constraints of the problem we choose one of the give implementations. To understand more how queues are implemented in Java, please read Queue Implementations

Please share if there is something wrong or missing. If you are preparing for an interview and need personalized coaching to help you with preparation, please book a free session with us.

Constant time max operation on stack

Constant time max operation on stack

We understood stack data structure, operations on it and some examples problems which can be solved using stack. Let’s take problem which is actually based on stack and with the help of other data structures, how can make it more efficient for certain function. Today’s problem is to implement constant time max operation on stack.

To elaborate, you have been given a stack, where elements are pushed and popped randomly. At any given point of time, you have to tell max of all the elements present in stack.
For example : we have stack, we push 5,3,1, current max in stack is 5; we push 6 next, current max is 6 now. How about we pop 6 back. Current max goes back to 5 again.

Constant time max operation: Line of thoughts

Push and pop operation in a stack are already constant time operations. Let’s concentrate on max operation.
If always just pushed on to stack, it would have been easy to just keep track of ma of all the elements we pushed on to stack. However if we are popping out from stack, this may not be as easy. Max will change if the element just popped from stack was current max. What can we do? We keep track of previous max just before the current max. What if next operation is again pop and it pops out the new current max. Again, we have to keep track of previous to previous max.
Are you getting some hint here? We have to keep track of all the max we ever saw while operating on stack in reverse order. That means the max we saw the last, goes out first. LIFO pattern and what better data structure than stack to implement that.

Idea is to have an auxiliary stack which stores all the max seen till a given point of time. Top of this auxiliary stack would be current max. What happens when pop happens on original array? We check if popped element is equal to top element of auxiliary array, that means popped element was current max. So we pop that from auxiliary stack too.

Let’s take an example and see if it works? To start with, both stacks are empty. Now, you add 2 as first element on to stack. Since auxiliary stack is empty, we add 2 on to that stack too.

Push 3 on to stack. Push operation so check if current top of aux stack is less than new element pushed. If yes, push new element to aux stack too.

Push 5 on to stack. Again, push operation and new push element is greater than top of aux stack, we push 5 there too.

Now, push 1. Tricky case. Push 1 on to original stack, but since new element is less than current top of aux stack, nothing gets pushed on aux stack.

Pop from stack now. 1 is popped, it is not equal to current top on aux stack, nothing happens.

Pop from stack again, this time popped element is equal to current max, so we have pop from aux stack too. If we are asked max at this point of time, answer would be 3.

Constant time max operation on stack : Implementation

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 22.9.18.
 */
public class MaxStack {
    Stack<Integer> stack;
    Stack<Integer> auxStack;

    public MaxStack() {
        stack = new Stack();
        auxStack = new Stack();
    }

    public void push(int x) {
        int max = auxStack.isEmpty() ? x : auxStack.peek();
        //Push on max stack only if max value is being changed.
        if (max <= x) auxStack.push(x);
        stack.push(x);
    }

    public int pop() {
        int returnValue = stack.pop();
        //Pop from aux stack only if ax value is being popped out.
        if(auxStack.peek() == returnValue) {
            auxStack.pop();
        }
        return returnValue;
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return auxStack.peek();
    }

    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack();
        while (top() != max) buffer.push(pop());
        pop();
        while (!buffer.isEmpty()) push(buffer.pop());
        return max;
    }
}

Complexity of implementation of constant time max operation stack is O(n) in terms of space, with O(1) time complexity for push, pop and max operation.

Wait, interviewer is not satisfied with this only. What we solve is just reporting the max element in stack at a given point of time. What if we were asked to implement pop max element from stack? Well, first of all finding the max element works as it is. However, popping max element requires popping out all element before max, popping out max and then pushing back all other elements again. Quite a lot of work, even when max operation is O(1).

Which data structure allows us to remove an element in constant time? It’s doubly link list. Once you know which node is to be removed, all we have to do is link previous node to next node. If we implement our original stack as doubly linked list, popping max from stack is O(1) operation without moving any other element on stack.

However finding the node in doubly linked list itself is O(n) operation. Back to square one. What would be helpful is that instead of just storing the max element, we store node address of max in doubly linked list. So in our aux stack, we do not store primitive data type, but a pointer to node which is current max.

Let’s see how it works? We follow the same process of finding the max as explained in earlier solution. It starts with pushing element 2 on to stack. This creates the first node on DLL and stores the pointer on stack.

Now, we push 3 on to stack. Since this is greater than current max being pointed to by top of aux stack, we push that to DLL and store the pointer as max pointer on aux stack.

As for 3, same thing happens when 5 is pushed on to stack.

Since new element pushed is less than current max, it’s pointer is not pushed on to aux stack.
constant time max operation on stack

After pushing 1, we want to pop max. Step 1 would be to fetch the node pointer for current max. Go to that node in doubly linked list. Remove that node from DLL and then remove the pointer from top of stack.

Make a note that whenever, new pushed element is equal to current max, push that on aux stack too. Why?

Let’s see the implementation of this method using doubly linked list.

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 22.9.18.
 */
public class MaxStackDLL {
    private DoubleLinkedList dll;
    private Stack<ListNode<Integer>> auxStack;

    public MaxStackDLL() {
        auxStack = new Stack();
        dll = new DoubleLinkedList();
    }

    public void push(int x) {
        int max = auxStack.isEmpty() ? x : auxStack.peek().getData();
        //Push on max stack only if max value is being changed.
        ListNode<Integer> newNode = dll.insertAtHead(x);
        if (max <= x) auxStack.push(newNode);
    }

    public int pop() {
        ListNode<Integer> returnValue = dll.deleteAtHead();

        //Pop from aux stack only if ax value is being popped out.
        if(auxStack.peek() == returnValue) {
            auxStack.pop();
        }
        return returnValue.getData();
    }

    public int peekMax() {
        return !auxStack.isEmpty() ? auxStack.peek().getData() : -1;
    }

    public int popMax() {
        return auxStack.isEmpty() ? -1 : dll.deleteNode(auxStack.pop()).getData();
    }
}

Doubly linked list class is as follows

package com.company;

/**
 * Created by sangar on 22.9.18.
 */
public class DoubleLinkedList {

    ListNode<Integer> head;

    public DoubleLinkedList(){
        head = null;
    }

    public boolean isEmpty(){
        return this.head == null;
    }

    public ListNode<Integer> insertAtHead(int data){
        if(this.isEmpty()) {
            this.head = new ListNode<Integer>(data);
            return this.head;
        }
        /*
            We are inserting node at head. So following things happen
            1. Create a new node.
            2. Set next of new pointer to current head.
            3. Set prev of head to new node
            4. Make new node as head of linked list
          */
        //First two steps are done here
        ListNode<Integer> newNode = new ListNode<Integer>(data,this.head, null);
        //Step 3.
        this.head.setPrev(newNode);
        //Step 4.
        this.head = newNode;

        return this.head;
    }

    public ListNode<Integer> deleteAtHead(){
        if(this.isEmpty()) {
            return null;
        }
        /*
            We are deleting node at head. So following things happen
            1. Set temporary node point to head.
            2. Move head to next of node.
            3. Set prev of new head to NULL.
            4. Free the temp node.
          */
        ListNode<Integer> tempNode = this.head;
        this.head = this.head.getNext();
        this.head.setPrev(null);

        return tempNode;
    }

    public ListNode<Integer> deleteNode(ListNode<Integer> node){
        if(this.isEmpty()) {
            return null;
        }
        /*
            We are deleting node in between. So following things happen
            1. If node has prev, set node.prev.next = node.next.
            2. If node has next, set node.next.prev = node.prev
        */
        if(node.getPrev() != null) node.getPrev().setNext(node.getNext());
        if(node.getNext() != null) node.getNext().setPrev(node.getPrev());

        return node;
    }
}

ListNode class is as follows

package com.company;

/**
 * Created by sangar on 22.9.18.
 */
public class ListNode<T> {
    private T data;

    private ListNode<T> next;
    private ListNode<T> prev;

    public ListNode(T data){
        this.data = data;
        next = null;
        prev = null;
    }

    public ListNode(T data, ListNode<T> next, ListNode<T> prev){
        this.data = data;
        this.next = next;
        this.prev = prev;
    }

    public ListNode<T> getNext(){
        return this.next;
    }

    public ListNode<T> getPrev(){
        return this.prev;
    }

    public void setPrev(ListNode<T> newNode){
        this.prev = newNode;
    }

    public void setNext(ListNode<T> newNode){
        this.next = newNode;
    }

    public T getData(){
        return this.data;
    }
}

Tester class is given below. Can you add more test cases to this?

package test;

import com.company.MaxStackDLL;
import org.junit.jupiter.api.Test;

import static org.junit.Assert.assertEquals;

/**
 * Created by sangar on 22.9.18.
 */
public class MaxStackTest {


    MaxStackDLL tester = new MaxStackDLL();
    @Test
    public void popMaxTest() {

        tester.push(2);
        tester.push(3);
        tester.push(5);
        tester.push(1);

        assertEquals(5, tester.popMax());
        assertEquals(3, tester.popMax());
    }
}

Time complexity of push, pop and popMax is O(1). There is additional space requirement which is O(n).

Please share if there is something wrong or missing. If you are interested in taking personalized coaching by our experienced coaches, please reach out to us at communications@algorithmsandme.com

Binary tree to doubly linked list conversion

Binary tree to doubly linked list conversion

This is very commonly asked problem in Amazon and Google interview question. It checks your understanding of binary tree and doubly link list data structures, their traversals and creation. In a binary tree, a node has two pointers, one point to the left child of the node and other points to the right child of the node. Similarly, in a doubly linked list, a node contains two pointers, one point to the next node and other points to the previous node of the current node. Given a binary tree, how can we convert the binary tree to a doubly linked list? To make the problem clear, let’s take an example.

convert binary tree to dll
Binary tree to doubly linked list conversion

Output should be

convert binary tree to doubly linked list
Doubly linked list from binary tree

Binary tree to a doubly linked list: Line of thought

The first question you should be asking is which node should be the head of the doubly linked list? If the leftmost node in the binary tree is to be head, you need to traverse a tree in inorder. However, if the root node has to be the head node, then you should do preorder traversal.

This question could be great started as it shows your understanding of tree traversals.

Let’s say our problem is to have inorder traversal. If a binary tree is binary search tree, the interviewer can just tell you to provide the output as a sorted list, which is another way of saying inorder traversal.

To convert a binary tree to a doubly linked list, at each node, the previous pointer will point to the inorder predecessor of the node whereas next pointer points to inorder successor of the node. We have left and right pointers already in the node, use them as previous and next pointer respectively.
Now, problem is to keep track of inorder successor and predecessor of the node. To keep track of inorder predecessor, store the previous node of the current node visited throughout traversal. We would link the left child to the inorder predecessor.
How to keep find the inorder successor of a node, if the node is left child of some node, the inorder successor would be parent node. At the parent node, it would be the leftmost child of the right child if it exists. This is not scary as it sound, inorder successor part is automatically implemented if we do the recursive inorder traversal of the tree.

There is one special case to handle, which is the leftmost node. This node will be head of the doubly linked list and there is no previous node to link it’s left to. 

This whole problem is a complex version of inorder traversal of a binary tree, but at the end, it is inorder traversal. We can first write the generic inorder traversal and then modify the process step to suit our needs.

    private void inorder(Node root){
        if(root == null) return;

        if(root.left != null) inorder(root.left);
        process(root);
        if(root.right != null) inorder(root.right);
    }

We have to modify this to send previous node, where root connects it’s left child in process step and head, which is set only once, to store the head of result doubly linked list.

private void inorder(Node root, Node prev, Node head){
        if(root == null) return;

        if(root.left != null) inorder(root.left);
        process(root, prev,head);
        if(root.right != null) inorder(root.right);
    }

What we have to do in process step? If the current node is the leftmost node, we will set that head of the doubly linked list. If the previous node is null yet, that means, we have it the leftmost node.
What if the previous node is not null, in that case, we have already created or assigned head of the doubly linked list, and the previous node points to the last node of the doubly linked list. It means we have to link right pointer of the previous node to the current node.
Set left pointer of the current node to the previous node irrespective of the previous node. The last step would update the previous with the current node.

private void process(TreeNode root, TreeNode prev, TreeNode head){
	if(prev == null){
		head = root;
	}
	else{
		prev.setRight(root);
	}
	root.setLeft(prev);
	prev = root;
}

The only problem is that if we are implementing the process function Java, we cannot change the value of pointer because Java passes arguments as pass-by-value rather than pass-by-reference. In short, even though head and previous pointers are updated in process function, the change would not be reflected in the calling function. To handle this, we will create a mutable static class with two members called head and previous and pass it to process function. Why this method works, please refer  :  pass-by-value and pass-by-reference in java

    private void process(TreeNode root, Context context){
        if(context.prev == null){
            context.head = root;
        }
        else{
            context.prev.setRight(root);
        }

        root.setLeft(context.prev);
        context.prev = root;
    }

An algorithm to convert a binary tree to a doubly linked list

  1. Start from root node, currentNode.
  2. If currentNode->left != NULL, currentNode = currentNode->left. (Moving down the tree on the left side)
  3. At this point we are at the left most node, check if previous == NULL.
    1. If previous is NULL, then this node has to be the head node.
    2. Mark currentNode as head and currentNode->left = previous = NULL.
  4. previous = currentNode.
  5. Traverse up the tree in inorder traversal.
    1. previous->right = currentNode.
    2. currentNode->left = previous
    3. previous = currentNode
  6. If currentNode->right != NULL, currentNode = currentNode->right and go to step 2.

Convert Tree to DLL : implementation in Java

package com.company.BST;

/**
 * Created by sangar on 21.10.18.
 */
public class TreeToDLL {

    public static class Context {
        public TreeNode head;
        public TreeNode prev;
    }
    
    private void process(TreeNode root, Context context){
        if(context.prev == null){
            context.head = root;
        }
        else{
            context.prev.setRight(root);
        }

        root.setLeft(context.prev);
        context.prev = root;
    }

    public void treeToDllRecursion(TreeNode root, Context context){

        if(root == null) return;

        if(root.getLeft() != null) {
            treeToDllRecursion(root.getLeft(),context);
        }

        process(root,context);

        if(root.getRight() != null)
			treeToDllRecursion(root.getRight(), context);
    }
}

Definition of TreeNode and BinarySearchTree is given below.

package com.company.BST;

/**
 * Created by sangar on 21.10.18.
 */
public class TreeNode<T> {
    private T value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(T value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public T getValue(){
        return this.value;
    }
    public TreeNode getRight(){
        return this.right;
    }
    public TreeNode getLeft(){
        return this.left;
    }

    public void setValue(T value){
        this.value = value;
    }

    public void setRight(TreeNode node){
        this.right = node;
    }

    public void setLeft(TreeNode node){
        this.left = node;
    }
}
package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree<T> {

    private TreeNode<T> root;

    public void BinarySearchTree(){
        root = null;
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private TreeNode insertNode(TreeNode root, int value){
        if(root == null){
            //if this node is root of tree
            root = new TreeNode(value);
        }
        else{
            if((int)root.getValue() > value){
                /*If root is greater than value,
				node should be added to left subtree */
                root.setLeft(insertNode(root.getLeft(), value));
            }
            else{
                /*If root is less than value,
				node should be added to right subtree */
                root.setRight(insertNode(root.getRight(), value));
            }
        }
        return root;
    }
    
    public TreeNode getRoot(){
        return this.root;
    }

    public void setRoot(TreeNode node){
        this.root = node;
    }
  }

Binary search tree to DLL conversion : C implementation

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

struct node{
        int value;
        struct node *left;
        struct node *right;
};
typedef struct node Node;

void treetoListRec(Node * node, Node ** prev, Node **ptrToHead){
        if(node == NULL)
                return;
        /* Go to left most child */
        if(node->left)
                treetoListRec(node->left, prev, ptrToHead);

        /* If this wasn't the first node being added to list*/  
        if(*prev!= NULL){
                (*prev)->right = node;
        }
        else{
                 *ptrToHead = node; 
         }
        /*make left pointer point to last node, and update the 
          last node to current*/

        node->left = *prev;
        *prev= node;

        /* If there is right child, process right child */
        if(node->right)
                treetoListRec(node->right, prev, ptrToHead);

}
Node * createNode(int value){
        Node * newNode=  (Node *)malloc(sizeof(Node));
        newNode->value = value;
        newNode->right = NULL;
        newNode->left = NULL;
        return newNode;
}
Node * addNode(Node *node, int value){
    if(!node)
        return create_node(value);
    else{
        if (node->value > value)
            node->left = addNode(node->left, value);
        else
            node->right = addNode(node->right, value);
    }
    return node;
}
 
/* Driver program for the function written above */
int main(){
        Node *root = NULL;
        Node * prev = NULL;
        Node *ptrToHead = NULL;
        //Creating a binary tree
        root = addNode(root,30);
        root = addNode(root,20);
        root = addNode(root,15);
        root = addNode(root,25);
        root = addNode(root,40);
        root = addNode(root,37);
        root = addNode(root,45);
        
        treetoListRec(root,&prev, &ptrToHead);
        
        return 0;
}

This requires traversal of each node at least once, hence complexity analysis is O(N).

Note

There is one method , which takes into consideration that the whole problem can be divided into sub-problems involving left sub tree and right sub tree, once these sub problems are solved, we can combine solutions of these to come up with the solution of the bigger problem.

Basic idea is to convert left sub binary tree to doubly linked list, then convert right sub binary tree to doubly linked list and join both the lists with root in between. Idea is very well explained here

Please share if there is something missing or wrong. If you want to contribute to website, please reach out to us on communications@algorithmsandme.com