A Common-Sense Guide to Data Structures and Algorithms

Reading

We noted previously that when reading a value from an array, the computer can jump to the appropriate cell in a single step, which is O(1). This is not the case, however, with a linked list.

If your program wanted to read the value at index 2 of a linked list, the computer could not 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! Instead, all the program knows is the memory address of the first node of the linked list. To find index 2 (which is the third node), the program must begin looking up index 0 of the linked list, and then follow the link at index 0 to index 1. It must then again follow the link at index ...