Home

Step 1 of 6

17% Complete

Introduction to Arrays & ArrayLists

Learn about static arrays, dynamic arrays (ArrayLists), and their practical applications

What is an Array?

An array is a fundamental data structure that stores a collection of elements of the same data type in contiguous memory locations. Each element can be accessed directly by its index or position in the array.

Array Visualization

Size: 5 | Capacity: 10

[0]
10
[1]
20
[2]
30
[3]
40
[4]
50
[5]
—
[6]
—
[7]
—
[8]
—
[9]
—
Occupied
Available Capacity

In the visualization above, you can see a dynamic array with 5 elements stored in a capacity of 10 slots. Each element has an index starting from 0, and empty slots are shown as dashed borders. This demonstrates how arrays allocate memory and manage unused space.

Key Characteristics of Arrays

  • Homogeneous Elements: Arrays only store data of the same type (all integers, all strings, etc.)
  • Fixed Size (Static Arrays): Traditional arrays have a fixed size determined at creation time
  • Random Access: Elements can be accessed directly using their index in O(1) time
  • Contiguous Memory: Elements are stored in adjacent memory locations, making them cache-friendly
  • Dynamic Arrays (ArrayLists): Can resize automatically when capacity is exceeded

Static Array vs Dynamic Array (ArrayList)

Static Array

  • Fixed size determined at compile time
  • Memory allocated on stack or at compile time
  • Faster access (no bounds checking in some languages)
  • Less memory overhead
  • Cannot grow or shrink after creation

Dynamic Array (ArrayList)

  • Size can grow and shrink dynamically
  • Memory allocated on heap at runtime
  • Automatic resizing when capacity is reached
  • Built-in bounds checking
  • Slightly more memory overhead for management

In modern programming, dynamic arrays (like Java's ArrayList, Python's list, C++'s vector) are more commonly used because of their flexibility, while static arrays are used for performance-critical sections or when the size is known and fixed.

Basic Array Structure in Code

Array Implementation in Java
// Static Array
int[] staticArray = new int[5];  // Fixed size array of 5 integers
staticArray[0] = 10;
staticArray[1] = 20;
// staticArray[5] = 60;  // ERROR: ArrayIndexOutOfBoundsException
 
// Dynamic Array (ArrayList)
import java.util.ArrayList;
 
ArrayList<Integer> dynamicArray = new ArrayList<>();
dynamicArray.add(10);     // Adds 10 at the end
dynamicArray.add(20);     // Adds 20 at the end
dynamicArray.add(30);
dynamicArray.add(40);
dynamicArray.add(50);     // Can keep adding, ArrayList will resize automatically
 
// Access elements
int firstElement = dynamicArray.get(0);  // Gets element at index 0
dynamicArray.set(2, 35);                 // Updates element at index 2 to 35
 
// Remove elements
dynamicArray.remove(1);   // Removes element at index 1, shifts others

The code above shows the difference between static arrays and dynamic arrays (ArrayLists) in Java. Static arrays have fixed sizes, while ArrayLists can grow dynamically as elements are added.

How Dynamic Arrays Work (Resizing)

Resizing Strategy (Amortized Analysis)

When a dynamic array (ArrayList) runs out of capacity, it needs to resize. Most implementations use a doubling strategy:

  • When array is full, create a new array with double the capacity
  • Copy all elements from old array to new array
  • Continue adding elements to the new array
  • This gives amortized O(1) time for append operations
Initial: Size=0, Capacity=2
Add 1: Size=1, Capacity=2
Add 2: Size=2, Capacity=2
Add 3: Size=3, Capacity=4 (Resized!)
Add 4: Size=4, Capacity=4
Add 5: Size=5, Capacity=8 (Resized!)

Time Complexity Analysis

OperationStatic ArrayDynamic Array (ArrayList)Explanation
Access by IndexO(1)O(1)Direct memory address calculation
Insert at EndN/A (Fixed size)O(1)**Amortized, occasional O(n) for resizing
Insert at MiddleO(n)O(n)Need to shift elements
Delete from EndN/A (Fixed size)O(1)Simple size decrement
Delete from MiddleO(n)O(n)Need to shift elements
SearchO(n)O(n)Linear search through elements

Common Applications of Arrays

Data Storage

  • Storing collections of data
  • Database record storage
  • Image pixel data
  • Audio samples

Implementing Other DS

  • Stacks (LIFO)
  • Queues (FIFO)
  • Heaps (Priority Queues)
  • Hash Tables (buckets)

Algorithms

  • Sorting algorithms
  • Searching algorithms
  • Dynamic programming
  • Matrix operations

Advantages and Disadvantages

Advantages

  • Fast Random Access: O(1) time for accessing any element
  • Cache Friendly: Contiguous memory improves cache performance
  • Memory Efficient: Only stores data, minimal overhead
  • Simple Implementation: Easy to understand and use
  • Predictable Performance: Consistent access time

Disadvantages

  • Fixed Size (Static): Cannot resize after creation
  • Costly Insertions/Deletions: O(n) for middle operations
  • Memory Waste: May allocate more than needed
  • Resizing Cost (Dynamic): O(n) when capacity exceeded
  • Homogeneous Elements: Can't store different data types

Check Your Understanding

What is the time complexity for accessing an element by index in an array?

From the Course Notes

Key Points from CSC508 Topic 2: Array

  • Array Definition: A collection of a fixed number of components where all components have the same data type
  • Indexing: Array elements are accessed using indices ranging from 0 to n-1
  • Java ArrayList: Implements List interface using array as underlying structure
  • ArrayList Methods: add(), remove(), get(), set(), size(), indexOf()
  • User-defined Arrays: Can create custom array classes with specific operations

Source: CSC508 Data Structures - Topic 2: Array, Compiled by Zahid Zainal

Next Steps

Now that you understand the fundamentals of arrays and ArrayLists, let's move on to practicing array operations including insertion, deletion, searching, and understanding how dynamic resizing works in the next tutorial.

You'll learn about edge cases, common pitfalls, and optimization techniques for working with arrays in real-world applications.