Back to all blogs
    2 min read

    Python for DSA — Lists

    PythonDsaListsArraysList-comprehension

    3. Lists

    💡 Why this matters for DSA Lists are the backbone of DSA in Python — stacks, queues, dynamic arrays, and matrices are all built on lists.

    3.1 Creating, Indexing & Slicing

    python
    arr = [1, 2, 3, 4, 5]

arr[0]        # 1
arr[-1]       # 5
arr[1:4]      # [2, 3, 4]
arr[::-1]     # [5, 4, 3, 2, 1] (reverse)
arr[::2]      # [1, 3, 5] (every other)

    ⚠️ Warning: Slicing a list creates a new copy (O(n)). Use it intentionally.

    Common initialization patterns

    python
    # Fixed-size list
zeros = [0] * 10          # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

# 2D grid (matrix)
grid = [[0] * 3 for _ in range(3)]  # [[0,0,0],[0,0,0],[0,0,0]]

# ❌ Wrong way — creates shared references!
bad = [[0] * 3] * 3       # Each row is the SAME list object

    🚨 Danger — The * trap for 2D lists:

    python
    bad = [[0] * 3] * 3
bad[0][0] = 1
print(bad)  # [[1,0,0],[1,0,0],[1,0,0]] — all rows changed!

    Always use list comprehension for 2D: [[0]*3 for _ in range(3)]

    3.2 Essential Methods

    python
    arr = [1, 2, 3]

arr.append(4)          # [1, 2, 3, 4]      O(1)
arr.pop()              # returns 4, arr = [1, 2, 3]   O(1)
arr.pop(0)             # returns 1, arr = [2, 3]      O(n)
arr.insert(0, 0)       # [0, 2, 3]          O(n)
arr.remove(2)          # [0, 3]             O(n) (removes first match)
arr.sort()             # in-place sort      O(n log n)
arr.reverse()          # in-place reverse   O(n)
arr.copy()             # shallow copy       O(n)

len(arr)               # 2                  O(1)

    ✅ Tip — Using list as a stack (LIFO):

    python
    stack = []
stack.append(1)      # push
stack.append(2)
stack.pop()          # pop → 2

    ✅ Tip — Using list as a queue (FIFO) — ❌ not recommended:

    python
    queue = []
queue.append(1)      # enqueue
queue.pop(0)         # dequeue → O(n)! Use collections.deque instead

    3.3 Shallow vs Deep Copy

    This is a common point of confusion. Understanding it saves hours of debugging.

    Shallow Copy (.copy(), [:], list())

    Copies the outer list, but inner lists are still shared references.

    python
    original = [[1, 2], [3, 4]]
shallow = original.copy()

shallow[0][0] = 99
print(original)   # [[99, 2], [3, 4]]  ❌ Changed!
print(shallow)    # [[99, 2], [3, 4]]

# Why? Because shallow[0] and original[0] point to the SAME list object.
    python
    # Visually:
original ──→ [  list_A  ,  list_B  ]
                 ↑           ↑
shallow  ──→ [  list_A  ,  list_B  ]

    Deep Copy (copy.deepcopy())

    Recursively copies everything — no shared references.

    python
    import copy

original = [[1, 2], [3, 4]]
deep = copy.deepcopy(original)

deep[0][0] = 99
print(original)   # [[1, 2], [3, 4]]  ✅ Unchanged!
print(deep)       # [[99, 2], [3, 4]]
    python
    # Visually:
original ──→ [  list_A  ,  list_B  ]
                                    
deep     ──→ [  list_C  ,  list_D  ]   (brand new inner lists)

    When to use what

    ScenarioUse
    1D list of primitivesarr.copy() or arr[:]
    2D list / nested listscopy.deepcopy(arr)
    You want to share inner structuresShallow copy intentionally

    ✅ Tip: For DSA, you'll mostly deal with 1D lists — shallow copy is usually enough. Deep copy becomes relevant when building complex state (backtracking, memoization).

    python
    # Basic
squares = [x**2 for x in range(5)]        # [0, 1, 4, 9, 16]

# With condition
evens = [x for x in range(10) if x % 2 == 0]  # [0, 2, 4, 6, 8]

# Nested loop (flattening)
flat = [x for row in matrix for x in row]

# With transformation
negatives = [-x for x in [1, -2, 3, -4]]   # [-1, 2, -3, 4]

    ✅ Tip — When to use list comprehension vs loop: Use comprehension for transforming one list to another. Use loop for side effects (printing, modifying in place).

    3.4 Nested Lists (Matrices)

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

matrix[0][1]     # 2  (row 0, col 1)
matrix[1]        # [4, 5, 6]  (entire row)

# Transpose
transposed = [[row[i] for row in matrix] for i in range(3)]

    Practice Drill

    python
    # 1. Find the largest element in a list
# 2. Remove duplicates from a list (order preserved)
# 3. Reverse a list in-place (without slicing)
# 4. Given a matrix, print all elements in spiral order (hard)
    💡 Click for Solutions
    python
    # 1. Largest element
arr = [3, 7, 2, 9, 5]
print(max(arr))     # 9

# 2. Remove duplicates (order preserved)
arr = [1, 2, 2, 3, 1, 4]
seen = set()
unique = []
for x in arr:
    if x not in seen:
        unique.append(x)
        seen.add(x)
print(unique)  # [1, 2, 3, 4]

# 3. Reverse in-place
arr = [1, 2, 3, 4, 5]
left, right = 0, len(arr) - 1
while left < right:
    arr[left], arr[right] = arr[right], arr[left]
    left += 1
    right -= 1
print(arr)  # [5, 4, 3, 2, 1]

# 4. Spiral matrix
def spiral_order(matrix):
    res = []
    while matrix:
        res += matrix.pop(0)
        if matrix and matrix[0]:
            for row in matrix:
                res.append(row.pop())
        if matrix:
            res += matrix.pop()[::-1]
        if matrix and matrix[0]:
            for row in matrix[::-1]:
                res.append(row.pop(0))
    return res

matrix = [[1,2,3],[4,5,6],[7,8,9]]
print(spiral_order(matrix))  # [1,2,3,6,9,8,7,4,5]

    ← Strings | Next → Tuples & Sets