Queue implementation is using underlying data structures (linked list, array) to implement enqueue and dequeue. A queue is a First-In-First-Out (FIFO) data structure. New elements are inserted at the rear (enqueue), and existing elements are removed from the front (dequeue). Both enqueue and dequeue operation have O(1) complexity.

queue implementation

In this post, the linked list is used to implement a queue. A linked list is preferred because it is flexible to add and remove elements.  Array is not recommended because it wastes a lot of space if there are many adds and removes. However, an array can be efficient in implementing a circular queue. Deque is a queue that can be enqueued and dequeued at both ends. It is implemented in a doubly linked list.

Table of Content


You are here

you are here

Part 1 – Queue implementation with linked list
Part 2 – Circular queue implementation with array
Part 3 – Circular queue as circular linked list
Part 4 – Deque as doubly linked list


Enqueue

Using a linked list, first, we need to define a queue node. This class has variables of data and next. Next, we define the queue class. It has three class variables: front, rear, and length. The front is a pointer to the first node. The rear is a pointer to the last node. The length is to track the length of the list.

The enqueue operation is to add an element at the rear. If the queue is empty, we point both front and rear to the new node. If it is not empty, we simply add the new node to the rear.

Java

Javascript

Python

Doodle

queue with linked list


Dequeue

The dequeue operation is to remove the first node from the queue. First, we check whether the queue is empty. If it is empty, the method should return. In this implementation, we simply move the front pointer to the next node. The “removed” node is still in the list without being accessible until the linked list is removed from the memory.

Java

Javascript

Python


Peek

Peek is to return the value of the first node. The same as dequeue, we should check whether the queue is empty. If it is not empty, return the value.

Java

Javascript

Python


Print

Print is to print all elements in the queue. Starting from the front node, a while loop is used to iterate through each node till to the rear in the list.

Java

Javascript

Python


Free download

Download queue implementation using linked list in Java, JavaScript and Python
Data structures and Java collections

What data structures can be used to implement a queue?

A queue is an abstract data type (ADT), meaning its underneath data structures and implementations are not visible to the outside. In theory, data structures to implement a queue are arrays, linked lists, or stacks. Using an array is not space-efficient. A linked list is preferred because it is flexible to add and remove elements.