Arrays and Lists

Arrays and Lists

An array is a data structure that stores elements in contiguous memory locations, providing O(1) constant-time access to any element through its index. Arrays are fundamental for managing collections of data of the same type.

Lists (dynamic arrays) build on arrays by providing automatic resizing, combining flexibility with all the speed advantages of indexed access.

Core Properties & Advantages:

• O(1) random access via index with direct mathematical address calculation
• Contiguous memory layout enhances cache performance and spatial locality
• Predictable operation times (most operations are constant-time)
• Homogeneous elements (fixed type) ensure layout and speed
• Resizable (for lists): Dynamic arrays grow as needed, typically by doubling capacity

Analogy: Think of arrays like a guitar rack where each guitar has a numbered position (0, 1, 2...). You can instantly grab any guitar by knowing its position number—no searching required.

Array Memory Layout

graph LR
    A["Base Address"] --> B["Index 0<br/>Element A"]
    B --> C["Index 1<br/>Element B"]
    C --> D["Index 2<br/>Element C"]
    D --> E["Index 3<br/>Element D"]

    F["Access Formula:<br/>address = base + (index × size)"] 

    style A fill:#e8f5e8
    style F fill:#c8e6c9

This diagram shows how arrays use contiguous memory and mathematical addressing for O(1) access.

Array Types Comparison

graph TD
    A["Array Types"] --> B["Static Arrays"]
    A --> C["Dynamic Arrays"]

    B --> D["Fixed Size<br/>Memory Efficient<br/>O(1) Operations"]
    C --> E["Auto Resizing<br/>Growth Strategy<br/>Amortized O(1) Append"]

    style D fill:#fff3e0
    style E fill:#e3f2fd

Static arrays offer maximum efficiency with fixed size, while dynamic arrays provide flexibility with automatic resizing.

Static vs Dynamic Arrays

Static Arrays

• Fixed size determined at creation
• Zero memory overhead - only exact space needed
• O(1) access, update
• Cannot resize after creation
• Examples: Java arrays

Dynamic Arrays (Lists)

• Automatic resizing as needed (growth strategy)
• Some memory overhead for unused capacity
• Amortized O(1) append operations
• Flexible size at runtime
• Examples: ArrayList (Java), Array (JS/TS), list (Python)

Dynamic Array Growth Process

graph LR
    A["Original Array<br/>Capacity: 4"] --> B["Add Element 5<br/>Capacity Exceeded"]
    B --> C["Allocate New Array<br/>Capacity: 8"]
    C --> D["Copy All Elements<br/>O(n) Operation"]
    D --> E["Add New Element<br/>Update References"]

    style A fill:#fff3e0
    style C fill:#e8f5e8
    style E fill:#c8e6c9

Dynamic arrays use exponential growth (typically doubling) to achieve amortized O(1) append operations.

Time Complexities

Operation	Static Array	Dynamic Array	Notes
Access by index	O(1)	O(1)	Direct memory calculation
Update by index	O(1)	O(1)	Direct memory access
Append	N/A	O(1) amortized	May trigger O(n) resize
Insert at index	N/A	O(n)	Shifts subsequent elements
Delete at index	N/A	O(n)	Shifts subsequent elements
Search	O(n)	O(n)	Linear scan for unsorted
Sort	O(n log n)	O(n log n)	Comparison-based sorting

Implementation Examples

JavaKotlinTypeScriptDartSwiftPython

import java.util.*;

// Static Array Declaration (fixed size)
String[] staticParts = new String[]{"Body", "Neck"};

// Dynamic Array (ArrayList) Operations
List<String> parts = new ArrayList<>(Arrays.asList("Body", "Neck"));

// Basic operations with O(1) complexity
parts.add("Bridge");                           // append - O(1) amortized
String first = parts.get(0);                    // access - O(1)
parts.set(1, "Maple Neck");                    // update - O(1)

// Operations requiring element shifting
parts.add(1, "Pickguard");                     // insert at index - O(n)
parts.remove(0);                                // delete at index - O(n)

// Query operations
boolean hasBridge = parts.contains("Bridge");   // membership check - O(n)
int size = parts.size();                        // get size - O(1)

// Sorting and manipulation
List<String> sorted = new ArrayList<>(parts);
Collections.sort(sorted);                       // sort (new copy) - O(n log n)
List<String> reversed = new ArrayList<>(parts);
Collections.reverse(reversed);                  // reverse (new copy) - O(n)

// 2D Array Operations
List<List<String>> skillTree = new ArrayList<>(Arrays.asList(
    Arrays.asList("C++", "Java", "Kotlin"),
    Arrays.asList("Neo4J", "SQL Server", "MongoDb")
));
String language = skillTree.get(0).get(1);      // access 2D element - O(1)

// Static Array Declaration
val staticParts = arrayOf("Body", "Neck")

// Dynamic Array (MutableList) Operations
val parts = mutableListOf("Body", "Neck")

// Basic operations with O(1) complexity
parts.add("Bridge")                         // append - O(1) amortized
val first = parts[0]                         // access - O(1)
parts[1] = "Maple Neck"                      // update - O(1)

// Operations requiring element shifting
parts.add(1, "Pickguard")                    // insert at index - O(n)
parts.removeAt(0)                            // delete at index - O(n)

// Query operations
val hasBridge = parts.contains("Bridge")     // membership check - O(n)
val size = parts.size                        // get size - O(1)

// Functional-style operations
val sorted = parts.sorted()                  // sort (new copy) - O(n log n)
val reversed = parts.reversed()              // reverse (new copy) - O(n)

// 2D Array Operations
val skillTree = listOf(
    listOf("C++", "Java", "Kotlin"),
    listOf("Neo4J", "SQL Server", "MongoDb")
)
val language = skillTree[0][1]               // access 2D element - O(1)

// Static-style Array Declaration (fixed content, but still resizable)
const staticParts: readonly string[] = ["Body", "Neck"];

// Dynamic Array Operations with type safety
const parts: string[] = ["Body", "Neck"];

// Basic operations with O(1) complexity
parts.push("Bridge");                        // append - O(1) amortized
const first = parts[0];                        // access - O(1)
parts[1] = "Maple Neck";                      // update - O(1)

// Operations requiring element shifting
parts.splice(1, 0, "Pickguard");              // insert at index - O(n)
parts.splice(0, 1);                           // delete at index - O(n)

// Query operations
const hasBridge = parts.includes("Bridge");    // membership check - O(n)
const size = parts.length;                     // get size - O(1)

// Functional operations (immutable style)
const sorted = [...parts].sort();             // sort (new copy) - O(n log n)
const reversed = [...parts].reverse();         // reverse (new copy) - O(n)

// 2D Array Operations with type annotations
const skillTree: string[][] = [
    ["C++", "Java", "Kotlin"],
    ["Neo4J", "SQL Server", "MongoDb"]
];
const language = skillTree[0][1];             // access 2D element - O(1)

// Fixed-length Array Declaration
List<String> staticParts = List.filled(2, "");
staticParts[0] = "Body";
staticParts[1] = "Neck";

// Dynamic Array (Growable List) Operations
List<String> parts = ["Body", "Neck"];

// Basic operations with O(1) complexity
parts.add("Bridge");                          // append - O(1) amortized
String first = parts[0];                      // access - O(1)
parts[1] = "Maple Neck";                      // update - O(1)

// Operations requiring element shifting
parts.insert(1, "Pickguard");                 // insert at index - O(n)
parts.removeAt(0);                            // delete at index - O(n)

// Query operations
bool hasBridge = parts.contains("Bridge");    // membership check - O(n)
int size = parts.length;                      // get size - O(1)

// Functional-style operations
List<String> sorted = List.from(parts)..sort(); // sort (new copy) - O(n log n)
List<String> reversed = parts.reversed.toList(); // reverse (new copy) - O(n)

// 2D Array Operations
List<List<String>> skillTree = [
    ["C++", "Java", "Kotlin"],
    ["Neo4J", "SQL Server", "MongoDb"]
];
String language = skillTree[0][1];             // access 2D element - O(1)

// Static Array Declaration (immutable)
let staticParts = ["Body", "Neck"]

// Dynamic Array Operations (mutable)
var parts = ["Body", "Neck"]

// Basic operations with O(1) complexity
parts.append("Bridge")                           // append - O(1) amortized
let first = parts[0]                              // access - O(1)
parts[1] = "Maple Neck"                          // update - O(1)

// Operations requiring element shifting
parts.insert("Pickguard", at: 1)                 // insert at index - O(n)
parts.remove(at: 0)                               // delete at index - O(n)

// Query operations
let hasBridge = parts.contains("Bridge")         // membership check - O(n)
let size = parts.count                            // get size - O(1)

// Functional operations (value semantics)
let sorted = parts.sorted()                       // sort (new copy) - O(n log n)
let reversed = Array(parts.reversed())            // reverse (new copy) - O(n)

// 2D Array Operations
let skillTree = [
    ["C++", "Java", "Kotlin"],
    ["Neo4J", "SQL Server", "MongoDb"]
]
let language = skillTree[0][1]                    // access 2D element - O(1)

# Array module for homogeneous data (memory efficient)
import array
static_numbers = array.array('i', [1, 2, 3])  # integer array

# Dynamic Array (List) Operations
parts = ["Body", "Neck"]

# Basic operations with O(1) complexity
parts.append("Bridge")              # append - O(1) amortized
first = parts[0]                    # access - O(1)
parts[1] = "Maple Neck"            # update - O(1)

# Operations requiring element shifting
parts.insert(1, "Pickguard")       # insert at index - O(n)
parts.pop(0)                       # delete at index - O(n)

# Query operations
has_bridge = "Bridge" in parts     # membership check - O(n)
size = len(parts)                  # get size - O(1)

# Sorting and manipulation
sorted_parts = sorted(parts)       # sort (new copy) - O(n log n)
reversed_parts = list(reversed(parts))  # reverse (new copy) - O(n)

# 2D Array Operations
skill_tree = [
    ["C++", "Java", "Kotlin"],
    ["Neo4J", "SQL Server", "MongoDb"]
]
language = skill_tree[0][1]       # access 2D element - O(1)

Applications

• Database Systems: Indexes, row storage, query optimization
• Web Development: DOM elements, state management, component rendering