Implement a Stack using a Linked List

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

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()

Github solution repo

Happy coding !! 🌟