pkglog
KO

Arrays vs Linked Lists for Coding Interviews: Access Costs, Two Pointers and Common Traps

By · · 17 min read · Updated Beginner Tutorial

Key takeaways

Arrays and linked lists compared for interview use: indexing vs insertion costs, when each one wins, the practical techniques interviewers expect, and a graded list of problems to practice.

Why Start With Arrays and Linked Lists

Arrays show up in a large share of interview problems, not because interviewers love arrays, but because almost every other structure is built on top of them: a hash table is an array of buckets, a binary heap is an array with index arithmetic, and a stack is usually an array you only touch at one end. If you understand exactly what an array operation costs and why, most of the “trick” techniques later in a problem set turn out to be ways of avoiding the expensive operations (shifting elements, rescanning ranges) that this post describes.

Linked lists are the opposite trade-off. In real application code they are rarer than textbooks suggest, but interviewers use them to test whether you can manipulate pointers without losing nodes. This post covers what each structure really costs, the two-pointer, sliding-window and Kadane patterns that come up most often, and a few worked problems with the mistakes people usually make on them.

Arrays

What is an Array?

An array is the most basic data structure that stores elements of the same type in contiguous memory. Each element can be accessed directly via index.

The O(1) access follows directly from the layout: because every element has the same size and they sit next to each other, the address of element i is a single multiply-and-add away from the start. No search is involved, which is why arr[999999] costs the same as arr[0]. The same layout is what makes insertion expensive — there is no gap to put a new element into, so everything after the insertion point has to move.

Array Memory Structure:

Memory Address:  1000  1004  1008  1012  1016
Array Values:    [1]   [2]   [3]   [4]   [5]
Index:            0     1     2     3     4
Each element stored in contiguous memory
→ Address calculation: address = base + (index × element_size)
→ arr[2] address = 1000 + (2 × 4) = 1008

Arrays in Python Python’s list keeps a contiguous block of references to objects, allowing O(1) (constant time regardless of input size) access with just the index. The objects themselves (ints, strings) live elsewhere on the heap, so a list of a million integers is really a million pointers plus a million separately allocated int objects. That detail rarely matters for complexity, but it explains why a Python list uses far more memory than a C++ vector<int> of the same length, and why array.array or NumPy arrays exist when you need densely packed numbers.

# Python list is a dynamic array (auto-resizing)
arr = [1, 2, 3, 4, 5]
# Index access - O(1) time complexity
print(arr[0])  # 1 (first element)
print(arr[2])  # 3 (third element)
print(arr[-1]) # 5 (last element, negative index)
print(arr[-2]) # 4 (second from end)
# Slicing - extract subarray
print(arr[1:4])   # [2, 3, 4] (index 1-3)
print(arr[:3])    # [1, 2, 3] (start to index 2)
print(arr[2:])    # [3, 4, 5] (index 2 to end)
print(arr[::2])   # [1, 3, 5] (every 2nd element)
print(arr[::-1])  # [5, 4, 3, 2, 1] (reverse)

Arrays in C++:

// C++ static array (fixed size)
int arr[5] = {1, 2, 3, 4, 5};
cout << arr[0] << endl;  // 1
cout << arr[2] << endl;  // 3
// Size check (compile time - determined when building code)
int size = sizeof(arr) / sizeof(arr[0]);  // 5
// Out of bounds causes undefined behavior (dangerous!)
// cout << arr[10] << endl;  // garbage value or crash

The out-of-bounds line is the biggest behavioral difference between the two languages. Python checks every index and raises IndexError: list index out of range; C++ does not check arr[i] at all, so reading arr[10] silently returns whatever bytes happen to sit there, and writing to it can corrupt a neighbouring variable. In an online judge this often shows up not as a crash but as a wrong answer on a hidden test case, which is much harder to diagnose. When I am unsure about an index in C++, I temporarily switch to vector::at() (which throws std::out_of_range) or compile with -fsanitize=address locally, and only go back to [] once the boundaries are right. Also note that the sizeof(arr) / sizeof(arr[0]) trick only works where arr is still an array; once it is passed to a function it decays to a pointer and the expression returns the pointer size divided by the element size.

Array Characteristics

Advantages:

  • ✅ O(1) Index Access: Instant access with arr[i] (just address calculation)
  • ✅ Good Cache Efficiency: Contiguous memory loads into CPU cache at once
  • ✅ Simple and Intuitive: Most basic data structure, easy to understand
  • ✅ Memory Efficient: No pointer overhead (vs linked lists) Disadvantages:
  • ❌ Fixed Size (static arrays): Cannot change size after creation
  • ❌ O(n) Insertion/Deletion: Must shift remaining elements
  • ❌ Possible Memory Waste: Pre-allocating large size wastes unused space Time Complexity Summary: | Operation | Time Complexity | Description | |-----------|----------------|-------------| | Access (arr[i]) | O(1) | Direct index access | | Search (find value) | O(n) | Must traverse all elements | | Insert at front | O(n) | Shift all elements right | | Insert at back | O(1) | Dynamic array amortized O(1) | | Insert in middle | O(n) | Shift elements after position | | Delete | O(n) | Shift elements after position |

Dynamic Arrays

Dynamic arrays automatically grow in size. Python’s list, C++‘s vector, and Java’s ArrayList are all dynamic arrays. How Dynamic Arrays Work:

Initial state: capacity=4, size=0
[_][_][_][_]
append(1): [1][_][_][_]  size=1
append(2): [1][2][_][_]  size=2
append(3): [1][2][3][_]  size=3
append(4): [1][2][3][4]  size=4 (capacity full)
append(5): capacity insufficient → reallocate!
1. Allocate new memory (capacity=8, usually 2x)
2. Copy existing elements: [1][2][3][4][_][_][_][_]
3. Add new element: [1][2][3][4][5][_][_][_]
4. Free old memory

Amortized O(1) Meaning: Most append operations are O(1), but occasionally O(n) reallocation occurs. On average, it’s O(1).

The reason the average stays constant is the multiplicative growth. If capacity doubles, then to reach n elements you copied roughly n/2 + n/4 + n/8 + … < n elements in total across all reallocations, so each append paid for at most about one extra copy. If capacity grew by a fixed amount instead (say +10 each time), the total copying would be quadratic. Real implementations use factors between 1.125 and 2 (CPython over-allocates by roughly 1/8, GCC’s std::vector doubles), trading memory slack against the number of reallocations. Two practical consequences: in C++, a reallocation invalidates every pointer, reference and iterator into the vector, so holding &v[0] across a push_back is a classic bug; and if you know the final size up front, v.reserve(n) in C++ or building the list with a comprehension in Python avoids the repeated copies entirely. Python List Dynamic Array Operations:

# Python list (dynamic array)
arr = []
# Append to back - O(1) amortized
arr.append(1)
arr.append(2)
arr.append(3)
print(arr)  # [1, 2, 3]
# Add multiple elements
arr.extend([4, 5, 6])
print(arr)  # [1, 2, 3, 4, 5, 6]
# Insert in middle - O(n)
arr.insert(1, 10)  # Insert 10 at index 1
print(arr)  # [1, 10, 2, 3, 4, 5, 6]
# Remove by value - O(n)
arr.remove(10)  # Find and remove 10
print(arr)  # [1, 2, 3, 4, 5, 6]
# Delete by index - O(n)
del arr[0]  # Delete index 0
print(arr)  # [2, 3, 4, 5, 6]
# Pop from back - O(1)
arr.pop()  # Remove last element
print(arr)  # [2, 3, 4, 5]
# Length check - O(1)
print(len(arr))  # 4
# Value existence - O(n)
print(3 in arr)  # False (traverses to find)
print(4 in arr)  # True

The comments above are where most accidental O(n²) solutions come from. x in arr, arr.remove(x), arr.index(x), arr.insert(0, x) and arr.pop(0) all look like single cheap operations, but each one walks or shifts the list. Put one of them inside a loop over the same list and a 10⁵-element input turns into about 10¹⁰ steps, which is a guaranteed time-limit failure. The usual fixes are to keep a set alongside the list for membership checks, and to use collections.deque when you need to remove from the front.

Linked Lists

What is a Linked List?

A linked list is a data structure where nodes are connected via next pointers. While arrays are contiguous, linked lists are like treasure hunt cards - each card only tells you the next location.

Because each node knows only its successor, there is no address arithmetic: reaching the k-th node means following k pointers. In exchange, inserting or removing a node never moves any other node — you rewire one or two pointers and you are done. Note the append below walks the whole list to find the end, so it is O(n); real implementations keep a tail pointer to make appending O(1), which is the assumption behind the “insert at back” row of the comparison table later.

# Python implementation
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    
    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")
# Usage
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.print_list()  # 1 -> 2 -> 3 -> None

List Characteristics

Advantages:

  • ✅ O(1) Insertion/Deletion: Just change pointers (once you already hold the node)
  • ✅ No reallocation: grows one node at a time, and existing nodes never move Disadvantages:
  • ❌ O(n) Index Access: Requires sequential search
  • ❌ Poor Cache Efficiency: Memory scattered
  • ❌ Pointer Overhead: every element carries at least one extra pointer, often more than the payload itself for small values

The “O(1) insertion” advantage is weaker than it looks. To insert in the middle you first have to find the position, and finding it is O(n), so “insert after the 500th element” costs O(n) in both structures. The linked list only wins when you already hold a reference to the node — for example an LRU cache that keeps a hash map from key to node, or a scheduler that removes the node it is currently processing. On modern hardware, the array’s cache friendliness also means that shifting a few thousand contiguous integers is often faster than chasing the same number of scattered pointers, which is why std::vector is the default container in C++ and std::list is a deliberate, measured choice.

In interviews the difficulty with linked lists is almost never complexity; it is losing nodes. The failure I see most often is reassigning current.next before saving the old next, which cuts off the rest of the list — reversing a list is the standard test of this. Using a dummy head node (dummy = Node(0); dummy.next = head) removes the special case for inserting or deleting at the head, and drawing three boxes on paper before writing pointer assignments catches most ordering mistakes.

Time Complexity Comparison

OperationArrayLinked List
Access (index)O(1)O(n)
Search (value)O(n)O(n)
Insert at frontO(n)O(1)
Insert at backO(1) amortizedO(1)
Insert in middleO(n)O(1)*
Delete from frontO(n)O(1)
Delete from backO(1)O(n)
Delete from middleO(n)O(1)*

* When node position is known. “Insert at back” is O(1) for a list only with a tail pointer, and “delete from back” stays O(n) for a singly linked list even with one, because you need the second-to-last node; a doubly linked list makes both O(1).

Practical Techniques

Two Pointers

Two pointers use two indices to efficiently traverse arrays. Can optimize O(n²) → O(n).

The brute-force answer to “find two numbers that sum to target” checks every pair, which is n(n−1)/2 comparisons. Sorting gives you a monotonic property to exploit: if arr[left] + arr[right] is too small, no pair using arr[left] with anything left of right can work either, because those values are even smaller — so left can be discarded for good. Each step throws away one candidate permanently, which is why the loop runs at most n times. That “discard with proof” argument is what interviewers want you to say out loud; without it, two pointers looks like a guess.

Example: Two Sum in Sorted Array

def two_sum_sorted(arr, target):
    """
    Find indices of two numbers that sum to target in sorted array.
    
    Time: O(n)
    Space: O(1)
    """
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1  # Need larger value
        else:
            right -= 1  # Need smaller value
    
    return []
# Test
arr = [1, 2, 3, 4, 6]
target = 6
result = two_sum_sorted(arr, target)
print(result)  # [1, 3] (arr[1]=2, arr[3]=4, 2+4=6)

The condition is left < right, not <=: with <= the same element could be used twice (for target 4 and element 2). And this only works on sorted input. For the original LeetCode “Two Sum”, where the array is unsorted and the answer must be the original indices, sorting destroys the indices, so the standard solution is a single pass with a hash map from value to index — O(n) time but O(n) extra space.

Sliding Window

Sliding window moves a fixed-size window across the array. Optimizes O(n×k) → O(n).

The naive version recomputes sum(arr[i:i+k]) for every start position, repeating k−1 of the same additions each time. The sliding version keeps a running total and adjusts it by exactly two values per step: subtract the element leaving on the left, add the one entering on the right. The same idea generalizes to variable-size windows (“longest substring without repeating characters”, “smallest subarray with sum ≥ S”), where the right edge advances every step and the left edge advances only while a condition is violated — still O(n), because each index enters and leaves the window at most once. Example: Maximum Sum Subarray of Size k

def max_sum_subarray(arr, k):
    """
    Find maximum sum of subarray with size k.
    
    Time: O(n)
    Space: O(1)
    """
    if len(arr) < k:
        return None
    
    # Step 1: Calculate first window sum - O(k)
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Step 2: Slide window one position at a time - O(n-k)
    for i in range(k, len(arr)):
        # Move window: remove left, add right
        window_sum = window_sum - arr[i - k] + arr[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum
# Test
arr = [1, 4, 2, 10, 23, 3, 1, 0, 20]
k = 4
result = max_sum_subarray(arr, k)
print(f"Maximum sum: {result}")  # 39 (10+23+3+1)

The running-sum trick depends on subtraction being the inverse of addition. For a window maximum (LeetCode 239) you cannot “subtract” the element that leaves, so the window needs a monotonic deque instead; for a window with negative numbers and a variable size, the shrink condition may no longer be monotonic and you fall back to prefix sums with a hash map (LeetCode 560).

Maximum Subarray Sum (Kadane’s Algorithm)

Kadane’s algorithm finds maximum subarray sum in O(n) time.

The idea is a one-line dynamic program: current_sum is the best sum of a subarray that ends exactly at the current index. Such a subarray either extends the best one ending at the previous index or starts fresh at this element, and it starts fresh precisely when the previous best is negative, since a negative prefix can only drag the total down. Initializing with arr[0] rather than 0 matters: with 0, an all-negative array like [-3, -1, -2] would report 0 (the empty subarray) instead of −1, which is the wrong answer for problems that require a non-empty subarray.

def max_subarray_sum(arr):
    """
    Find maximum subarray sum (Kadane's Algorithm).
    
    Time: O(n)
    Space: O(1)
    """
    if not arr:
        return 0
    
    max_sum = current_sum = arr[0]
    
    for num in arr[1:]:
        # Key idea: add num to current sum or start fresh from num
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    
    return max_sum
# Test
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result = max_subarray_sum(arr)
print(result)  # 6 (subarray: [4, -1, 2, 1])

Worked Problems

Problem 1: Rotate Array

Problem: Rotate array to the right by k positions.

def rotate_array(arr, k):
    """
    Rotate array right by k positions.
    
    Example: [1,2,3,4,5], k=2 → [4,5,1,2,3]
    
    Time: O(n)
    Space: O(n) (slicing) or O(1) (in-place)
    """
    if not arr:
        return arr
    
    n = len(arr)
    k = k % n  # Handle k > n
    
    # Method 1: Slicing (simple but O(n) space)
    return arr[-k:] + arr[:-k]
# Test
arr = [1, 2, 3, 4, 5]
print(rotate_array(arr, 2))  # [4, 5, 1, 2, 3]

Two details catch people here. First, k % n is essential: rotating a 5-element array by 7 is the same as rotating by 2, and without the modulo the slice indices are simply wrong. Second, when k % n == 0 the slicing still works because arr[-0:] is arr[0:] (the whole list) and arr[:-0] is arr[:0] (empty) — correct by accident, but worth knowing in case you port it to another language. LeetCode 189 also asks you to modify the array in place and return nothing, so a solution that returns a new list is rejected even though it prints the right values; arr[:] = arr[-k:] + arr[:-k] assigns into the existing list object.

Method 2: Three Reversals (in-place, O(1) space)

Reversing the whole array puts the last k elements at the front, but each block is now backwards; reversing the two blocks separately restores their internal order. Every element is swapped at most twice, so it stays O(n) with no extra memory. Unlike the slicing version, this one needs a guard for an empty array before computing k % n, otherwise it raises ZeroDivisionError.

def rotate_array_inplace(arr, k):
    """
    Rotate array in-place (no extra memory).
    
    Algorithm:
    1. Reverse entire array
    2. Reverse first k elements
    3. Reverse remaining elements
    """
    n = len(arr)
    k = k % n
    
    def reverse(start, end):
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1
    
    reverse(0, n - 1)  # [1,2,3,4,5] → [5,4,3,2,1]
    reverse(0, k - 1)  # [5,4,3,2,1] → [4,5,3,2,1]
    reverse(k, n - 1)  # [4,5,3,2,1] → [4,5,1,2,3]
    
    return arr
# Test
arr = [1, 2, 3, 4, 5]
print(rotate_array_inplace(arr.copy(), 2))  # [4, 5, 1, 2, 3]

Problem 2: Remove Duplicates (Sorted Array)

This is the read/write-pointer variant of two pointers: read_idx scans every element, while write_idx marks where the next unique value belongs. Because the array is sorted, duplicates are adjacent, so comparing with the immediately preceding element is enough. The tempting alternative — calling arr.remove() or del arr[i] inside the loop — is both O(n²) and buggy, since deleting while iterating by index skips the element that slides into the deleted position.

def remove_duplicates(arr):
    """
    Remove duplicates from sorted array (in-place).
    
    Example: [1,1,2,2,3] → [1,2,3], return length 3
    
    Time: O(n)
    Space: O(1)
    """
    if not arr:
        return 0
    
    write_idx = 1
    
    for read_idx in range(1, len(arr)):
        if arr[read_idx] != arr[read_idx - 1]:
            arr[write_idx] = arr[read_idx]
            write_idx += 1
    
    return write_idx
# Test
arr = [1, 1, 2, 2, 3, 4, 4, 5]
length = remove_duplicates(arr)
print(f"New length: {length}")
print(f"Result: {arr[:length]}")
# Output:
# New length: 5
# Result: [1, 2, 3, 4, 5]

Problem 3: Merge Sorted Arrays

Each comparison moves exactly one element into the output, so the loop runs at most n + m times; when one side runs out, the rest of the other side is already sorted and can be appended in one go. Using < versus <= in the comparison decides which array wins ties, which matters when you need a stable merge (as in merge sort). Note that LeetCode 88 is a different shape of the same problem: it asks you to merge into nums1, which has spare room at the end, without extra space. The trick there is to fill from the back — compare the largest remaining elements and write them into the last free slot — so you never overwrite a value of nums1 you have not read yet.

def merge_sorted_arrays(arr1, arr2):
    """
    Merge two sorted arrays (Merge Sort's merge step).
    
    Example: [1,3,5], [2,4,6] → [1,2,3,4,5,6]
    
    Time: O(n + m)
    Space: O(n + m)
    """
    result = []
    i, j = 0, 0
    
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1
    
    result.extend(arr1[i:])
    result.extend(arr2[j:])
    
    return result
# Test
arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
result = merge_sorted_arrays(arr1, arr2)
print(result)  # [1, 2, 3, 4, 5, 6, 7, 8]

Summary

Key Points

  1. Arrays: Contiguous memory, O(1) index access, O(n) insertion/deletion
  2. Lists: Node connections, O(1) insertion/deletion, O(n) index access
  3. Two Pointers: O(n) traversal in sorted arrays
  4. Sliding Window: Optimize subarray problems
  5. Python list = Dynamic Array (same as C++ vector)

Problem-Solving Strategy

  1. Check Input Size: n ≤ 10³ → O(n²) is usually fine, n ≈ 10⁵ → aim for O(n log n) or better, n ≈ 10⁶ → O(n) needed
  2. Check if Sorted: If sorted, consider binary search, two pointers
  3. Space Complexity: If in-place required, use two pointers, sliding window

Next Steps

Beginner (Easy)

LeetCode:

Intermediate (Medium)

LeetCode:

Advanced (Hard)

LeetCode:

Frequently Asked Questions (FAQ)

Q. Why is inserting at the front of a Python list slow, and what should I use instead?

A. A Python list is a dynamic array, so insert(0, x) or pop(0) shifts every remaining element and costs O(n). Inside a loop that becomes O(n²) and is a common cause of timeouts. If you need to add or remove at both ends, use collections.deque, whose appendleft and popleft are O(1).