DEV Community

CodeWithML
CodeWithML

Posted on

Implement a Stack using a Linked List

#tutorial #python #computerscience #challenge

Problem Statement: Implement a stack using a linked list with it's functions like push, pop, peek, isEmpty.

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

Test Cases:

  1. Push
    • Push on an empty stack
    • Push on a non-empty stack
  2. Peek
    • Peek on an empty stack --> None.
    • Peek on a non-empty stack --> value.
  3. Pop
    • Pop from an empty stack --> None.
    • Pop from a non-empty stack --> value
  4. isEmpty
    • isEmpty on an empty stack --> True
    • isEmpty on a non-empty stack --> False

Algorithm:

  1. Push
    • Create a new node with data
    • Set next of new node to top
    • Set top to node
  2. Peek
    • if stack is empty,
      • return None
    • else,
      • return value of top
  3. Pop
    • if stack is empty,
      • return None
    • else,
      • save value of top in a temporary variable
      • set top to next of top
      • return temporary variable
  4. isEmpty
    • if top has value,
      • return false
    • else,
      • return true

Time and Space Complexity:

  1. Push
    • Time: O(1)
    • Space: O(1)
  2. Pop
    • Time: O(1)
    • Space: O(1)
  3. Peek
    • Time: O(1)
    • Space: O(1)
  4. isEmpty
    • Time: O(1)
    • Space: O(1)
  5. Length
    • Time: O(n)
    • Space: O(1)

Code

class Node(object): def __init__(self, data, next=None): self.data = data self.next = next class Stack(object): def __init__(self, top=None): self.top = top def __len__(self): curr = self.top counter = 0 while curr is not None: counter += 1 curr = curr.next return counter def pop(self): if self.top is None: return None data = self.top.data self.top = self.top.next return data def push(self, data): self.top = Node(data, self.top) def peek(self): return self.top.data if self.top is not None else None def isEmpty(self): return self.peek() is None
Enter fullscreen mode Exit fullscreen mode

Unit Tests

import unittest from stack import Stack, Node class TestStack(unittest.TestCase): def test_end_to_end(self): print('Test: Empty stack') stack = Stack() self.assertAlmostEqual(len(stack), 0) self.assertEqual(stack.peek(), None) self.assertEqual(stack.pop(), None) print('Test: One element') top = Node(5) stack = Stack(top) self.assertEqual(len(stack), 1) self.assertEqual(stack.pop(), 5) self.assertEqual(stack.peek(), None) print('Test: More than one element') stack = Stack() stack.push(1) stack.push(2) stack.push(3) self.assertEqual(len(stack), 3) self.assertEqual(stack.pop(), 3) self.assertEqual(len(stack), 2) self.assertEqual(stack.peek(), 2) self.assertEqual(stack.pop(), 2) self.assertEqual(len(stack), 1) self.assertEqual(stack.peek(), 1) self.assertEqual(stack.isEmpty(), False) self.assertEqual(stack.pop(), 1) self.assertEqual(len(stack), 0) self.assertEqual(stack.peek(), None) self.assertEqual(stack.isEmpty(), True) print('Success: test_end_to_end') def main(): test = TestStack() test.test_end_to_end() if __name__ == '__main__': main()
Enter fullscreen mode Exit fullscreen mode

Github solution repo

Happy coding !! 🌟

Top comments (0)