Arrays vs. linked lists

Arrays are stored in memory “contiguously”. A reference to an array in memory is really just a reference to the register where the first index of the array is stored, and then the next register in memory contains the second index, and so on until the end of the array. All of the items in the array are stored “next to one another” in memory, since moving “up” or “down” one register will traverse the array. Since a contiguous block of registers is needed to fit the data, the necessary sized block of memory must be free before it can be allocated. Then, it must be allocated to the array, at which point the array can be stored.

Linked lists are stored randomly throughout memory. A reference to a linked list in memory is just a reference to the register where the first item of the list is stored, but each item of the list contains a pointer to the register containing the next item. This allows linked lists to be stored without initially allocating memory to store them, since there doesn’t need to be a contiguous block of memory to fit the data.

Because arrays and linked lists are stored differently, they perform differently upon read/write.

To read an array item at a given index is very fast (O(1) in Big O notation), since the register can be found easily based on the starting location of the array.

Writing to an array is slower however (O(n)), since all of the items are stored in order and must be moved around in order to accomodate the new item. A good analogy is inserting a friend into a group of friends sitting together in a movie theater: many friends will need to move down one seat to make room, or, if there is no room in the row, a new row must be found (or a new block freed).

To read a linked list is as slow as writing to an array (O(n)), since finding the correct item in the list to read requires traversing along the path of pointers to the correct item.

Writing to a linked list is faster however (O(1)), since a random free register can be easily found (or freed) to accomodate the new data.

So: