Inserting at the Beginning and End
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.
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.
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.
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.
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.
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
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.
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.
So we’ll say
if not self.head, I just want to set the
.head value equal to this new node.
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:
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.
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.
@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?