Stack implementation with singly linked list
Clash 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()
python linked-list reinventing-the-wheel stack
add a comment |Â
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()
python linked-list reinventing-the-wheel stack
add a comment |Â
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()
python linked-list reinventing-the-wheel stack
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()
python linked-list reinventing-the-wheel stack
edited Apr 29 at 7:39
Billal BEGUERADJ
1
1
asked Apr 28 at 20:15
MAA
5716
5716
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
- You have a typo/mistake in
if not self._head and not self._head
, I think you wanted to writeself._tail
in one of them. - I do not see the interest of making
Node()
inner toLinkedList()
. In opposite, doing so condemns you not to reuse theNode()
code and slaughters your code scalability (in case you will need to add functionality to your code by implementing a queue, for example) 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- 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 theif ... else
statements instead because this makes sense and that is what the reader of your code may expect. - Here, we can use more common sense:
if not self._head and not self._tail
: honestly, if the head isNone
, it must be obvious the tail is in the same condition. I mean you can replace similar lines to simply:if not self._head
- 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.
- Do not code what you do not need: it is unnecessary to use
add_last()
andremove_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. - 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())
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
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
- You have a typo/mistake in
if not self._head and not self._head
, I think you wanted to writeself._tail
in one of them. - I do not see the interest of making
Node()
inner toLinkedList()
. In opposite, doing so condemns you not to reuse theNode()
code and slaughters your code scalability (in case you will need to add functionality to your code by implementing a queue, for example) 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- 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 theif ... else
statements instead because this makes sense and that is what the reader of your code may expect. - Here, we can use more common sense:
if not self._head and not self._tail
: honestly, if the head isNone
, it must be obvious the tail is in the same condition. I mean you can replace similar lines to simply:if not self._head
- 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.
- Do not code what you do not need: it is unnecessary to use
add_last()
andremove_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. - 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())
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
add a comment |Â
up vote
3
down vote
accepted
- You have a typo/mistake in
if not self._head and not self._head
, I think you wanted to writeself._tail
in one of them. - I do not see the interest of making
Node()
inner toLinkedList()
. In opposite, doing so condemns you not to reuse theNode()
code and slaughters your code scalability (in case you will need to add functionality to your code by implementing a queue, for example) 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- 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 theif ... else
statements instead because this makes sense and that is what the reader of your code may expect. - Here, we can use more common sense:
if not self._head and not self._tail
: honestly, if the head isNone
, it must be obvious the tail is in the same condition. I mean you can replace similar lines to simply:if not self._head
- 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.
- Do not code what you do not need: it is unnecessary to use
add_last()
andremove_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. - 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())
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
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
- You have a typo/mistake in
if not self._head and not self._head
, I think you wanted to writeself._tail
in one of them. - I do not see the interest of making
Node()
inner toLinkedList()
. In opposite, doing so condemns you not to reuse theNode()
code and slaughters your code scalability (in case you will need to add functionality to your code by implementing a queue, for example) 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- 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 theif ... else
statements instead because this makes sense and that is what the reader of your code may expect. - Here, we can use more common sense:
if not self._head and not self._tail
: honestly, if the head isNone
, it must be obvious the tail is in the same condition. I mean you can replace similar lines to simply:if not self._head
- 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.
- Do not code what you do not need: it is unnecessary to use
add_last()
andremove_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. - 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())
- You have a typo/mistake in
if not self._head and not self._head
, I think you wanted to writeself._tail
in one of them. - I do not see the interest of making
Node()
inner toLinkedList()
. In opposite, doing so condemns you not to reuse theNode()
code and slaughters your code scalability (in case you will need to add functionality to your code by implementing a queue, for example) 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- 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 theif ... else
statements instead because this makes sense and that is what the reader of your code may expect. - Here, we can use more common sense:
if not self._head and not self._tail
: honestly, if the head isNone
, it must be obvious the tail is in the same condition. I mean you can replace similar lines to simply:if not self._head
- 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.
- Do not code what you do not need: it is unnecessary to use
add_last()
andremove_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. - 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())
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
add a comment |Â
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
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password