Arrays

The easiest way to create a contiguous block to data is to use an array. By allocating a whole block of memory and storing the first address of the block all other elements can be calculated in reference to that address or base pointer. As you can see in the example below, the addresses are sequential. This means that you must know how much memory you will require during the initialization process. The "7" in the code below is the number of integers worth of space we are requesting from the operating system. The inherent predictability of where the data will be allows for more cache hits and branch predictions. The disadvantage is that memory requirements must be specified ahead of time which can result in requesting more space than is required at any given step of a programs execution.

Linked Lists

These data structures are almost opposite of arrays. All data is allocated when needed and data locations are completely independent of each other. To link all the data together a base pointer cannot be used so each piece of data must also be grouped with a pointer to the next or previous data location. This data and pointer to the next memory location is grouped in a structure often called a Node. A head or start pointer is always kept to remember the location of the first node and the list is traversed by moving a current pointer keeping track of your current location in the list. While executing the program below notice how memory addresses are not continuous. This discontinuity removes many of the performance benefits of arrays. Cache hits occur less often and branch prediction becomes more difficult for the compiler. Linked lists allow dynamic allocation of memory for applications like a user creating a new tab in the browser, event based actions, where we do not know how much or when to allocate resources.

Linked lists are important to understand as their concepts are used in many more advanced data structures such as trees. However when storing lots of data in practice other more efficient structures are used such as Array Lists or Vectors, crosses between arrays and linked lists, offering the speed of continuous block of memory but the dynamic allocation of linked lists.