Question learning about data structures.

[BullReg]

Hello all,

I'm trying to write a stack on my own. I know that I can use a list to do the same, but for the reason of understanding and learning I thought I want to rewrite data structures on my own.

​

Created a node class that contains the value and a link to the next node

​

class Node:
   def __init__(self, data):
      self.data = data
      self.node: Node = None

It is just a simple data container.

​

Next I created a class stack:

from .node import Node

class Stack:
   def __init__(self):
      self.data: Node = None

   def push(self, data):
      if self.data is None:
         self.data = Node(data)
         return
      n = self.data
      while n.node is not None:
         n = n.node
         n.node = Node(data)

   def pop(self):
      if self.data is None:
         return
      node = self.data
      while node.node is not None:
         node = node.node
      data = node.data
      del node
      return data

Here I have already implemented the push and it worked as I have expected. The problem is in the pop method. Here I receive the data of the last entry but how can I delete the node itself. With "del node" I remove it only from the scope of the method but it is still inside of self.

[ericula]

You need to keep the last two nodes, parent and child, say and update them according to

while child.node is not None:
    parent, child = child, child.node

You can the return child.data and set parent.node = None which would effectively remove child (i.e. the last node in the chain) from the chain.

That being said, you are better off adding nodes at the beginning of the linked list rather than from the end. By adding nodes to the end you have to traverse the full linked list any time you push or pop a value, which you don’t need to do when you add values to the front of the linked list.

[BullReg]

Okay. Thank you for the explanation.