implement stack with freelist feature in Python 2.7
<p>Design a stack with free list feature (i.e. after a node is popped, its space is reusable by future push operation, and kept in free list). The code is simplified and does not make sense in some perspective, and I just use below code to show the general idea of stack with free list (as a prototype).</p>

<p>My question is about how to design <code>pop</code> operation. My confusion is since a reference to a node is returned after <code>pop</code> operation, for example in my code there is <code>node1 = stack.pop()</code>, the reference to a node might be used by client who call <code>pop</code>, and the same node reference is reclaimed in free list and might be used by other <code>push</code> operation, how to resolve such conflict and wondering for general advice for design free list feature with stack, linked list or queue.</p>

<pre><code>MAXSIZE = 100
freeListHead = None

class StackNode:
    def __init__(self, value, nextNode):
        self.value = value
        self.nextNode = nextNode
class Stack:
    def __init__(self):
        self.top = None
        self.size = 0
    def peek(self):
        # return StackNode
        return self.top
    def push(self, value):
        global freeListHead
        if self.size &gt;= MAXSIZE:
            raise Exception('stack full')
        node = freeListHead
        node.value = value
        freeListHead = node.nextNode
        node.nextNode = self.top
        self.top = node
        self.size += 1
    def pop(self):
        if self.size == 0:
            return None
        node = self.top
        self.top = self.top.nextNode
        self.size -= 1
        return node

if __name__ == "__main__":
    # initialization for nodes and link them to be a free list
    nodes = [StackNode(-1, None) for i in range(MAXSIZE)]
    freeListHead = nodes[0]
    for i in range(0, len(nodes)-1):
        nodes[i].nextNode = nodes[i+1]
    stack = Stack()
    stack.push(1)
    stack.push(50)
    stack.push(100)
    stack.push(200)
    print stack.peek().value
    node1 = stack.pop()
    print node1.value
    print stack.peek().value
</code></pre>

<p>You could simplify your code by returning the <code>value</code> given to <code>push</code> instead of <code>StackNode</code> holding the value. There are no concerns of memory consumption since you can set <code>node.value</code> to <code>None</code> in <code>pop</code> before returning the result. Below is simple example on how this would work in the practice:</p>

<pre><code>class Node:
    def __init__(self):
        self.nextNode = self.value = None

class Stack:
    def __init__(self, maxSize):
        self.maxSize = maxSize
        self.size = 0
        self.top = self.free = None

    def push(self, value):
        if self.size == self.maxSize:
            raise Exception('Stack full')

        if self.free:
            node = self.free
            self.free = node.next
        else:
            node = Node()

        node.value = value
        node.nextNode = self.top
        self.top = node
        self.size += 1

    def pop(self):
        if not self.top:
            raise Exception('Stack empty');
        node = self.top
        self.top = node.nextNode
        node.nextNode = self.free
        self.free = node
        self.size -= 1
        result = node.value
        node.value = None

        return result

stack = Stack(3)
for i in range(3):
    stack.push(list(range(i + 1)))

while stack.size:
    print(stack.pop())
</code></pre>

<p>Output:</p>

<pre><code>[0, 1, 2]
[0, 1]
[0]
</code></pre>

python python-2.7 stack