Lists #

# Ways to create lists
empty = []
empty2 = list()

numbers = [1, 2, 3, 4, 5]
mixed = [42, "hello", 3.14, True, None]     # different types allowed
nested = [[1, 2], [3, 4], [5, 6]]           # lists inside lists

# From other iterables
from_range = list(range(1, 6))       # → [1, 2, 3, 4, 5]
from_string = list("Python")         # → ['P', 'y', 't', 'h', 'o', 'n']
from_tuple = list((1, 2, 3))         # → [1, 2, 3]
from_set = sorted(list({3, 1, 2}))   # → [1, 2, 3]

# List comprehensions
squares = [x**2 for x in range(1, 6)]          # → [1, 4, 9, 16, 25]
even = [x for x in range(10) if x % 2 == 0]   # → [0, 2, 4, 6, 8]

# Initializing lists with default values
ten_zeros = [0] * 10           # → [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
matrix = [[0] * 3 for _ in range(3)]  # → [[0,0,0], [0,0,0], [0,0,0]]

# ANTI-PATTERN: initializing a matrix with nested list multiplication
# ANTI-PATTERN: matrix = [[0] * 3] * 3
# All rows point to THE SAME OBJECT!
wrong_matrix = [[0] * 3] * 3
wrong_matrix[0][0] = 9
print(wrong_matrix)   # → [[9,0,0], [9,0,0], [9,0,0]] ← every row changed!

# CORRECT: use a comprehension for independent rows
right_matrix = [[0] * 3 for _ in range(3)]
right_matrix[0][0] = 9
print(right_matrix)   # → [[9,0,0], [0,0,0], [0,0,0]] ← only the first row

fruits = ["apple", "orange", "mango", "banana", "grape"]
#          0        1         2          3          4       ← positive indices
#         -5       -4        -3         -2         -1       ← negative indices

# Indexing
print(fruits[0])    # → apple    (first)
print(fruits[-1])   # → grape    (last)
print(fruits[-2])   # → banana   (second from the end)

# Slicing: [start:stop:step]
print(fruits[1:3])    # → ['orange', 'mango']    (indices 1 and 2)
print(fruits[:3])     # → ['apple', 'orange', 'mango']  (from the start)
print(fruits[2:])     # → ['mango', 'banana', 'grape']  (to the end)
print(fruits[::2])    # → ['apple', 'mango', 'grape']  (every 2nd)
print(fruits[::-1])   # → ['grape', 'banana', 'mango', 'orange', 'apple']  (reversed)
print(fruits[1:-1])   # → ['orange', 'mango', 'banana']  (except first & last)

# Slicing produces a NEW list — not a view like NumPy
a = [1, 2, 3, 4, 5]
b = a[1:4]   # copies elements at indices 1–3
b[0] = 99
print(a)     # → [1, 2, 3, 4, 5]  ← a is unchanged

# Slice assignment — modify part of a list without a loop
a = [1, 2, 3, 4, 5]
a[1:3] = [20, 30]        # replace indices 1–2
print(a)   # → [1, 20, 30, 4, 5]

a[1:3] = [10, 20, 30]    # replace 2 elements with 3
print(a)   # → [1, 10, 20, 30, 4, 5]

a[2:4] = []              # delete elements at indices 2–3
print(a)   # → [1, 10, 30, 4, 5]

lst = [1, 2, 3]

# append() — add one element at the end: O(1) amortized
lst.append(4)
print(lst)   # → [1, 2, 3, 4]

# extend() — add several elements from an iterable: O(k)
lst.extend([5, 6, 7])
print(lst)   # → [1, 2, 3, 4, 5, 6, 7]

# insert() — add at a specific index: O(n) because elements shift
lst.insert(0, 0)    # add 0 at the front
print(lst)   # → [0, 1, 2, 3, 4, 5, 6, 7]

# ANTI-PATTERN: + to add elements to an existing list
lst = [1, 2, 3]
lst = lst + [4]        # creates a NEW list every time — O(n)

for i in range(1000):
    lst = lst + [i]    # very slow for large loops!

# CORRECT: append() or extend() for in-place modification — O(1)
lst = [1, 2, 3]
lst.append(4)

result = []
for i in range(1000):
    result.append(i)    # O(1) per operation

# Or even better: a list comprehension
result = list(range(1000))

lst = [10, 20, 30, 20, 40, 20]

# remove() — remove the FIRST occurrence of a value: O(n)
lst.remove(20)
print(lst)   # → [10, 30, 20, 40, 20]  ← only the first one removed

# pop() — remove and return an element: O(1) at the end, O(n) in the middle
last = lst.pop()      # remove the last element → 20
print(last, lst)      # → 20 [10, 30, 20, 40]

element = lst.pop(1)  # remove the element at index 1 → 30
print(element, lst)   # → 30 [10, 20, 40]

# del — remove an element or a slice: O(n)
lst = [10, 20, 30, 40, 50]
del lst[1]            # remove index 1
print(lst)   # → [10, 30, 40, 50]

del lst[1:3]          # remove a slice
print(lst)   # → [10, 50]

# clear() — remove all elements: O(n)
lst.clear()
print(lst)   # → []

# ANTI-PATTERN: removing elements while iterating — elements get skipped!
numbers = [1, 2, 3, 4, 5, 6]
for n in numbers:
    if n % 2 == 0:
        numbers.remove(n)   # ← dangerous! modifying the list while iterating
print(numbers)   # → [1, 3, 5]  but not because it's right — there's a hidden bug
                 # Try [1, 2, 3, 4] → you get [1, 3] instead of [1, 3]

# CORRECT: build a new list (comprehension) or iterate over a copy
numbers = [1, 2, 3, 4, 5, 6]

# Way 1: list comprehension (most idiomatic)
numbers = [n for n in numbers if n % 2 != 0]
print(numbers)   # → [1, 3, 5]

# Way 2: filter()
numbers = list(filter(lambda n: n % 2 != 0, [1, 2, 3, 4, 5, 6]))

# Way 3: iterate over a copy (less efficient but sometimes needed)
numbers = [1, 2, 3, 4, 5, 6]
for n in numbers[:]:   # iterate over a copy
    if n % 2 == 0:
        numbers.remove(n)

fruits = ["apple", "orange", "mango", "orange", "banana"]

# Membership check: O(n)
print("mango" in fruits)      # → True
print("durian" not in fruits) # → True

# index() — index of the FIRST occurrence: O(n), errors if absent
print(fruits.index("orange")) # → 1
# fruits.index("durian")      # → ValueError: 'durian' is not in list

# Search safely using try/except or check first
if "durian" in fruits:
    idx = fruits.index("durian")

# count() — count occurrences: O(n)
print(fruits.count("orange")) # → 2
print(fruits.count("durian")) # → 0

# List length
print(len(fruits))   # → 5

numbers = [3, 1, 4, 1, 5, 9, 2, 6]

# sort() — sort IN-PLACE, returns None: O(n log n)
numbers.sort()
print(numbers)   # → [1, 1, 2, 3, 4, 5, 6, 9]

numbers.sort(reverse=True)
print(numbers)   # → [9, 6, 5, 4, 3, 2, 1, 1]

# sorted() — returns a NEW list, original unchanged: O(n log n)
original = [3, 1, 4, 1, 5]
sorted_list = sorted(original)
print(original)     # → [3, 1, 4, 1, 5]  ← unchanged
print(sorted_list)  # → [1, 1, 3, 4, 5]

# Sorting with a key — very flexible
students = [
    {"name": "Citra", "score": 78},
    {"name": "Ani",   "score": 92},
    {"name": "Budi",  "score": 85},
]

# Sort by score (descending)
by_score = sorted(students, key=lambda s: s["score"], reverse=True)
for s in by_score:
    print(f"{s['name']}: {s['score']}")
# → Ani: 92
# → Budi: 85
# → Citra: 78

# Sort by multiple criteria (name if scores tie)
data = [("Ani", 85), ("Budi", 92), ("Citra", 85), ("Dedi", 92)]
sorted_data = sorted(data, key=lambda x: (-x[1], x[0]))   # score DESC, name ASC
print(sorted_data)
# → [('Budi', 92), ('Dedi', 92), ('Ani', 85), ('Citra', 85)]

# reverse() — reverse order IN-PLACE: O(n)
lst = [1, 2, 3, 4, 5]
lst.reverse()
print(lst)   # → [5, 4, 3, 2, 1]

# Shallow copy — elements inside are still shared
original = [[1, 2], [3, 4], [5, 6]]

shallow_copy = original.copy()    # or: original[:]  or: list(original)
shallow_copy[0][0] = 99           # modify an element inside a sub-list

print(original)       # → [[99, 2], [3, 4], [5, 6]]  ← ALSO CHANGED!
print(shallow_copy)   # → [[99, 2], [3, 4], [5, 6]]

# Why? Because a shallow copy only copies the references to the sub-lists,
# not the sub-list objects themselves.

# Deep copy — copy the entire structure recursively
import copy

original = [[1, 2], [3, 4], [5, 6]]
deep_copy = copy.deepcopy(original)
deep_copy[0][0] = 99

print(original)     # → [[1, 2], [3, 4], [5, 6]]  ← unchanged!
print(deep_copy)    # → [[99, 2], [3, 4], [5, 6]]

# Practical implications of time complexity

# ANTI-PATTERN: repeated insert at the front of a list — O(n) per op = O(n²) total
result = []
for i in range(10000):
    result.insert(0, i)   # every insert shifts all elements — very slow!

# CORRECT: append at the back, then reverse once
result = []
for i in range(10000):
    result.append(i)
result.reverse()          # O(n) once — much faster

# Or use a deque if you frequently insert at both ends
from collections import deque
d = deque()
for i in range(10000):
    d.appendleft(i)      # O(1) per operation

from collections import deque

# A deque supports all list operations, PLUS O(1) operations at the front
queue = deque(["B", "C", "D"])

queue.appendleft("A")   # add at the front: O(1)
queue.append("E")       # add at the back: O(1)
print(queue)   # → deque(['A', 'B', 'C', 'D', 'E'])

queue.popleft()         # remove from the front: O(1)
queue.pop()             # remove from the back: O(1)
print(queue)   # → deque(['B', 'C', 'D'])

# rotate() — rotate elements
queue = deque([1, 2, 3, 4, 5])
queue.rotate(2)    # rotate 2 to the right
print(queue)   # → deque([4, 5, 1, 2, 3])

queue.rotate(-1)   # rotate 1 to the left
print(queue)   # → deque([5, 1, 2, 3, 4])

# maxlen — a bounded queue (sliding window)
log = deque(maxlen=3)   # keep at most the last 3 elements
for message in ["a", "b", "c", "d", "e"]:
    log.append(message)
print(log)   # → deque(['c', 'd', 'e'], maxlen=3)

import bisect

sorted_list = [1, 3, 5, 7, 9, 11]

# bisect_left / bisect_right — find an insertion position
pos = bisect.bisect_left(sorted_list, 6)   # → 3 (before 7)
pos = bisect.bisect_right(sorted_list, 5)  # → 3 (after 5)

# insort — insert while keeping the order: O(log n) search + O(n) shift
bisect.insort(sorted_list, 6)
print(sorted_list)   # → [1, 3, 5, 6, 7, 9, 11]

# Practical use: finding a value range
scores = [60, 70, 75, 80, 85, 90, 95]

def grade(score, thresholds=[60, 70, 80, 90], letters=["D", "C", "B", "A"]):
    """Convert a score to a letter using binary search."""
    return letters[bisect.bisect_left(thresholds, score)]

print(grade(85))   # → B
print(grade(92))   # → A
print(grade(65))   # → C

# zip two lists into a list of tuples
names = ["Budi", "Ani", "Citra"]
scores = [85, 92, 78]
pairs = list(zip(names, scores))
print(pairs)   # → [('Budi', 85), ('Ani', 92), ('Citra', 78)]

# Unzip again
names_back, scores_back = zip(*pairs)
print(list(names_back))    # → ['Budi', 'Ani', 'Citra']

# Flatten a nested list one level
nested = [[1, 2, 3], [4, 5], [6, 7, 8, 9]]
flat = [item for sub in nested for item in sub]
print(flat)   # → [1, 2, 3, 4, 5, 6, 7, 8, 9]

# Or with itertools.chain
from itertools import chain
flat = list(chain.from_iterable(nested))

# Remove duplicates while preserving order
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
unique_ordered = list(dict.fromkeys(data))
print(unique_ordered)   # → [3, 1, 4, 5, 9, 2, 6]
# dict.fromkeys preserves the order of first occurrence (Python 3.7+)