A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

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 ...