DEV Community

loading...

Implement a Queue using a Linked List

codewithml profile image CodeWithML ・2 min read

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,
      • save head's value
      • set head and tail value to None
      • return value.
    • Else,
      • save head's value.
      • set head to next of head.
      • 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.head = None
        self.tail = None

    def __len__(self):
        counter = 0
        curr_node = self.head
        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.head = node
            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
        data = self.head.data
        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
        return data

    def getData(self):
        data = []
        curr_node = self.head
        while curr_node is not None:
            data.append(curr_node.data)
            curr_node = curr_node.next
        return data
Enter fullscreen mode Exit fullscreen mode

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(), [1])

        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()
Enter fullscreen mode Exit fullscreen mode

Github solution repo

Happy Coding !!! 🌟

Discussion (1)

pic
Editor guide
Collapse
paddy3118 profile image
Paddy3118

Remember that it's CS. Understanding over use. If given a restricted environment in maybe a strange language, then it allows recognition. If you were coding at a higher level and needed a queue then you would never implement on top of a linked list in Python for example.