Stack using linked List I have this problem with my interview. I was asked to implement a stack using a linked list.

Gist

#!python

from linkedlist import LinkedList


# Implement LinkedStack below, then change the assignment at the bottom
# to use this Stack implementation to verify it passes all tests
class LinkedStack(object):

    def __init__(self, iterable=None):
        """Initialize this stack and push the given items, if any."""
        # Initialize a new linked list to store the items
        self.list = LinkedList()
        if iterable is not None:
            for item in iterable:
                self.push(item)

    def __repr__(self):
        """Return a string representation of this stack."""
        return 'Stack({} items, top={})'.format(self.length(), self.peek())

    def is_empty(self):
        """Return True if this stack is empty, or False otherwise."""
        return self.list.is_empty()
        # TODO: Check if empty

    def length(self):
        """Return the number of items in this stack."""
        return self.list.size
        # TODO: Count number of items

    def push(self, item):
        """Insert the given item on the top of this stack.
        Running time: O(1) – Just does an append, which is O(1)"""
        self.list.append(item)

def peek(self):
    """Return the item on the top of this stack without removing it,
    or None if this stack is empty."""
    if self.is_empty():
        return
    return self.list.get_at_index(self.length() - 1)

def pop(self):
    """Remove and return the item on the top of this stack,
    or raise ValueError if this stack is empty.
    Running time: O(n) – It will always loop through whole list before
    finding the item at the end"""
    if self.is_empty():
        raise ValueError("Cannot pop from an empty stack")
    item = self.peek()
    self.list.delete(item)
    return item


My code passed the following 6 tests. I make sure that my code works a pretty comprehensive following unit test cases, and it passed against all test cases, so the code seems to be working fine.

#!python

from LLstack import Stack
import unittest


class StackTest(unittest.TestCase):

    def test_init(self):
        s = Stack()
        assert s.peek() is None
        assert s.length() == 0
        assert s.is_empty() is True

    def test_init_with_list(self):
        s = Stack(['A', 'B', 'C'])
        assert s.peek() == 'C'
        assert s.length() == 3
        assert s.is_empty() is False

    def test_length(self):
        s = Stack()
        assert s.length() == 0
        s.push('A')
        assert s.length() == 1
        s.push('B')
        assert s.length() == 2
        s.pop()
        assert s.length() == 1
        s.pop()
        assert s.length() == 0

    def test_push(self):
        s = Stack()
        s.push('A')
        assert s.peek() == 'A'
        assert s.length() == 1
        s.push('B')
        assert s.peek() == 'B'
        assert s.length() == 2
        s.push('C')
        assert s.peek() == 'C'
        assert s.length() == 3
        assert s.is_empty() is False

    def test_peek(self):
        s = Stack()
        assert s.peek() is None
        s.push('A')
        assert s.peek() == 'A'
        s.push('B')
        assert s.peek() == 'B'
        s.pop()
        assert s.peek() == 'A'
        s.pop()
        assert s.peek() is None

    def test_pop(self):
        s = Stack(['A', 'B', 'C'])
        assert s.pop() == 'C'
        assert s.length() == 2
        assert s.pop() == 'B'
        assert s.length() == 1
        assert s.pop() == 'A'
        assert s.length() == 0
        assert s.is_empty() is True
        with self.assertRaises(ValueError):
            s.pop()


if __name__ == '__main__':
    unittest.main()
.pop() in a stack can be \$O(1)\$ with a proper implementation of linked list.