Python Algorithms — Implementing a FIFO Queue Using a Linked List

Published in

Dm03514 Tech Blog

3 min readAug 29, 2021

Queues are commonly used to lineup work to be done. Consider a queue at a store. The first person in line is the first to be serviced. This is referred to as a “first in first out queue” (FIFO). This post details an implementation of a FIFO queue using a linked list. This post hopes to be a useful algorithm interview study reference. All code is available on github at dm03514/python-algorithms.

Queues

Queues support the following methods:

Enqueue: Adds an item to the end of the queue.
Dequeue: Removes an item from the beginning of the queue.
Peek: Returns the item from the beginning of the queue, without modifying the queue.
Size: Returns the length of the enqueued items.

An abstract interface to support these methods looks like the following:

Time Complexity

Space — O(n): The queue requires space proportional to the size of the queue. 10 item queue will require 10 items worth of space, and a 75 item queue will require 75 items worth of space.
Enqueue — O(1): Adding an item to the end of a queue takes the same amount of time complexity regardless of queue size.
Dequeue — O(1): Removing an item to the end of a queue takes the same amount of time complexity regardless of queue size.

Implementation

The core of the linked list based queue is the concept of the linked list. In a linked list each item (or node) contains a reference to the next item in the list:

This allows a list to be built up like the following:

The list above can be instantiated directly using the Node class, or built up over time. The following shows how to instantiate the linked list directly:

Node(  value='first',  next=Node(    value='second',    next=Node(      value='third    )  ))

The linked list does all the heavy lifting. The rest of the queue implementation is wrappers around the linked list and some record keeping to track the head, tail, and size of the linked list.