Insertion
Admittedly, linked lists have yet to impress us from a performance standpoint. They’re no better than arrays at search, and much worse at reading. But not to worry—linked lists will have their moment. In fact, that moment is now.
Insertion is one operation in which linked lists have a distinct advantage over arrays in certain situations.
Recall that the worst-case scenario for insertion into an array is when the program inserts data into index 0, because it first has to shift the rest of the data one cell to the right, which ends up yielding an efficiency of O(N). With linked lists, however, insertion at the beginning of the list takes just one step—which is O(1). Let’s see why.
Say we have the following linked list:
If we want to add "yellow" to the beginning of the list, all we have to do is create a new node and have its link point to the node containing "blue":
(In our code, we’d also need to update the LinkedList instance so that its first_node attribute now points to this "yellow" node.)
In contrast with an array, the linked list provides the flexibility of inserting data to the front of the list without requiring the shifting of any data. How sweet is that?
The truth is that, theoretically, inserting data anywhere within a linked list takes just one step, but there’s one gotcha. Let’s continue with our example. Here’s our linked list now:
Say we now want to insert "purple" at index 2 (which would be between "blue" and "green"). The actual insertion takes just one step; that is, we can create the new purple node and simply change the blue node’s link to point to the purple node, as shown here:
However, for the computer to do this, it first needs to get to the node at index 1 ("blue") so that it can modify its link to point to the newly created node. As we’ve seen, though, reading—which is accessing an item at a given index—from a linked list already takes O(N). Let’s see this in action.
We know that we want to add a new node after index 1. So the computer needs to get to index 1 of the list. To do this, we must start at the beginning of the list:
We then access the next node by following the first link:
Now that we’ve found index 1, we can finally add the new node:
In this case, adding "purple" took three steps. If we were to add it to the end of our list, it would take five steps: four steps to access index 3 and one step to insert the new node.
Practically speaking, then, inserting into a linked list is O(N), as the worst-case scenario of inserting at the end of the list will take N + 1 steps.
However, we’ve seen that the best-case scenario of inserting at the beginning of the list is only O(1).
Interestingly, our analysis shows that the best- and worst-case scenarios for arrays and linked lists are the opposite of one another. The following table breaks this all down:
Scenario | Array | Linked List |
|---|---|---|
Insert at beginning | Worst case | Best case |
Insert at middle | Average case | Average case |
Insert at end | Best case | Worst case |
As you can see, arrays favor insertions at the end, while linked lists favor insertions at the beginning.
We’ve now found one thing that linked lists are great at—inserting things at the beginning of the list. Later in this chapter, we’ll see a great practical example of where we can take advantage of this.
Code Implementation: Linked List Insertion
Let’s add an insertion method to our LinkedList class. We’ll call it insert:
| | def insert(self, index, value): |
| | new_node = node.Node(value) |
| | |
| | if index == 0: |
| | new_node.next_node = self.first_node |
| | self.first_node = new_node |
| | return |
| | |
| | current_node = self.first_node |
| | current_index = 0 |
| | |
| | while current_index < (index - 1): |
| | current_node = current_node.next_node |
| | current_index += 1 |
| | |
| | new_node.next_node = current_node.next_node |
| | |
| | current_node.next_node = new_node |
To use the method, we pass in both the new value as well as the index of where we want to insert it.
For example, to insert "purple" at index 2, we’d say this:
| | list.insert(2, "purple") |
Let’s break this insert method down.
First, we create a new Node instance with the value provided to our method:
| | new_node = node.Node(value) |
(Here, the node from node.Node refers to the node module we imported at the beginning of the file, as we placed the Node class in a separate file from the LinkedList class.)
Next, we deal with the case where we’re inserting into index 0—that is, at the beginning of our list. The algorithm for this case is different than if we insert elsewhere into the list, so we deal with this case separately.
To insert at the beginning of the list, we simply have our new_node link to the first node of the list and declare our new_node to be the first node going forward:
| | if index == 0: |
| | new_node.next_node = self.first_node |
| | self.first_node = new_node |
| | return |
The return keyword ends the method early, as there’s nothing left to do.
The rest of the code deals with a case in which we’re inserting anywhere other than at the beginning.
As with reading and searching, we start off by accessing the head of the list:
| | current_node = self.first_node |
| | current_index = 0 |
We then use a while loop to access the node just before the spot where we want to insert our new_node:
| | while current_index < (index - 1): |
| | current_node = current_node.next_node |
| | current_index += 1 |
At this point, the current_node is the node that’ll immediately precede our new_node.
Next, we set the link of our new_node to point to the node after the current_node:
| | new_node.next_node = current_node.next_node |
Finally, we change the link of the current_node (which, again, is to be the node that precedes our new_node) to point to our new_node:
| | current_node.next_node = new_node |
And we’re done!
