Stack implementation with singly linked list

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;







up vote
4
down vote

favorite












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






share|improve this question



























    up vote
    4
    down vote

    favorite












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






    share|improve this question























      up vote
      4
      down vote

      favorite









      up vote
      4
      down vote

      favorite











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






      share|improve this 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()








      share|improve this question












      share|improve this question




      share|improve this question








      edited Apr 29 at 7:39









      Billal BEGUERADJ

      1




      1









      asked Apr 28 at 20:15









      MAA

      5716




      5716




















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          3
          down vote



          accepted










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





          share|improve this answer



















          • 1




            'simply linked list': did you mean 'singly'?
            – Daniel
            Apr 29 at 8:41






          • 1




            Both notions are used in the litterature and they are both correct, but there is a typo I guess, 'simple' not 'simply', so thank you@Coal_
            – Billal BEGUERADJ
            Apr 29 at 8:44










          • Great great answer. Points 1, 2, 3 were right on the money. Point 4 is because I love early exit from functions, but you are right. The code is readable when replacing the return with if else. I did not do it for remove_last though. A while loop inside an else statement makes me uncomfortable :). For point 5, I knew that when I wrote it. I just overdid it with both checks just as a form of catching myself making mistakes in moving the tail and head nodes during other operations
            – MAA
            Apr 29 at 21:00










          • You are also quite correct in points 6, 7 and 8. I kinda did them on purpose since I wanted to write a linked list anyways. But I should have removed them from the code I've posted here.
            – MAA
            Apr 29 at 21:02






          • 2




            Now everything after 8 surprised me. I always thought implementing a stack with linked list meant creating a linked list class. I noticed when I was done with the Stack class that I did not do anything stack-related. All of my code was for the linked list. I found it odd, but carried on. Now that I see your implementation, I get it. The simplicity of it and the fact that it's actually the stack logic I wanted to practice makes me appreciate your answer even more. Thank you Begueradj. I truly appreciate your time.
            – MAA
            Apr 29 at 21:06










          Your Answer




          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ifUsing("editor", function ()
          StackExchange.using("externalEditor", function ()
          StackExchange.using("snippets", function ()
          StackExchange.snippets.init();
          );
          );
          , "code-snippets");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "196"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          convertImagesToLinks: false,
          noModals: false,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );








           

          draft saved


          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f193162%2fstack-implementation-with-singly-linked-list%23new-answer', 'question_page');

          );

          Post as a guest






























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          up vote
          3
          down vote



          accepted










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





          share|improve this answer



















          • 1




            'simply linked list': did you mean 'singly'?
            – Daniel
            Apr 29 at 8:41






          • 1




            Both notions are used in the litterature and they are both correct, but there is a typo I guess, 'simple' not 'simply', so thank you@Coal_
            – Billal BEGUERADJ
            Apr 29 at 8:44










          • Great great answer. Points 1, 2, 3 were right on the money. Point 4 is because I love early exit from functions, but you are right. The code is readable when replacing the return with if else. I did not do it for remove_last though. A while loop inside an else statement makes me uncomfortable :). For point 5, I knew that when I wrote it. I just overdid it with both checks just as a form of catching myself making mistakes in moving the tail and head nodes during other operations
            – MAA
            Apr 29 at 21:00










          • You are also quite correct in points 6, 7 and 8. I kinda did them on purpose since I wanted to write a linked list anyways. But I should have removed them from the code I've posted here.
            – MAA
            Apr 29 at 21:02






          • 2




            Now everything after 8 surprised me. I always thought implementing a stack with linked list meant creating a linked list class. I noticed when I was done with the Stack class that I did not do anything stack-related. All of my code was for the linked list. I found it odd, but carried on. Now that I see your implementation, I get it. The simplicity of it and the fact that it's actually the stack logic I wanted to practice makes me appreciate your answer even more. Thank you Begueradj. I truly appreciate your time.
            – MAA
            Apr 29 at 21:06














          up vote
          3
          down vote



          accepted










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





          share|improve this answer



















          • 1




            'simply linked list': did you mean 'singly'?
            – Daniel
            Apr 29 at 8:41






          • 1




            Both notions are used in the litterature and they are both correct, but there is a typo I guess, 'simple' not 'simply', so thank you@Coal_
            – Billal BEGUERADJ
            Apr 29 at 8:44










          • Great great answer. Points 1, 2, 3 were right on the money. Point 4 is because I love early exit from functions, but you are right. The code is readable when replacing the return with if else. I did not do it for remove_last though. A while loop inside an else statement makes me uncomfortable :). For point 5, I knew that when I wrote it. I just overdid it with both checks just as a form of catching myself making mistakes in moving the tail and head nodes during other operations
            – MAA
            Apr 29 at 21:00










          • You are also quite correct in points 6, 7 and 8. I kinda did them on purpose since I wanted to write a linked list anyways. But I should have removed them from the code I've posted here.
            – MAA
            Apr 29 at 21:02






          • 2




            Now everything after 8 surprised me. I always thought implementing a stack with linked list meant creating a linked list class. I noticed when I was done with the Stack class that I did not do anything stack-related. All of my code was for the linked list. I found it odd, but carried on. Now that I see your implementation, I get it. The simplicity of it and the fact that it's actually the stack logic I wanted to practice makes me appreciate your answer even more. Thank you Begueradj. I truly appreciate your time.
            – MAA
            Apr 29 at 21:06












          up vote
          3
          down vote



          accepted







          up vote
          3
          down vote



          accepted






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





          share|improve this answer















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






          share|improve this answer















          share|improve this answer



          share|improve this answer








          edited Apr 29 at 8:45


























          answered Apr 29 at 7:38









          Billal BEGUERADJ

          1




          1







          • 1




            'simply linked list': did you mean 'singly'?
            – Daniel
            Apr 29 at 8:41






          • 1




            Both notions are used in the litterature and they are both correct, but there is a typo I guess, 'simple' not 'simply', so thank you@Coal_
            – Billal BEGUERADJ
            Apr 29 at 8:44










          • Great great answer. Points 1, 2, 3 were right on the money. Point 4 is because I love early exit from functions, but you are right. The code is readable when replacing the return with if else. I did not do it for remove_last though. A while loop inside an else statement makes me uncomfortable :). For point 5, I knew that when I wrote it. I just overdid it with both checks just as a form of catching myself making mistakes in moving the tail and head nodes during other operations
            – MAA
            Apr 29 at 21:00










          • You are also quite correct in points 6, 7 and 8. I kinda did them on purpose since I wanted to write a linked list anyways. But I should have removed them from the code I've posted here.
            – MAA
            Apr 29 at 21:02






          • 2




            Now everything after 8 surprised me. I always thought implementing a stack with linked list meant creating a linked list class. I noticed when I was done with the Stack class that I did not do anything stack-related. All of my code was for the linked list. I found it odd, but carried on. Now that I see your implementation, I get it. The simplicity of it and the fact that it's actually the stack logic I wanted to practice makes me appreciate your answer even more. Thank you Begueradj. I truly appreciate your time.
            – MAA
            Apr 29 at 21:06












          • 1




            'simply linked list': did you mean 'singly'?
            – Daniel
            Apr 29 at 8:41






          • 1




            Both notions are used in the litterature and they are both correct, but there is a typo I guess, 'simple' not 'simply', so thank you@Coal_
            – Billal BEGUERADJ
            Apr 29 at 8:44










          • Great great answer. Points 1, 2, 3 were right on the money. Point 4 is because I love early exit from functions, but you are right. The code is readable when replacing the return with if else. I did not do it for remove_last though. A while loop inside an else statement makes me uncomfortable :). For point 5, I knew that when I wrote it. I just overdid it with both checks just as a form of catching myself making mistakes in moving the tail and head nodes during other operations
            – MAA
            Apr 29 at 21:00










          • You are also quite correct in points 6, 7 and 8. I kinda did them on purpose since I wanted to write a linked list anyways. But I should have removed them from the code I've posted here.
            – MAA
            Apr 29 at 21:02






          • 2




            Now everything after 8 surprised me. I always thought implementing a stack with linked list meant creating a linked list class. I noticed when I was done with the Stack class that I did not do anything stack-related. All of my code was for the linked list. I found it odd, but carried on. Now that I see your implementation, I get it. The simplicity of it and the fact that it's actually the stack logic I wanted to practice makes me appreciate your answer even more. Thank you Begueradj. I truly appreciate your time.
            – MAA
            Apr 29 at 21:06







          1




          1




          'simply linked list': did you mean 'singly'?
          – Daniel
          Apr 29 at 8:41




          'simply linked list': did you mean 'singly'?
          – Daniel
          Apr 29 at 8:41




          1




          1




          Both notions are used in the litterature and they are both correct, but there is a typo I guess, 'simple' not 'simply', so thank you@Coal_
          – Billal BEGUERADJ
          Apr 29 at 8:44




          Both notions are used in the litterature and they are both correct, but there is a typo I guess, 'simple' not 'simply', so thank you@Coal_
          – Billal BEGUERADJ
          Apr 29 at 8:44












          Great great answer. Points 1, 2, 3 were right on the money. Point 4 is because I love early exit from functions, but you are right. The code is readable when replacing the return with if else. I did not do it for remove_last though. A while loop inside an else statement makes me uncomfortable :). For point 5, I knew that when I wrote it. I just overdid it with both checks just as a form of catching myself making mistakes in moving the tail and head nodes during other operations
          – MAA
          Apr 29 at 21:00




          Great great answer. Points 1, 2, 3 were right on the money. Point 4 is because I love early exit from functions, but you are right. The code is readable when replacing the return with if else. I did not do it for remove_last though. A while loop inside an else statement makes me uncomfortable :). For point 5, I knew that when I wrote it. I just overdid it with both checks just as a form of catching myself making mistakes in moving the tail and head nodes during other operations
          – MAA
          Apr 29 at 21:00












          You are also quite correct in points 6, 7 and 8. I kinda did them on purpose since I wanted to write a linked list anyways. But I should have removed them from the code I've posted here.
          – MAA
          Apr 29 at 21:02




          You are also quite correct in points 6, 7 and 8. I kinda did them on purpose since I wanted to write a linked list anyways. But I should have removed them from the code I've posted here.
          – MAA
          Apr 29 at 21:02




          2




          2




          Now everything after 8 surprised me. I always thought implementing a stack with linked list meant creating a linked list class. I noticed when I was done with the Stack class that I did not do anything stack-related. All of my code was for the linked list. I found it odd, but carried on. Now that I see your implementation, I get it. The simplicity of it and the fact that it's actually the stack logic I wanted to practice makes me appreciate your answer even more. Thank you Begueradj. I truly appreciate your time.
          – MAA
          Apr 29 at 21:06




          Now everything after 8 surprised me. I always thought implementing a stack with linked list meant creating a linked list class. I noticed when I was done with the Stack class that I did not do anything stack-related. All of my code was for the linked list. I found it odd, but carried on. Now that I see your implementation, I get it. The simplicity of it and the fact that it's actually the stack logic I wanted to practice makes me appreciate your answer even more. Thank you Begueradj. I truly appreciate your time.
          – MAA
          Apr 29 at 21:06












           

          draft saved


          draft discarded


























           


          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f193162%2fstack-implementation-with-singly-linked-list%23new-answer', 'question_page');

          );

          Post as a guest













































































          Popular posts from this blog

          Chat program with C++ and SFML

          Function to Return a JSON Like Objects Using VBA Collections and Arrays

          Will my employers contract hold up in court?