Skip to content

Systems and Tech Thoughts

Python Algorithms - Implementing a FIFO Queue Using a Linked List

August 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 implemention 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.

queue operations

An abstract interface to support these methods looksl ike the following:

queue interface

Time Complexity

OperationTime ComplexityDescription
SpaceO(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.
EnqueueO(1)Adding an item to the end of a queue takes the same amount of time complexity regardless of queue size.
DequeueO(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:

node

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

linked list

The list above can be instatiated 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.

Queue Record Keeping

record keeping

Enqueue

enqueue

Dequeue

dequeue

Peek

peek

Size

size


Thank you for reading!


Thoughts on Systems & Tech