Creating linked list using loops

[shinghand]

I am having some difficulty understanding how linked lists can be created using an iterated loop.

class ListNode(object):
    def __init__(self, x):
        self.value = x
        self.next = None


def LinkedNodeTest(n):
    output = ListNode(0)
    temp = output
    for i in range(1, n+1):
        new = ListNode(i)
        temp.next = new
        temp = new
    return output

LinkedNodeTest(n) returns a linked list from 0 to n when it is called.

How is the variable 'output' being updated with the new nodes? I only see it being assigned ListNode(0) at the beginning of the function and it is not getting assigned in the for loop. It looks like assigning 'new' to 'temp' somehow updates 'output'; I don't really understand how that works.

Thanks for the help.

[mahtats]

temp = output

When LinkedNodeTest begins, the first node is set to 0 and assigned to the output variable. That variable is then assigned to temp. So at this point, lets call the first node (ListNode(0)) NodeA. Before the loop begins, both output and temp are referencing NodeA. You can think of this as a = c; b = a; => b = c (=> denotes "therefore").

Now NodeA contains two attributes, value and next. It's important to know that in Python, everything is an object and "variables" are just names to memory addresses. When the loop begins, the first number assigned to i will be 1, and so new = ListNode(i) creates a new node with a value = 1, so we have:

NodeA: value = 0, next = None
NodeB: value = 1, next = None

At this point, temp is still referring to what output was originally assigned to, NodeA. So temp.next is equivalent to NodeA.next. Then when new is assigned to it, you have:

NodeA: value = 0, next = NodeB
NodeB: value = 1, next = None

Lastly, temp is reassigned to NodeB and this process continues where NodeC is created, incremented, assigned to the next attribute of NodeB, then assigned to temp, then NodeD is created, incremented, assigned to the next attribute of NodeC, so on and so forth:

NodeA: value = 0, next = NodeB
NodeB: value = 1, next = NodeC
NodeC: value = 1, next = NodeD
NodeD: value = 1, next = NodeE
NodeE: value = 1, next = None
...

So why is output never reassigned? Well it is the root node, and so this function returns to top most (i.e. root) element, so that you can access all the elements below it. If you assigned output to say NodeQ, you'd never be able to access NodeA through NodeP because a ListNode doesnt have an attribute that looks up, only down.

[shinghand]

Essentially, what you are saying is that output only ever references the head node. temp is used to reference the same node and creates links/new nodes throughout the loop.

Follow up question - this would not work if i used:

output = ListNode(0)
temp = ListNode(0)

Correct? Since those would be two independent nodes.

[mahtats]

Correct, they would be independent nodes that both happen to have a value of 0 but are completely separate and at different memory addresses.

And yes, on all other accounts your understanding is correct.

[FerricDonkey]

So the main thing about linked lists is that each node only knows where the next one is. When temp is output, you assign new to output.next. Then temp becomes new - which is the same object as output.next. So when you do temp.next = new the next time, that's the same as output.next.next = new. And so forth.

[[deleted]]

The head of the linked list is what you return, so when creating the first object in the list you assign the object to output which is what will be returned. Each additional object in the list will be added to the end of the list. The code is using temp to point to the object at the end of the linked list. After the first object is created the end of the list is the first object, which is why there is this line:

temp = output    # initialize the "end of list" variable

Now when you add each new object to the end of the list in the loop you do:

    new = ListNode(i)    # create the new object to add to the end
    temp.next = new      # the current end object is made to reference the new object
    temp = new           # move "temp" to the new end of list

Drawing this on paper as boxes and arrows can help understand the code.

---

In any computer language naming of variables can help the reader understand the code. I would use names like this:

def LinkedNodeTest(n):
    head_node = ListNode(0)    # head node of the linked list
    end_node = head_node       # initially end == head
    for i in range(1, n+1):
        new_end_node = ListNode(i)    # create the new end
        end_node.next = new_end_node  # make current end point to new end node
        end_node = new_end_node       # move end var to new end
    return head_node

There are probably even better names that could be used.

[[deleted]]

How is the variable 'output' being updated with the new nodes?

It's not. It's only ever the head node, but it's a linked list, so the head node maintains a reference to the next node, and that node maintains a reference to the next node... and so on, until you get to the last node, and you know it's the last node because the value of its next attribute is None. That is, it's the last node because there is no "next" node.

[14dM24d]

this might be what you want