Arrays

What Exactly is an Array?

An array is a collection of items of the same type stored at contiguous memory locations. This "contiguous" part is its superpower—it means all the elements live side-by-side in memory, which allows for incredibly fast access to any element.

• Indexing: Each element in an array has a numerical index, which is like its address. In most languages, indexing starts at 0. So, the first element is at index 0, the second at index 1, and so on.
• Fixed vs. Dynamic Size: In languages like C++ or Java, you must declare the size of an array beforehand. In others, like Python (lists) or C++ (std::vector), arrays are dynamic and can grow or shrink as needed. These are often called dynamic arrays or vectors.

Time Complexity at a Glance

Understanding the efficiency of array operations is key. Here's a quick rundown:

• O(1)

  Constant Time

  Access by Index: The biggest advantage of arrays. Reading or writing to array[i] is incredibly fast because the computer can calculate the memory address directly from the index.
• O(1)

  Amortized

  Insertion / Deletion (at the end): For dynamic arrays, adding or removing from the end is very fast on average. While it might occasionally require resizing the whole array (an O(n) operation), these resizes are infrequent enough that the average cost is still O(1).
• O(n)

  Linear Time

  Search, Insertion, & Deletion (at beginning or middle): These operations are slower because they require shifting all subsequent elements. In the worst case, if you insert at the beginning, you have to move every single element one position to the right.

Interactive Demo

To better understand how these operations affect an array, try the interactive simulation below. Notice how adding or removing from the beginning requires shifting everything, which is an O(n) operation that animations can help visualize (even though our demo makes it look instant!).