Array

An array is the most common and simple list data structure. It imposes no memory overhead because the constituent items occupy a single contiguous section of memory. The graphic below depicts how an array is arranged in memory.

Array

A distinct advantage of Arrays is that any item can be accessed in constant time via direct addressing. This means that the memory address of any item in an array is easily calculable from an index. If $i$ is the array index, $sz$ is the size of individual items, and is the starting address, the formula for determining the address of an individual array is: $(i * sz) + a$.

Asymptotic Complexity

  • Insert\Delete: $O(n)$
  • Search: $O(n)$
  • Enumerate: $O(n)$

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions

Advantages

  • Access By Index: Arrays are the only data structure capable of accessing items by index in $O(1)$. The memory address of any item is easily calculable by summing the base address and the product of the desired index and item size.
  • Memory: Zero overhead required. The total size of an array is the sum of all its items.
  • Cache Optimized: Guaranteed to have optimal spatial locality which can have profound performance implications. See the Memory Cache Hierarchy section for more details.
  • Maintains Order: Maintains the order in which items are inserted

Disadvantages

  • Insert\Delete: Inserting\Deleting a item requires a different sized contiguous section of memory. Therefore, a new section of memory must be allocated and existing items must be copied into the newly allocated area.
  • Search: The only way to search an array is to start at the first item and examine each item individually.