linked list output not expected in Python 2.7

Question

Implement a linked list and I expect output to be 0, -1, -2, -3, ... etc., but it is -98, -98, -98, -98, ... etc., wondering what is wrong in my code? Thanks.

MAXSIZE = 100
freeListHead = None

class StackNode:
    def __init__(self, value, nextNode):
        self.value = value
        self.nextNode = nextNode

if __name__ == "__main__":
    # initialization for nodes and link them to be a free list
    nodes=[StackNode(-1, None)] * MAXSIZE
    freeListHead = nodes[0]
    for i in range(0, len(nodes)-1):
        nodes[i].nextNode = nodes[i+1]
        nodes[i].value = -i
    for node in nodes:
        # output -98, -98, -98, -98, ... etc.
        # exepcted output, 0, -1, -2, -3, ... etc.
        print node.value

@dsgdfg, thanks and how it is related to my original question? — Lin Ma, Sep 26 '16 at 05:23

score 10 · Accepted Answer · edited Sep 27 '17 at 04:15

This is the problem:

# initialization for nodes and link them to be a free list
nodes=[StackNode(-1, None)] * MAXSIZE

When you use the multiply operator, it will create multiple references to the same object, as noted in this StackOverflow answer. So changing one node's value (as in nodes[i].value = -i) will affect every node since every item in the list points to the same object.

In that same linked answer, the solution is to use list comprehension like this:

nodes = [StackNode(-1, None) for i in range(MAXSIZE)]

Also, note that you did not set the value of the last element, so the output (after the fix I suggested above) will be:

0, -1, -2, ..., -98, -1

Nice catch justhalf! Vote up and mark your reply as answer. – Lin Ma Sep 26 '16 at 05:23 — Lin Ma, Sep 26 '16 at 05:23

linked list output not expected in Python 2.7

1 Answers1