📊 Arrays vs Linked Lists Fundamentals

🎯 The Two Foundational Linear Data Structures

Arrays are contiguous blocks of memory storing elements of the same type, allowing O(1) random access. Linked Lists are collections of nodes where each node contains data and a reference to the next node, allowing O(1) insertions/deletions at known positions.

Choosing the right data structure is critical for algorithm efficiency!

The Fundamental Trade-off

Arrays: Fast access, slow insertion/deletion (except at end). Fixed size (in static arrays).
Linked Lists: Slow access (O(n)), fast insertion/deletion if you have a reference to the node. Dynamic size.

Analogy: Array = parking lot with numbered spots (direct access). Linked List = treasure hunt where each clue tells you where the next is.

📌 Contiguous vs Non-contiguous📌 Random Access vs Sequential Access📌 Fixed vs Dynamic Size

# Array in Python (list)
arr = [10, 20, 30, 40, 50]
print(arr[2])        # O(1) - direct access
arr.insert(2, 25)    # O(n) - shifts elements
arr.pop(2)           # O(n) - shifts elements

# Singly Linked List implementation
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    def insert_at_head(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node        # O(1)
    
    def get(self, index):
        current = self.head
        for i in range(index):
            if not current:
                return None
            current = current.next
        return current.data if current else None  # O(n)

🔵 Arrays - Deep Dive

🎯 Contiguous Memory Storage

An array is a homogeneous data structure stored in contiguous memory locations. Each element can be accessed directly using its index because the address is calculated as: base_address + index × element_size.

Static Array Fixed size declared at compile time (C, C++ traditional)
Dynamic Array Grows automatically (Python list, Java ArrayList, C++ vector)
Multidimensional Arrays of arrays (matrices, grids)

# Array memory visualization
# arr = [10, 20, 30, 40]
# Memory: [10][20][30][40]
# Address: 1000, 1004, 1008, 1012 (assuming 4-byte ints)

# Static array (C-style simulation in Python)
import array
static_arr = array.array('i', [1, 2, 3, 4, 5])

# Dynamic array (Python list)
dynamic_arr = [1, 2, 3]
dynamic_arr.append(4)   # O(1) amortized
dynamic_arr.insert(1, 5)  # O(n)

# Cache friendliness - iterating is extremely fast
total = 0
for x in dynamic_arr:  # Sequential access - L1/L2 cache hits!
    total += x

🟠 Linked Lists - Deep Dive

🎯 Node-Based Dynamic Structure

A linked list consists of nodes where each node contains data and a pointer/reference to the next node. Nodes can be anywhere in memory — no contiguity requirement.

Singly Linked Each node points to next node only
Doubly Linked Each node points to next AND previous
Circular Linked Last node points back to head

# Complete Singly Linked List Implementation
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):  # O(n) - must traverse to end
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node
    
    def prepend(self, data):  # O(1)
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    def delete_value(self, data):  # O(n)
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        curr = self.head
        while curr.next and curr.next.data != data:
            curr = curr.next
        if curr.next:
            curr.next = curr.next.next
    
    def print_list(self):
        curr = self.head
        while curr:
            print(curr.data, end=" -> ")
            curr = curr.next
        print("None")

⚖️ Detailed Comparison Table

Operation	Array (Static)	Dynamic Array	Singly Linked List	Doubly Linked List
Access (by index)	O(1)	O(1)	O(n)	O(n)
Search (by value)	O(n)	O(n)	O(n)	O(n)
Insert at beginning	O(n)	O(n)	O(1)	O(1)
Insert at end	O(1)*	O(1) amortized	O(n)	O(1) with tail ptr
Insert at position	O(n)	O(n)	O(n)	O(n)
Delete at beginning	O(n)	O(n)	O(1)	O(1)
Delete at end	O(1)*	O(1) amortized	O(n)	O(1) with tail ptr
Delete at position	O(n)	O(n)	O(n)	O(n)
Memory overhead	Low	Low + slack	Per node (next ptr)	Per node (next + prev)
Cache locality	Excellent	Excellent	Poor	Poor

* Requires knowing the last index; O(n) if inserting/deleting not at end.

⏱️ Time & Space Complexities

🎯 Complexity Summary

Array (Static): Space O(n), Access O(1), Search O(n), Insert/Delete O(n)
Dynamic Array: Same plus amortized O(1) append, O(n) worst-case resize
Singly Linked List: Space O(n) + overhead, Access O(n), Insert/Delete at head O(1)
Doubly Linked List: Space O(n) + 2× overhead, O(1) insert/delete if node known

Amortized Analysis of Dynamic Arrays

When a dynamic array runs out of capacity, it allocates a larger array (typically 2×) and copies elements. Although a single append can be O(n), the average cost over many appends is O(1). This is called amortized analysis.

💻 Multiple Implementations

# 1. Static Array (using Python's array module)
import array
static = array.array('i', [1, 2, 3, 4, 5])

# 2. Dynamic Array (Python list with manual capacity)
class DynamicArray:
    def __init__(self, capacity=4):
        self.capacity = capacity
        self.size = 0
        self.arr = [None] * capacity
    
    def append(self, value):
        if self.size == self.capacity:
            self._resize(self.capacity * 2)
        self.arr[self.size] = value
        self.size += 1
    
    def _resize(self, new_capacity):
        new_arr = [None] * new_capacity
        for i in range(self.size):
            new_arr[i] = self.arr[i]
        self.arr = new_arr
        self.capacity = new_capacity

# 3. Singly Linked List (full implementation)
class SLL:
    class Node:
        __slots__ = ('data', 'next')
        def __init__(self, data):
            self.data = data
            self.next = None
    
    def __init__(self):
        self.head = None
        self.tail = None  # for O(1) append
        self.length = 0
    
    def append(self, data):  # O(1) with tail
        node = self.Node(data)
        if not self.head:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.length += 1
    
    def prepend(self, data):  # O(1)
        node = self.Node(data)
        node.next = self.head
        self.head = node
        if not self.tail:
            self.tail = node
        self.length += 1

🔄 Linked List Variants

Singly Linked List: Simplest, memory efficient, one-way traversal
Doubly Linked List: Two-way traversal, O(1) deletion of known node, more memory
Circular Linked List: Last node points to head, useful for round-robin scheduling
Skip List: Multiple layers for faster search O(log n) average
Unrolled Linked List: Each node stores an array of elements (better cache)

# Doubly Linked List Node
class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def delete_node(self, node):  # O(1) if you have reference
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev

💾 Memory Layout & Cache

🎯 Why Arrays Are Often Faster

Arrays benefit from spatial locality — contiguous memory means that when you access one element, the CPU cache loads a block of neighboring elements. Linked lists suffer from pointer chasing — each node could be anywhere in memory, causing frequent cache misses.

Array iteration: Sequential memory access → cache efficient
Linked list traversal: Random memory jumps → cache inefficient
Modern CPUs: Can be 10-100× faster iterating over arrays vs linked lists

🎯 When to Use Which

🎯 Choose Array When:

You need frequent random access by index
The size is known in advance or changes infrequently
Memory overhead is critical
You need cache efficiency (iterating through all elements)
Your operations are mostly reads, few insertions/deletions

🎯 Choose Linked List When:

You need frequent insertions/deletions at arbitrary positions
The size changes unpredictably and frequently
You don't need random access (only sequential access)
You're implementing a queue/stack with O(1) operations at ends
Memory fragmentation isn't a concern

📈 Dynamic Arrays (ArrayList/Vector)

🎯 The Best of Both Worlds?

Dynamic arrays (Python list, Java ArrayList, C++ vector) grow automatically while maintaining O(1) random access. They use amortized analysis — occasional O(n) resizes, but average O(1) append.

Growth factor: Typically 1.5× to 2× (trade-off between memory waste and resize frequency)
Shrink factor: Some implementations shrink when size < capacity/4

# Dynamic array growth visualization
# Initial capacity = 4
# Appends: [1] [2] [3] [4] (capacity 4)
# Append 5 → resize to 8, copy all elements O(4)
# Over 8 appends, total copy cost = 4 + 8 + 16 + ... = O(n) amortized

⚡ Operation Deep Dive

🎯 Why Insert/Delete are O(n) for Arrays

When inserting into the middle of an array, all elements after the insertion point must be shifted right. Similarly for deletion, elements shift left. This is O(n) in worst case.

🎯 Why Access is O(n) for Linked Lists

To access the i-th element, you must start from the head and follow next pointers i times — no direct indexing.

# Array insertion visualization
# [1, 2, 4, 5] insert 3 at index 2
# Step 1: Shift right: [1, 2, 4, 4, 5]
# Step 2: Insert: [1, 2, 3, 4, 5]

# Linked list insertion
# head -> 1 -> 2 -> 4 -> 5 -> None
# Insert 3 after 2:
# 2.next = new_node (3)
# new_node.next = 4
# Result: head -> 1 -> 2 -> 3 -> 4 -> 5 -> None

💪 Classic Problems & Algorithms

🎯 Array Problems

Two Sum, Container With Most Water
Sliding Window Maximum, Subarray Sum
Binary Search, Merge Sorted Arrays
Rotate Array, Reverse Array

🎯 Linked List Problems

Reverse a Linked List (iterative & recursive)
Detect Cycle (Floyd's Tortoise and Hare)
Find Middle Node, Find Kth from End
Merge Two Sorted Lists, Add Two Numbers
Remove Nth Node, Palindrome Linked List

# Floyd's Cycle Detection (Linked List)
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# Reverse a Linked List (iterative)
def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

🌐 Language-Specific Implementations

Python: list (dynamic array), no built-in linked list (use collections.deque for double-ended queue)
Java: ArrayList (dynamic array), LinkedList (doubly linked list)
C++: vector (dynamic array), list (doubly linked list)
C#: List<T> (dynamic array), LinkedList<T> (doubly linked list)
Go: slice (dynamic array), container/list (doubly linked list)
Rust: Vec (dynamic array), LinkedList (doubly linked, rarely used)

📝 Practice & Interview Patterns

🎯 Key Interview Questions

Arrays: Two pointers, sliding window, prefix sums, binary search, cyclic sort
Linked Lists: Runner technique (fast/slow pointers), dummy head, recursion, in-place reversal

# Two Pointers pattern (Array)
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        curr = arr[left] + arr[right]
        if curr == target:
            return [left, right]
        elif curr < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]

# Runner pattern (Linked List) - Find middle
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow