Join us and get access to thousands of tutorials and a community of expert Pythonistas.
This lesson is for members only. Join us and get access to thousands of tutorials and a community of expert Pythonistas.
Inserting at the Beginning and End
00:00
At this point, we have a linked list that can be created with any number of nodes and traversed—or “iterated through”—using a Python for loop. Next, let’s add a way to insert elements at the beginning or the end of the list.
00:17
Since these methods act on the linked list, it makes the most sense to put them in the LinkedList class. This method will be called add_first(), and it will take a Node to add to the beginning of the list. First, I’m going to set the .head of our LinkedList equal to the node we passed in. Now to connect the rest of the nodes to this one, we can do node.next = self.head.
00:58
Well, that’s unfortunate. The program appears to be hung. Something is wrong with our .add_first() method. Pause the video and see if you can figure out what the problem is.
01:12
As you might’ve figured out, I accidentally lost most of the linked list in the process of adding a new node to the beginning. That’s because I reassigned self.head equal to the Node, so it stopped referencing the linked list in memory.
01:29
Then, I tried to set the next node equal to the .head, which already holds the passed-in Node, so we ended up with a single Node that pointed to itself. Traversing that is a recipe for disaster. The fix here is pretty simple: all we have to do is reverse the order of these two lines.
01:50
This way, we’re setting the .next attribute of the Node being passed in to the current LinkedList in memory. Then, we tell the LinkedList.head to point to the passed-in Node.
02:03 As you can tell, the order in which you do things is very important when working with linked lists. It’s very easy to make a mistake and lose your list or get stuck in a loop.
02:19
There we go. Next, let’s create a method that will allow us to add an element to the end of the linked list. That code will go in a new method called add_last(). And just like the other method, it will take a Node to add. Before we can traverse to the end of the linked list and add the new node, we have to check for a special case—that is, the list is empty. If the list is empty, self.head will point to None, and trying to traverse that won’t work.
02:53
So we’ll say if not self.head, I just want to set the .head value equal to this new node.
03:02
By writing return here, I tell Python to stop execution of this method right on this line. In the event that there are nodes to traverse, we can traverse them by taking advantage of the fact that our LinkedList is now iterable. for current_node in self: pass.
03:24
This little trick will create a local variable called current_node and set it equal to the last node in the list. Now that we’re at the end of the list, we can set the .next attribute of this Node equal to the one that was passed in.
03:40
Keep in mind here that because we used a new local variable to traverse the linked list, we never modify self.head directly. We don’t have to worry about where it’s pointing to.
03:58 And now, we have a new node at the end. Next, let’s write code to insert a node between two existing nodes.
Bartosz Zaczyński RP Team on June 4, 2021
@xiaohao-lin1 The for loop creates an iterator object by calling the built-in iter() function on self, which in turn calls the .__iter__() special method in your LinkedList class. That special method yields the subsequent list elements that can be intercepted in the loop. When the loop finishes, the current_node will point to the last element on the list you can append new elements to.
This is roughly similar to the folowing steps:
it = iter(self)
try:
while True:
current_node = next(it)
except StopIteration:
last_element = current_node
Become a Member to join the conversation.
xiaohao-lin1 on June 4, 2021
Can you kindly explain how does the following code bring us to the end of list?