Data structures and algorithms in Java

In the previous post I discussed about queue implementation using circular array. Queue can also be implemented using linked list to overcome the disadvantages of the queue implementation using array. This post discusses how queue implementation using linked list gives better performance and reduces the overhead of shifting the elements to the left, every time an element is dequeued from the queue.

Prerequisites:

Knowledge of Java, basic data structures, working of queue, linked list and understanding of time and space complexity.

Explanation:

In the queue implementation using array, a major drawback is when an element is dequeued from the front of the array, all the elements have to be shifted to the left by 1 position. This works well when the number of elements is small. But when the number of elements stored in the array becomes large it can give poor performance.

To solve the above problem, queue can be implemented using linked list. The enqueue operation is performed at the tail end of the linked list and dequeue is performed at the head end of the linked list. Two node pointers front and rear is maintained at the head and at the tail end of the linked list.

Operations that can be performed:

1. enqueue(int data): This operation is used to enqueue an element to the rear end of the linked list.
2. dequeue(): This operation is used to dequeue en element from the front of the linked list.
3. display(): This method is used to display all the queue elements by iterating over the elements.

Algorithm:

1. Declare a QueueNode class with data as an integer variable which will hold the data of a queue node and a next pointer of type QueueNode which will point to the next node in the queue.
2. To enqueue an element, a new node is created and attached to the rear end of the queue.
3. To dequeue an element, a node is removed from the front end of the queue.

Diagrammatic representation:

Code implementation:

public class QueueUsingLinkedList {

	QueueNode front;
	QueueNode rear;

	// constructor to initialize front and rear pointers
	QueueUsingLinkedList() {
		this.front = null;
		this.rear = null;
	}

	// QueueNode class representing a node in the linked list
	static class QueueNode {
		int data;
		QueueNode next;

		QueueNode(int val) {
			this.data = val;
			next = null;
		}

	}

	/* method to add a new element to the queue */
	void enqueue(int data) {

		QueueNode newNode = new QueueNode(data);

		// inserting the first element
		if (rear == null) {
			rear = newNode;
			front = rear;

		} else {
			// attach the new node at the rear end and update rear pointer
			rear.next = newNode;
			rear = newNode;
		}
		System.out.println("Element enqueued = " + rear.data);
	}

	/* method to remove an element from the queue */
	void dequeue() {
		if (rear == null) {
			System.out.println("Queue is empty. Cannot dequeue element.");
		} else {
			System.out.println("Element dequeued = " + front.data);
			front = front.next;

			// if this was the only node
			if (front == null) {
				rear = null;
			}
		}
	}

	/* method to display all elements of the queue */
	void display() {
		QueueNode temp = front;
		System.out.print("Queue elements are = ");
		while (temp != null) {
			System.out.print(temp.data + " ");
			temp = temp.next;
		}
		System.out.println();

	}

	public static void main(String[] args) {
		QueueUsingLinkedList q = new QueueUsingLinkedList();
		q.enqueue(1);
		q.enqueue(2);
		q.enqueue(3);
		q.enqueue(4);
		q.enqueue(5);
		q.dequeue();
		q.dequeue();
		q.dequeue();
		q.enqueue(6);
		q.display();
		q.dequeue();
		q.dequeue();
		q.dequeue();
		q.dequeue();

	}

}

Code output:

Element enqueued = 1
Element enqueued = 2
Element enqueued = 3
Element enqueued = 4
Element enqueued = 5
Element dequeued = 1
Element dequeued = 2
Element dequeued = 3
Element enqueued = 6
Queue elements are = 4 5 6
Element dequeued = 4
Element dequeued = 5
Element dequeued = 6
Queue is empty. Cannot dequeue element.

Time and space complexity:

Time complexity of enqueue and dequeue operations is constant i.e. O(1), since only the rear and front pointers need to be updated and no iteration is performed over the elements.

Time complexity of display operation is O(N) where N = number of elements in the queue, since all the elements of the queue are iterated.

Space complexity = O(1) since no extra or any auxiliary space is used for the above operations.

Link to the above code on my github profile, Queue using linked list.

Thank you for reading. You feedback is highly appreciated.