Linear Structures Lesson 3

Arrays and Dynamic Arrays

beginner ⏱️ 40 minutes 🌍 Implementing a photo gallery, building a playlist

Arrays are one of the most fundamental data structures in computer science. They provide a way to store collections of items, typically of the same type, in contiguous memory locations. We’ll explore two main types: fixed-size arrays and their more flexible counterparts, dynamic arrays. Understanding their strengths, weaknesses, and how they operate is crucial for efficient programming.

Fixed-Size Array: `items`

Elements are stored in contiguous memory, allowing for O(1) direct access by index.

Accessing items[2] is O(1)

🔢 Fixed-Size Arrays

A fixed-size array (often just called “an array” in languages like C/C++ or low-level contexts) is a collection of elements of the same data type stored in contiguous memory locations, accessed using an index. Once declared, its size cannot be changed.

Characteristics:

Contiguous Memory: Elements are stored right next to each other.
Fixed Size: You declare the maximum size at creation, and it cannot be altered.
Homogeneous Elements: Typically store items of the same data type.
Direct Access: Elements can be accessed directly using an index (e.g., arr[0], arr[5]).

Analogy: Imagine a row of mailboxes, each with a number starting from zero. You know exactly how many mailboxes there are, and to get to mailbox #5, you just go to the 5th one, not having to check all previous ones.

Fixed-Size Array Operations


        
          
#include <stdio.h>

int main() {
  // Declaration and Initialization
  int numbers[5]; // Fixed-size array of 5 integers
  int primes[] = {2, 3, 5, 7, 11}; // Initialized with values, size is 5

  // Accessing elements (O(1))
  printf("First prime: %d\n", primes[0]); // Output: 2
  printf("Third prime: %d\n", primes[2]); // Output: 5

  // Modifying elements (O(1))
  numbers[0] = 10;
  numbers[1] = 20;
  // Attempting to access numbers[5] would be out-of-bounds!

  // Iterating (O(N))
  for (int i = 0; i < 5; i++) {
      // ... do something with primes[i]
  }
  return 0;
}


        
          
# Python lists are dynamic arrays, but can conceptually represent fixed-size
# if you treat them that way. For true fixed-size, usually use 'array' module
# or NumPy arrays.

import array

# Fixed-size array of integers
# 'i' is the type code for signed int
fixed_array = array.array('i', [0] * 5)
print(f"Initial fixed_array: {fixed_array}")

# Accessing elements (O(1))
print(f"First element: {fixed_array[0]}")

# Modifying elements (O(1))
fixed_array[0] = 10
fixed_array[1] = 20
print(f"Modified fixed_array: {fixed_array}")

# Attempting to access fixed_array[5] would raise an IndexError!

# Iterating (O(N))
for item in fixed_array:
  # ... do something with item
  pass


        
          
// JavaScript arrays are dynamic. To simulate fixed-size:
let fixedArray = new Array(5).fill(0); // Create array of size 5, filled with 0

// Accessing elements (O(1))
console.log("First element:", fixedArray[0]); // Output: 0

// Modifying elements (O(1))
fixedArray[0] = 10;
fixedArray[1] = 20;
console.log("Modified fixedArray:", fixedArray); // Output: [10, 20, 0, 0, 0]

// Attempting to access fixedArray[5] returns undefined, doesn't error
// It also won't expand the array size by default unless explicitly assigned.

// Iterating (O(N))
for (let i = 0; i < fixedArray.length; i++) {
  // ... do something with fixedArray[i]
}

Complexity (Fixed-Size Arrays):

Access (by index): O(1) - Direct memory lookup.
Insertion/Deletion (at end): O(1) (if allowed and within bounds)
Insertion/Deletion (at beginning/middle): O(N) - Requires shifting all subsequent elements.
Search (unsorted): O(N)
Search (sorted - binary search): O(log N)
Space Complexity: O(N) - Stores N elements.

Practical Usages:

Storing a small, known number of items (e.g., days of the week, months of the year).
Implementing lookup tables.
Buffers for fixed-size data.
Foundational component for more complex data structures.

Note: The O(1) access time is a direct consequence of elements being stored contiguously. Given the base address of the array and the size of each element, the memory address of any element can be calculated directly: address(arr[i]) = base_address + i * element_size. This makes arrays incredibly fast for reads and writes at known indices.

📈 Dynamic Arrays

Dynamic arrays (often called ArrayList in Java, Vector in C++, or just “list” in Python and “array” in JavaScript) provide the flexibility of arrays without the fixed-size limitation. They automatically grow or shrink as elements are added or removed.

How they work: A dynamic array is typically implemented using a fixed-size array under the hood. When the underlying array becomes full, the dynamic array performs the following steps:

Allocates a new, larger fixed-size array (often double the current capacity).
Copies all elements from the old array to the new array.
Deallocates the old array.
Adds the new element to the new (larger) array.

Analogy: Imagine a shopping cart. As you add more items, if the cart gets full, you transfer everything to a bigger cart. This process takes extra effort but allows you to keep adding items indefinitely.

Dynamic Array Resizing

When a dynamic array runs out of capacity, it allocates a larger underlying array and copies existing elements.

1. Array is Full

Capacity: 4, Size: 4

Red

Green

Blue

Yellow

Needs more space!

➡️

2. Allocate New Array

New Capacity: 8, Size: 4

Red

Green

Blue

Yellow

...

Larger array created.

➡️

3. Copy Elements

New Capacity: 8, Size: 4 + 1

Red Red

Green Green

Blue Blue

Yellow Yellow

<NEW>

Elements moved, new item added.

This copy operation takes O(N) time, but it's amortized to O(1) for many appends.

Dynamic Array Operations (Conceptual)


        
          
// C does not have a built-in dynamic array type like C++'s std::vector.
// You'd implement it manually using realloc().

#include <stdio.h>
#include <stdlib.h> // For malloc, realloc, free

typedef struct {
  int *data;
  int size;     // Current number of elements
  int capacity; // Current allocated capacity
} DynamicArray;

// Initialize a dynamic array
void init_array(DynamicArray *arr, int initialCapacity) {
  arr->data = (int *) malloc(sizeof(int) * initialCapacity);
  if (arr->data == NULL) { /* Handle error */ }
  arr->size = 0;
  arr->capacity = initialCapacity;
}

// Add an element to the end (amortized O(1))
void push_back(DynamicArray *arr, int value) {
  if (arr->size == arr->capacity) {
      // Time to resize!
      arr->capacity *= 2; // Double capacity
      arr->data = (int *) realloc(arr->data, sizeof(int) * arr->capacity);
      if (arr->data == NULL) { /* Handle error */ }
      printf("Resized array to capacity: %d\n", arr->capacity);
  }
  arr->data[arr->size++] = value;
}

// Cleanup
void free_array(DynamicArray *arr) {
  free(arr->data);
  arr->data = NULL;
  arr->size = 0;
  arr->capacity = 0;
}

int main() {
  DynamicArray my_array;
  init_array(&my_array, 2); // Start with capacity 2

  push_back(&my_array, 10); // size=1, cap=2
  push_back(&my_array, 20); // size=2, cap=2 (full)
  push_back(&my_array, 30); // Resizes to cap=4, then adds. size=3, cap=4
  push_back(&my_array, 40); // size=4, cap=4 (full)
  push_back(&my_array, 50); // Resizes to cap=8, then adds. size=5, cap=8

  printf("Array elements: ");
  for (int i = 0; i < my_array.size; i++) {
      printf("%d ", my_array.data[i]);
  }
  printf("\n");

  free_array(&my_array);
  return 0;
}


        
          
# Python lists are dynamic arrays.
my_list = [] # Initially empty

# Appending elements (amortized O(1))
my_list.append(10) # List grows automatically
my_list.append(20)
my_list.append(30)
print(f"Current list: {my_list}")

# Accessing elements (O(1))
print(f"Element at index 1: {my_list[1]}") # Output: 20

# Modifying elements (O(1))
my_list[0] = 100
print(f"Modified list: {my_list}")

# Inserting at arbitrary position (O(N))
my_list.insert(1, 15) # Shifts elements
print(f"After insert: {my_list}") # Output: [100, 15, 20, 30]

# Deleting at arbitrary position (O(N))
my_list.pop(1) # Removes element at index 1, shifts elements
print(f"After pop: {my_list}") # Output: [100, 20, 30]


        
          
// JavaScript arrays are dynamic.
let myArray = []; // Initially empty

// Adding elements (amortized O(1))
myArray.push(10); // Array grows automatically
myArray.push(20);
myArray.push(30);
console.log("Current array:", myArray); // Output: [10, 20, 30]

// Accessing elements (O(1))
console.log("Element at index 1:", myArray[1]); // Output: 20

// Modifying elements (O(1))
myArray[0] = 100;
console.log("Modified array:", myArray); // Output: [100, 20, 30]

// Inserting at arbitrary position (O(N))
myArray.splice(1, 0, 15); // Insert 15 at index 1, removes 0 elements
console.log("After splice (insert):", myArray); // Output: [100, 15, 20, 30]

// Deleting at arbitrary position (O(N))
myArray.splice(1, 1); // Remove 1 element at index 1
console.log("After splice (delete):", myArray); // Output: [100, 20, 30]

Complexity (Dynamic Arrays):

Access (by index): O(1) - Same as fixed-size arrays.
Insertion/Deletion (at end): O(1) amortized. Most insertions are O(1), but occasional resize operations are O(N) (copying all elements), leading to an average O(1).
Insertion/Deletion (at beginning/middle): O(N) - Requires shifting elements, similar to fixed-size arrays.
Search (unsorted): O(N)
Search (sorted - binary search): O(log N)
Space Complexity: O(N) - Stores N elements, but typically over-allocates to allow for future growth.

Practical Usages:

Most common collection type in high-level languages (Python list, Java ArrayList, JavaScript Array).
Implementing stacks and queues.
Storing data where the exact size isn’t known beforehand or changes frequently.
Intermediate data storage during algorithm execution.

Note: The “amortized O(1)” time for appending to a dynamic array is a key concept. While individual resize operations are expensive (O(N)), they happen infrequently enough that the average cost per append operation over a sequence of appends effectively works out to be O(1). This is a great example of how analyzing worst-case vs. amortized complexity matters.

⚖️ Fixed vs. Dynamic: Choosing the Right Array

The choice between a fixed-size array and a dynamic array depends on your specific needs:

Feature	Fixed-Size Array	Dynamic Array
Size	Immutable, set at creation	Mutable, automatically grows/shrinks
Memory	Precisely allocated for `N` elements	Over-allocated (`>N` elements) to prevent frequent resizing
Insertion/End	O(1) (if space exists)	Amortized O(1) (with occasional O(N) resizes)
Insertion/Mid	O(N)	O(N)
Access by Index	O(1)	O(1)
Use Case	Known number of items, performance-critical buffers	Most general-purpose list scenarios

Key Considerations:

Predictable Size: If the number of items is truly fixed and known at compile-time or initialization, a fixed-size array is more memory-efficient and avoids resizing overhead.
Frequent Appends: Dynamic arrays excel here, providing good average performance despite occasional reallocations.
Memory Overhead: Dynamic arrays usually consume more memory than strictly necessary to maintain capacity for future growth.
Language Support: High-level languages often abstract away fixed-size arrays entirely, providing only dynamic array-like structures (e.g., Python lists).

Note: While dynamic arrays are incredibly versatile, if you frequently need to insert or delete elements in the middle of a large collection, other data structures like linked lists might offer better average-case time complexity for those specific operations (though often at the cost of O(N) access time by index).

Fixed-Size Array: items