## DEV Community is a community of 617,294 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Implement a Queue using a Linked List

Problem Statement: Implement a queue using a linked list with methods like enqueue and dequeue.

What is a Queue?
A Queue is a linear data structure, where the elements are stored in a particular order. It follows the FIFO(First In First Out) order in which the operations are performed.

Test Cases:

1. Enqueue
• Enqueue on an empty queue
• Enqueue on a non-empty queue
2. Dequeue
• Dequeue on an empty queue. --> None
• Dequeue on a non-empty queue. --> value
3. getData
• getData on an empty queue. --> None
• getData on a non-empty queue. --> List of elements in queue

Algorithm:

1. Enqueue
• Create a new node with data
• If head and tail pointers are None,
• set head and tail to new node
• Else,
• set tail to new node.
2. Dequeue
• If the queue is empty,
• return None
• If queue has only one element, i.e head and tail pointers are equal,
• set head and tail value to None
• return value.
• Else,
• return value.
3. getData
• initialise an empty list and a current pointer pointing to head.
• iterate through the queue till current pointer is not None.
• append value to the list at each iteration
• return the list.

Time and Space Complexity

1. Enqueue
• Time: O(1)
• Space: O(1)
2. Dequeue
• Time: O(1)
• Space: O(1)
3. getData
• Time: O(n)
• Space: O(n)
4. Length
• Time: O(n)
• Space: O(1)

Code

``````class Node(object):

def __init__(self, data):
self.data = data
self.next = None

class Queue(object):

def __init__(self):
self.tail = None

def __len__(self):
counter = 0
while curr_node is not None:
counter += 1
curr_node = curr_node.next
return counter

def enqueue(self, data):
node = Node(data)
if self.head is None and self.tail is None:
self.tail = node
else:
self.tail.next = node
self.tail = node

def dequeue(self):
if self.head is None and self.tail is None:
return None
self.tail = None
else:
return data

def getData(self):
data = []
while curr_node is not None:
data.append(curr_node.data)
curr_node = curr_node.next
return data
``````

Unit Test

``````import unittest
from queue import Queue

class TestQueue(unittest.TestCase):
def testEnqueue(self):
print('Test: Enqueue on an empty queue')
qu = Queue()
qu.enqueue(1)
self.assertEqual(qu.getData(), )

print('Test: Enqueue on a non-empty queue')
qu = Queue()
qu.enqueue(2)
qu.enqueue(3)
self.assertEqual(len(qu), 2)
self.assertEqual(qu.getData(), [2, 3])
print('Success: enqueue')

def testDequeue(self):
print('Test: Dequeue on an empty queue')
qu = Queue()
self.assertEqual(qu.dequeue(), None)

print('Test: Dequeue on a non-empty queue')
qu = Queue()
qu.enqueue(1)
qu.enqueue(3)
qu.enqueue(5)
self.assertEqual(len(qu), 3)
self.assertEqual(qu.dequeue(), 1)
self.assertEqual(qu.dequeue(), 3)
self.assertEqual(qu.dequeue(), 5)

print('Success: testDequeue')

def main():
test = TestQueue()
test.testEnqueue()
test.testDequeue()

if __name__ == "__main__":
main()
``````

Github solution repo

Happy Coding !!! 🌟

## Discussion (1)  