Reading

As you know, a computer can read from an array in O(1) time. But now let’s figure out the efficiency of reading from a linked list.

If you want to read, say, the value of the third item of a linked list, the computer cannot look it up in one step, because it wouldn’t immediately know where to find it in the computer’s memory. After all, each node of a linked list could be anywhere in memory! All our program knows immediately is the memory address of the first node of the linked list; it doesn’t know offhand where any of the other nodes are.

To read from the third node, then, the computer must go through a process. First, it accesses the first node. It then follows the first node’s link to the second node and then the second node’s link to the third node.

To get to any node, then, we always need to start with the first node (the only node we initially have access to), and follow the chain of nodes until we reach the node we want.

It turns out, then, that if we were to read from the last node in the list, it would take N steps for N nodes in the list. Linked lists having a worst-case read of O(N) is a major disadvantage when compared with arrays that can read any element in just O(1). But don’t fret, as linked lists will have their moment to shine, as we’ll see soon.

Code Implementation: Linked List Reading

Let’s go ahead and add a read method to our LinkedList class:

If we want to read the fourth node from a list, for example, we’d call our method by passing in the node’s index as follows:

Let’s walk through how this method works.

First, we create a variable called current_node that refers to the node we’re currently accessing. Since we’re going to start by accessing the head, we say this:

Recall that first_node is an instance variable of the LinkedList class.

We also track the index of current_node so that we can know when we reach the desired index. We start at 0 since the first node’s index is 0:

We then launch a loop that runs while current_index is less than the index we’re attempting to read:

In each pass-through of the loop, we access the next node in the list and make it the new current_node:

We also bump up the current_index by 1:

At the end of each pass-through, we check whether we’ve reached the end of the list, and we return None if the index we’re trying to read isn’t in our list:

This works because the final node of the list will actually have a next_node that is None since the last node was never assigned a next_node of its own. This being the case, when current_node refers to the final node and we then execute current_node = current_node.next_node, the current_node becomes None.

Finally, if we do break out of the loop, it’s because we reached the desired index. We can then return the node’s value with the following: