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.

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

Time Complexity

Operation	Time Complexity	Description
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 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

Enqueue

Dequeue

Peek

Size

Thank you for reading!