Arrays: The Foundation of Data Storage

In the previous chapter we discussed efficiency metrics.

Now we begin with the most common data structure: the array.

---

What Is an Array?

An array stores elements in a fixed-order sequence.

Each element has an index position, typically starting from 0.

Example:

• arr[0]
• arr[1]
• arr[2]

This indexing model is simple and powerful.

---

Contiguous Memory Model

Conceptually, arrays are stored in contiguous memory locations.

That helps compute element addresses quickly.

graph LR
  A[Index 0] --> B[Index 1] --> C[Index 2] --> D[Index 3]

Because positions are predictable, random access is very fast.

---

Strength: Fast Access

Accessing an element by index is typically O(1).

This makes arrays excellent for:

• direct lookup by position
• iteration across sequential data
• representing compact collections

---

Weakness: Expensive Middle Updates

Inserting or deleting near the beginning or middle may require shifting many elements.

That often costs O(n).

So arrays are great for read-heavy workloads, but not always ideal for frequent arbitrary insertions.

---

Why Arrays Matter So Much

Many higher-level structures build on array-like storage:

• dynamic arrays / vectors
• heaps
• hash table buckets
• matrix representations

Understanding arrays gives a foundation for many later structures.

---

Key Ideas to Remember

• Arrays store ordered elements by index.
• Indexed access is typically constant-time.
• Contiguous layout enables fast lookup.
• Middle insertions/deletions are usually expensive.
• Arrays are foundational to many advanced structures.

---

What Comes Next

Arrays are rigid in how they store data.

Next we explore a more flexible model:

linked structures built from nodes and pointers.