Arrays and Lists — Complete Guide

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

---

Table of Contents

1. Arrays
2. Linked Lists
3. Time Complexity Comparison
4. Practical Techniques
5. Problem Solving
6. 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

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 ≤ 100 → O(n²) possible, 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

• Stack and Queue
• Hash Table
• Binary Search

---

Recommended Problems (By Difficulty)

Beginner (Easy)

LeetCode:

• 1. Two Sum - Hash map usage
• 26. Remove Duplicates - Two pointers
• 27. Remove Element - In-place deletion
• 88. Merge Sorted Array - Array merging

Intermediate (Medium)

LeetCode:

• 53. Maximum Subarray - Kadane’s algorithm
• 121. Best Time to Buy and Sell Stock - Maximum profit
• 238. Product of Array Except Self - Prefix product
• 560. Subarray Sum Equals K - Prefix sum + hash map

Advanced (Hard)

LeetCode:

• 42. Trapping Rain Water - Two pointers
• 239. Sliding Window Maximum - Deque
• 295. Find Median from Data Stream - Two heaps

---

Related Posts

• Stack and Queue | Essential Data Structures
• Hash Table | O(1) Search Data Structure
• Binary Search | O(log n) Search in Sorted Arrays
• Two Pointers | Optimization Technique for Sorted Arrays
• Sliding Window | Solving Subarray Problems

---

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

---

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. Complete guide to arrays and lists for coding interviews. Master the fundamentals with principles, code examples, and pr… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

---

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

• 스택과 큐 | 코딩 테스트 필수 자료구조 완벽 정리
• 해시 테이블 | O(1) 탐색 자료구조 완벽 정리
• Python 자료형 | 리스트, 딕셔너리, 튜플, 세트 완벽 가이드
• C++ vector 기초 완벽 가이드 | 초기화·연산·용량 관리와 실전 패턴

---

이 글에서 다루는 키워드 (관련 검색어)

Algorithm, Data Structure, Array, List, Coding Interview, Python, C++ 등으로 검색하시면 이 글이 도움이 됩니다.