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.
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.
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.
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.
Become a Member to join the conversation.