What is the difference between arrays and lists?

Arrays use contiguous memory, lists use connected nodes. Arrays have O(1) index access, lists have O(1) insertion/deletion.

When to use arrays vs lists?

Use arrays for frequent random access, lists for frequent insertion/deletion. Most cases are fine with arrays (Python list).

Is Python list an array or a list?

Python list is a dynamic array, similar to C++ vector.

When to use two pointers?

Use for finding two numbers in sorted array, subarray problems. Optimizes O(n²) → O(n).

Arrays and Lists | Essential Data Structures for Coding Interviews

2026년 3월 28일 · 20분 읽기 · 수정 2026년 3월 28일 Beginner Tutorial

이 글의 핵심

Practical guide to arrays and lists. Complete coverage of essential data structures for coding interviews with detailed examples.

Introduction: The Most Fundamental Data Structure

”Knowing arrays alone solves 50% of coding interview problems”

Arrays and lists are the most fundamental and widely used data structures for storing and retrieving data. Over half of coding interview problems involve arrays.

What this article covers:

Array vs List differences
Time complexity analysis (how execution time grows with input size)
Two pointers (technique using two indices to traverse arrays), Sliding window (moving fixed-size window technique)
Real-world problem solving

Arrays
Linked Lists
Time Complexity Comparison
Practical Techniques
Problem Solving
Summary

1. 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.

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 stores values in contiguous memory, allowing O(1) (constant time regardless of input size) access with just the index. Like books on a shelf - you can grab any book instantly if you know its position.

# 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

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).

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

2. 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.

# 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
✅ No Size Limit
✅ Memory Efficient (only what’s needed)

Disadvantages:

❌ O(n) Index Access: Requires sequential search
❌ Poor Cache Efficiency: Memory scattered
❌ Pointer Overhead

3. Time Complexity Comparison

Operation	Array	Linked List
Access (index)	O(1)	O(n)
Search (value)	O(n)	O(n)
Insert at front	O(n)	O(1)
Insert at back	O(1) amortized	O(1)
Insert in middle	O(n)	O(1)*
Delete from front	O(n)	O(1)
Delete from back	O(1)	O(n)
Delete from middle	O(n)	O(1)*

* When node position is known

4. Practical Techniques

Two Pointers

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

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)

Sliding Window

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

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)

Maximum Subarray Sum (Kadane’s Algorithm)

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

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])

5. Problem Solving

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]

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

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)

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

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

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

Problem-Solving Strategy

Check Input Size: n ≤ 100 → O(n²) possible, n ≤ 10⁶ → O(n) needed
Check if Sorted: If sorted, consider binary search, two pointers
Space Complexity: If in-place required, use two pointers, sliding window

Next Steps

Stack and Queue
Hash Table
Binary Search

Keywords

Array, List, Linked List, Data Structure, Time Complexity, Two Pointers, Sliding Window, Kadane's Algorithm, Subarray, Dynamic Array, Python list, C++ vector, Coding Interview, Algorithm Problems

Arrays and Lists | Essential Data Structures for Coding Interviews

이 글의 핵심

Introduction: The Most Fundamental Data Structure

”Knowing arrays alone solves 50% of coding interview problems”

Table of Contents

1. Arrays

What is an Array?

Array Characteristics

Dynamic Arrays

2. Linked Lists

What is a Linked List?

List Characteristics

3. Time Complexity Comparison

4. Practical Techniques

Two Pointers

Sliding Window

Maximum Subarray Sum (Kadane’s Algorithm)

5. Problem Solving

Problem 1: Rotate Array

Problem 2: Remove Duplicates (Sorted Array)

Problem 3: Merge Sorted Arrays

Summary

Key Points

Problem-Solving Strategy

Next Steps

Recommended Problems (By Difficulty)

Beginner (Easy)

Intermediate (Medium)

Advanced (Hard)

Keywords

이 글의 핵심

Introduction: The Most Fundamental Data Structure

”Knowing arrays alone solves 50% of coding interview problems”

Table of Contents

1. Arrays

What is an Array?

Array Characteristics

Dynamic Arrays

2. Linked Lists

What is a Linked List?

List Characteristics

3. Time Complexity Comparison

4. Practical Techniques

Two Pointers

Sliding Window

Maximum Subarray Sum (Kadane’s Algorithm)

5. Problem Solving

Problem 1: Rotate Array

Problem 2: Remove Duplicates (Sorted Array)

Problem 3: Merge Sorted Arrays

Summary

Key Points

Problem-Solving Strategy

Next Steps

Recommended Problems (By Difficulty)

Beginner (Easy)

Intermediate (Medium)

Advanced (Hard)

Related Posts

Keywords