Arrays

An array is one of the most fundamental data structures in programming. Everything else - stacks, queues, trees, graphs - builds on top of this idea.

This guide covers arrays in Python (called lists), how memory works behind the scenes, and the time complexity of every operation.

What is an Array?

An array is a collection where you store multiple values in one place, and each value has a numbered position called an index.

Think of it like a row of boxes, each box holding one value and having a number label on it.

Index:  0    1    2    3
Value: [10] [20] [30] [40]

You can reach any box instantly by its number - that is the superpower of arrays.

Arrays in Python - The List

In Python, the built-in list is how you work with arrays.

A list is:

• Ordered - keeps the order you put things in
• Mutable - you can change values after creating it
• Indexed - every element has a position number starting at 0
• Dynamic - grows and shrinks automatically
• Allows duplicates and mixed types

my_list = [1, 2, 3, 4]

Creating Lists

# Empty list
a = []
b = list()

# List with values
nums = [10, 20, 30]
mixed = [1, "hello", 3.5, True]

# Nested list (list inside a list)
nested = [1, [2, 3], [4, 5]]

Indexing - Accessing Elements

Every element has an index. Python uses 0-based indexing - the first element is at index 0.

arr = [10, 20, 30, 40]

arr[0]   # 10  (first element)
arr[1]   # 20
arr[-1]  # 40  (last element - negative index counts from end)
arr[-2]  # 30

Forward:   0    1    2    3
          [10] [20] [30] [40]
Backward: -4   -3   -2   -1

Slicing - Getting a Portion

Slicing lets you grab a chunk of the list.

arr[start : end : step]

start is included, end is NOT included.

arr = [10, 20, 30, 40, 50]

arr[1:3]    # [20, 30]       - index 1 and 2
arr[:2]     # [10, 20]       - from start up to index 2
arr[2:]     # [30, 40, 50]   - from index 2 to end
arr[::2]    # [10, 30, 50]   - every second element
arr[::-1]   # [50, 40, 30, 20, 10]  - reversed

Tip

arr[::-1] is the fastest way to reverse a list in Python. Interviewers love seeing this.

Modifying Elements

Lists are mutable, so you can change any element directly.

arr = [10, 20, 30]
arr[1] = 99
# arr is now [10, 99, 30]

List Methods - The Most Important Part

Adding Elements

# append - add ONE element to the end
arr.append(50)

# extend - add MULTIPLE elements to the end
arr.extend([60, 70])

# insert - add at a specific position
arr.insert(1, 15)   # insert 15 at index 1

Removing Elements

# remove - removes the FIRST occurrence of a value
arr.remove(20)   # error if value not found

# pop - removes and RETURNS the element
x = arr.pop()      # removes last element
y = arr.pop(1)     # removes element at index 1

# clear - removes everything
arr.clear()

Searching and Counting

arr.index(30)    # returns the index of 30
arr.count(10)    # how many times 10 appears

Sorting and Reversing

arr.sort()               # sort ascending, modifies original
arr.sort(reverse=True)   # sort descending

new = sorted(arr)        # returns NEW sorted list, original unchanged

arr.reverse()            # reverses in place

Copying Lists - A Common Mistake

This is one of the most common bugs beginners write.

# WRONG - both a and b point to the same list
b = a

# CORRECT - creates an independent copy
b = a.copy()
b = list(a)
b = a[:]

Why does the wrong way fail?

a --> [1, 2, 3]
b --> same memory location

# Change b[0] and a[0] also changes!

Caution

Always use .copy() or slicing [:] when you want a separate copy. Assignment (b = a) just creates another name for the same list.

List Operators

# Joining two lists
a = [1, 2]
b = [3, 4]
c = a + b    # [1, 2, 3, 4]

# Repeating a list
[1, 2] * 3   # [1, 2, 1, 2, 1, 2]

# Checking membership
10 in arr        # True if 10 is in arr
20 not in arr    # True if 20 is NOT in arr

Looping Over a List

arr = [10, 20, 30]

# Simple loop
for x in arr:
    print(x)

# Loop with index
for i in range(len(arr)):
    print(i, arr[i])

# Loop with both index and value (cleanest)
for i, x in enumerate(arr):
    print(i, x)

List Comprehension - Write Less, Do More

List comprehension is a shorter way to build lists. Interviewers love it.

# Syntax
[expression for item in iterable if condition]

# Squares of 0 to 4
squares = [x * x for x in range(5)]
# [0, 1, 4, 9, 16]

# Only even numbers
even = [x for x in arr if x % 2 == 0]

The same thing written as a regular loop:

result = []
for x in arr:
    if x % 2 == 0:
        result.append(x)

Both do the same thing. List comprehension is faster and cleaner.

Built-in Functions for Lists

len(arr)    # number of elements
max(arr)    # largest value
min(arr)    # smallest value
sum(arr)    # sum of all values

Nested Lists - 2D Arrays

A list can contain other lists. This is how you make a 2D grid or matrix.

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

matrix[0]     # [1, 2, 3]  - first row
matrix[1][2]  # 6           - row 1, column 2

Common Mistake - Modifying While Iterating

# WRONG - unpredictable behavior
for x in arr:
    arr.remove(x)

# CORRECT - build a new list
arr = [x for x in arr if x != value]

Address Calculation - How Memory Works

This is important for theory/exam questions. Every array element sits in memory at a specific address.

1D Array Formula

LOC(A[i]) = BA + (i - L) * w

Symbol	Meaning
BA	Base Address - where the array starts in memory
L	Lower bound (usually 0 in Python, but can be different)
i	Index of the element you want
w	Size of one element in bytes

Example: Array starts at address 100, element size = 4 bytes, lower bound = 0. Find address of index 3:

LOC(A[3]) = 100 + (3 - 0) * 4 = 100 + 12 = 112

2D Array - Row-Major Order

Most languages (C, Python) store 2D arrays row by row in memory.

LOC(A[i][j]) = BA + [(i - IL) * c + (j - JL)] * w

Symbol	Meaning
BA	Base Address
IL	Lower bound for rows
JL	Lower bound for columns
i	Row index
j	Column index
c	Total number of columns
w	Element size in bytes

2D Array - Column-Major Order

Some languages (Fortran, MATLAB) store column by column.

LOC(A[i][j]) = BA + [(j - JL) * r + (i - IL)] * w

Where r = total number of rows.

Note

The difference between row-major and column-major is just the order in which elements are laid out in memory. The formula flips the role of rows and columns.

Time Complexity of List Operations

This is what interviewers test you on.

Operation	Time	Why
Access by index arr[i]	O(1)	Direct memory jump using address formula
Append to end	O(1)	Adding at known position
Insert in middle	O(n)	All elements after must shift right
Delete from middle	O(n)	All elements after must shift left
Search (unsorted)	O(n)	May need to check every element
Sort	O(n log n)	Python uses TimSort
len()	O(1)	Stored separately

Tip

The reason access is O(1) is the address formula - you calculate the memory location directly instead of scanning through elements.

List vs Array Module

Python has an array module too. Here is the difference:

Feature	List	array module
Data types	Mixed (int, str, float, etc.)	Same type only
Speed	Slightly slower	Faster for numbers
Usage	General purpose	Numeric-heavy work

For DSA interviews, list is what you use. For heavy number crunching, NumPy arrays are even better.

When to Use a List

• You need a dynamic, growing collection
• You have mixed data types
• You need frequent append or remove at the end
• General-purpose storage

Quick Reference Cheat Sheet

Access is O(1)

Use index to jump directly to any element. No scanning needed.

Insert/Delete is O(n)

Middle insertions/deletions require shifting all elements after the point.

Copy carefully

Use .copy() or [:] - never b = a if you want a separate list.

List Comprehension

Faster and cleaner than a loop. Use it whenever building a new list from an old one.

Negative Indexing

arr[-1] is the last element. arr[-2] is second to last. Very useful in interviews.

Address Formula

LOC(A[i]) = BA + (i - L) * w. This is why index access is constant time.

Summary

Key Facts

• Python list = dynamic array
• 0-based indexing
• Mutable - elements can change
• Access is O(1), insert/delete in middle is O(n)
• Always copy with .copy() or [:]

Methods

• Add: append(), extend(), insert()
• Remove: remove(), pop(), clear()
• Search: index(), count()
• Sort: sort(), sorted(), reverse()
• Copy: .copy(), list(), [:]

Interview Tips

• Use arr[::-1] to reverse
• Use list comprehension instead of loops
• Always state time complexity for each operation
• For 2D arrays, know the row-major and column-major formulas
• sorted() does not modify original; sort() does

Tip

The single most important thing about arrays: index access is O(1) because of the address formula. Every other property follows from how memory is laid out.