Stack implementation with singly linked list

Question

The following is my implementation of a stack using a linked list.

class EmptyStackError(Exception):
    def __init__(self):
        super().__init__("Stack is empty: Invalid Operation!")


class LinkedList:
    class _Node:
        def __init__(self, data, next_node=None):
            self.data = data
            self.next_node = next_node


    def __init__(self):
        self._head = None
        self._tail = None

    def add_first(self, data):
        """ Add data to the beginning of the linked list"""
        node = self._Node(data)
        if not self._head and not self._head:
            self._head = self._tail = node
            return
        node.next_node = self._head
        self._head = node

    def add_last(self, data):
        """ Add data to the end of the linked list """
        node = self._Node(data)
        if not self._head and not self._tail:
            self._head = self._tail = node
            return
        self._tail.next_node = node
        self._tail = node

    def remove_last(self):
        """ Remove the last element in the linked list """
        if not self._head and not self._tail:  # if linked list is empty
            raise EmptyStackError
        elif self._head is self._tail:  # if only one element
            data = self._head.data  # or data of tail
            self._head = self._tail = None
            return data
        data = self._tail.data
        current = self._head
        while current.next_node.next_node:
            current = current.next_node
        current.next_node = None
        self._tail = current
        return data

    def remove_first(self):
        """ Remove the first element in the linked list """
        if not self._head and not self._tail:  # if linked list is empty
            raise EmptyStackError
        elif self._head is self._tail:  # if only one element
            data = self._head.data
            self._head = self._tail = None
            return data
        data = self._head.data
        self._head = self._head.next_node
        return data

    def __str__(self):
        if not self._head and not self._tail:
            return "Stack is empty!!"
        items = []
        current = self._head
        while current:
            items.append(current.data)
            current = current.next_node
        return " ".join([str(i) for i in items])


class Stack:
    """ A stack implementation using a linked list

    Note: The reason add_first and remove_first are using for push and pop respectively is to keep them O(1).
          If adding and removing last were used, then remove last would O(n).
          This is because deleting the tail would require the traversal of the linked list to delete the last element.
    """
    def __init__(self):
        self.items = LinkedList()

    def push(self, data):
        self.items.add_first(data)

    def pop(self):
        data = self.items.remove_first()
        return data

    def peek(self):
        data = self.items.remove_first()
        self.items.add_first(data)
        return data

    def __str__(self):
        string = self.items.__str__()
        return string

Is there anything I need to improve? whether it's style or logic.

Can you find any bugs? Whether in the linked list or the stack.

My basic tests:

import pytest

def test_push():
    """ This is depending on another method """
    stack = Stack()
    stack.push(5)
    assert stack.peek() == 5

def test_pop():
    stack = Stack()
    stack.push(5)
    data = stack.pop()
    assert data == 5

def test_empty_pop():
    stack = Stack()
    with pytest.raises(EmptyStackError):
        stack.pop()

def test_peek():
    stack = Stack()
    stack.push(5)
    assert stack.peek() == 5

def test_empty_peek():
    stack = Stack()
    with pytest.raises(EmptyStackError):
        stack.peek()

test_push()
test_pop()
test_empty_pop()
test_peek()
test_empty_peek()

Answer 1

1. You have a typo/mistake in if not self._head and not self._head, I think you wanted to write self._tail in one of them.
2. I do not see the interest of making Node() inner to LinkedList(). In opposite, doing so condemns you not to reuse the Node() code and slaughters your code scalability (in case you will need to add functionality to your code by implementing a queue, for example)

3. You can refactor this code into one function and call it when necessary:

   if not self._head and not self._head:
       self._head = self._tail = node
       return
   

4. While it apparently does the job, the return statement of your code in (3) is not in the right place. You should remove it and use the if ... else statements instead because this makes sense and that is what the reader of your code may expect.
5. Here, we can use more common sense: if not self._head and not self._tail: honestly, if the head is None, it must be obvious the tail is in the same condition. I mean you can replace similar lines to simply: if not self._head
6. You said you want to code a stack: by definition, in a stack, we need only a pointer to its head. The head is the tail, and the tail is the head because that is where operations occur.
7. Do not code what you do not need: it is unnecessary to use add_last() and remove_last(). Why? Because you are coding a stack, and a stack follows the principle of LIFO, so do not care about the other end at all. In a stack, we need to perform the push and pop operations; at best, we would like to know its size, everything else does not belong to the stack notion.
8. The points (6) and (7) are a gentle introduction to what I will tell you here: you misunderstood the stack implementation: we can implement a stack using an array or a simple linked list. You chose the later one but you misunderstood it because you lost yourself in implementing a linked list and you ended up by missing the notion of the stack.

If you carefully read this section, for example, you will understand that stack implementation using linked lists does not require you to implement a linked list and its different operations but simply having a data structure which looks like a node that belongs to a linked list, and by designing the pop and push operations, your stack will look, by default, as a singly linked a list. So based on your code, let me share with you the right way to implement a stack based on linked lists:

class EmptyStack(Exception):
    def __init__(self):
        super().__init__('Stack is empty: invalid operation!')

class Node:

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

class Stack:

    def __init__(self):
        self.head = None
        self.size = 0

    def get_size(self):
        return self.size

    def push(self, item):
        self.node = Node()
        self.node.data = item
        self.node.next = self.head
        self.head = self.node
        self.size += 1

    def pop(self):
        if self.head == None:
            raise EmptyStack
        self.head_item = self.head.data
        self.head = self.head.next
        self.size -= 1
        return self.head_item



if __name__ == '__main__':
    stack = Stack()
    for i in range(10):
        stack.push(i)
    print('size: {}'.format(stack.get_size()))
    print(stack.pop())
    print(stack.get_size())