Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Python

Derek Derek
Derek Derek
8,744 Points
Posted by Derek Derek
Derek Derek
8,744 Points

python linkedlist implementation

I got below implementation of a linkedlist from online, but I don't understand how it works. In the add method, the while loop runs until cur.next is not None. However, we see that Node.next is initialized to None. How, then, can nodes be added after the first one? I also don't get the cur = cur.next part. What does that do? To me, it seems that it is setting the node that we want to add to the LL to itself, which is pointless. I must not be getting it right.. Please explain how the add method works.

One more thing is that I want to be able to print out the linkedlist, and I am trying to use a list. I've commented out the parts where I am trying to do the printing, and could you please confirm that I'm doing it correctly?

Thank you.

import unittest


class Node:
    def __init__(self, item):
        self.val = item
        self.next = None


class LinkedList:
    def __init__(self, item):
#       self.my_linkedlist = []
        self.head = Node(item)

    def add(self, item):
        cur = self.head
#       self.my_linkedlist.append(cur)
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(item)

#   def __str__(self):
#       return "Here's the linkedlist: {}".format(self.my_linkedlist)


class LinkedListTest(unittest.TestCase):
    def test(self):
        ll = LinkedList(3)
        ll.add(4)
        ll.add(5)
        ll.add(6)
        ll.add(7)
#       print ll

2 Answers

Jason Anello
PLUS
Jason Anello
Courses Plus Student 94,610 Points
Jason Anello
Jason Anello
Courses Plus Student 94,610 Points

Hi Derek,

The purpose of the next attribute is to point to the next node. But at the time that you create a node, there isn't another node for it to be pointing to and that's why it gets initialized to None

With the way this code is, the add method adds the node to the end of the list. Your only link to this list is the head node. This means that if you're going to add a new node at the end, you need some way of getting to that last node starting from the head.

That's the purpose of the while loop. You want to traverse through the nodes until you've arrived at the last node.

What's unique about the last node is that it's next attribute is None because it doesn't have another node to be pointing to. Each node points to the next one in the list except for the very last one.

The condition on the while loop, cur.next is not None is meant to detect this last node. As soon as the next attribute is None you want to stop looping because you know you've reached the last node.

def add(self, item):
        cur = self.head

        while cur.next is not None:
            cur = cur.next
        cur.next = Node(item)

cur is meant to reference the current node you're on. It's initialized to the head node to start off with. Inside the loop it gets updated to be the next node until you've detected that you're on the last node.

Once you get out of the loop, cur is a reference to the last node. You can then set its next attribute to this new node that you want to add.

Hopefully I didn't make it more confusing. Let me know if you're still having trouble with it.

In regards to your commented code -

I would recommend that you handle the printing of the linked list entirely within the __str__ method. Right now your commented code is dispersed across multiple methods but it's all related code. Also, you're storing and maintaining 2 copies of this data. The linked list itself and also storing it again in a python list for the purposes of later printing.

I would recommend that you put a while loop in your str method similar to what's in the add method. Then you can loop over every node and save the integer in a python list. Then return whatever string you'd like to see.

Derek Derek
Derek Derek
8,744 Points
Derek Derek
Derek Derek
8,744 Points

Jason Anello,

Thank you for the answer. I didn't know that calling a method creates an instance of the class. I'm still not sure about how the add method works.

When we do ll.add(4), self.head becomes Node(4), and in the add method, cur becomes Node(4), but Node(4).next is None. Therefore, we cannot proceed to the loop because the condition filters out Node(4) because its next is None by the initialization by creating a Node instance. Maybe if you could explain how Node(4) becomes Node(3).next, that will clear up my confusion. Thank you!

Jason Anello
Jason Anello
Courses Plus Student 94,610 Points

I think you must have deleted some of your follow up questions because I had 3 email notifications.

Calling a method doesn't create an instance of the class. You have to create the instance first and then you can call methods on it.

Maybe it will help to trace through the code for the first few lines in the test case and also talk a little about what's happening in memory.

I'll go go through the following 3 lines. I wanted to go as far as add(5) because that's the first time the while loop will execute. Beyond that, it's the same except that the while loop will loop more times.

ll = LinkedList(3)
ll.add(4)
ll.add(5)

ll = LinkedList(3) -

The first line creates a LinkedList object and passes 3 to the init method. Inside the init method, a Node object is created and the 3 is passed to it's init method. Inside that init method the 3 is stored in the val attribute and the next attribute is initialized to None because at the moment there isn't another Node to point to.

A reference to this newly created Node is then assigned to the head attribute of the LinkedList object.

At this moment, there is a LinkedList object in memory and a Node object somewhere else in memory. I'm not sure if you're thinking that the LinkedList is storing the Nodes or they are combined in some way but they are both completely separate.

Think of the head attribute as storing the memory location of where that Node is that's storing the 3. It knows where in memory this linked list begins. The nodes in a linked list can all be scattered throughout the computers memory. Each node is responsible for knowing where in memory the next node is.

ll.add(4) -

The local cur variable is assigned a reference to the head node. Right now, this is the only node there is. So the head is also the end node or the tail node.

The head nodes next attribute is still None from when it was created so the while loop condition is false and it's skipped.

Now we have cur.next = Node(item) to execute. This will create a new Node and pass the 4 to its init method. The 4 is stored and the next attribute is set to None. A reference to this newly created node is then assigned to cur.next

cur is a reference to the head node. So this means that the head node which is storing 3 is now pointing to this 2nd node in memory which is storing the 4. That node is pointing to nothing.

ll.add(5) -

Now, we'll finally see the while loop run 1 time.

Again, cur is assigned a reference to the head node. The difference is that the head node next attribute is no longer None. it's a reference to that 2nd node storing the 4. This makes the while condition true. Inside the while loop the cur variable is updated to be a reference to the 2nd node.

The while condition is tested again. Since cur is pointing to the second node, the while condition is false because the 2nd node is currently the last node and isn't pointing to anything.

Then you go on to the last line cur.next = Node(item) cur is still a reference to the 2nd node. A new node is created passing in the 5 and a reference to this new node is assigned to the next attribute of the 2nd node.

At this point, the head node storing a 3 is pointing to the 2nd node storing a 4, which in turn is pointing to the 3rd node that is storing a 5.

The rest of the adds will be the same with the exception of the while loop running more times because there will be more nodes to get through to reach the tail.

This ended up being pretty long-winded but hopefully it helps.

Let me know if there is still some part you don't understand.

Derek Derek
Derek Derek
8,744 Points
Derek Derek
Derek Derek
8,744 Points

Wow that clarifies my confusion 100%. Thank you so much. Now I understand how it works, I was able to write the str method. I really appreciate for taking the time to write such a beautiful answer.