minte9
LearnRemember   ALGORITHMS







PVM / Python / Data Structures / Lists

1. Reading lists O(1)

Accessing an item by list index takes a constant time: 1 step. The computer "jumps" directly to the memory address of that index (number). It's like opening a book to a specific page using a bookmark. Time complexity is O(1). 
 py
# Reading from a list O(1)
data = ["apples", "bananas", "oranges"]
known_index = 1

# Reading takes 1 step O(1)
found_item = data[known_index]          

print("Found item=", found_item)
print("Steps =", 1)

"""
    Found item= bananas
    Steps = 1
"""

2. Searching lists O(n)

Linear search from a list takes maximum n steps. Check each item one by one until you find the target (or reach the end). In the worst case, you look at every element which means N steps for N items. It's like looking for oranges in a grocery receipt by reading each line from top to bottom. In the worst case, when last item matched, time complexity is O(N). In the best case, when first item matched, time complexity is O(1). Use linear search when the list is unsorted. Use linear search when the list is small, so the overhead is negligible. 
 py
# Linear search in a list O(n)
fruits = ["apples", "bananas", "oranges"]

def search_value(items, value):
    for i in range(len(items)):
        if value == items[i]:
            return i  # Found: return index
    return -1

# Last item matched O(n)
item = "oranges"
index = search_value(fruits, item)
print(f"Found {item} at index {index}, steps = {index + 1}")

# First item matched O(1)
item = "apples"
index = search_value(fruits, item)
print(f"Found {item} at index {index}, steps = {index + 1}")

"""
    Found oranges at index 2, steps = 3
    Found apples at index 0, steps = 1
"""

Inserting lists O(n)

Inserting into a specific index in a list takes maximum n steps. To insert at position key, we first make space by shifting all elements from the right toward the end, then place the new value. There are up to n shifts (to move items and make space) +1 step (constant) to write the new value into position. As analogy, imagine a row of theater seats. To seat a new person in the middle, everyone to the right has to move over one seat. O(n) shifts grow with the number of elements to the right of key. Use when order matters and you must insert at a specific position. 
 py
# Insert in a list O(n)
fruits = ["apples", "bananas", "oranges"]

def add(data, k, value):
    steps = 0

    # Create new list to avoid list being changed in place (lists are mutable)
    items = data[:]  

    # aAdd one empty element at the end
    items.append("")
    
    # From end down to the k+1
    for i in range(len(items), k+1, -1):  # start, stop (required), step
        items[i-1] = items[i-2]           # shift elements one position to the right  
        steps += 1

    # place the new value in the gap
    items[k] = value
    steps += 1
    return items, steps

res, steps = add(fruits, 1, "kiwi")
print(res, steps)  

res, steps = add(fruits, 2, "kiwi")
print(res, steps)  

assert add(fruits, 1, "kiwi") == (['apples', 'kiwi', 'bananas', 'oranges'], 3)
assert add(fruits, 2, "lemons") == (['apples', 'bananas', 'lemons', 'oranges'], 2)

"""
    ['apples', 'kiwi', 'bananas', 'oranges'], 3
    ['apples', 'bananas', 'kiwi', 'oranges'], 2
"""

Deleting lists O(n)

Deleteing from a list at a specific index takes maximum n steps. This functon mutates the input list. To remove the item at key, we shift everything to its right one step left to cover the gap, then remove the non-duplicate last element. There are up to N-1 shifts (elements to the right of the key) +1 step to pop() the trailing duplicate. As analogy, pull a book from the middle of a tight shelf. Every book to the right slides left by one position to close the gap, then you tidy the end. O(N) is proportional to how many elements are to the right of key. 
 py
# Deleting from a list O(n)
fruits = ["apples", "bananas", "oranges"]

def delete_item(data, k):
    steps = 0

    for i in range(k, len(data)-1):
        data[i] = data[i+1]
        steps += 1

    # Remove the duplicate last element
    data.pop()
    
    steps += 1
    return steps

delete_item(fruits, 1)
print(fruits)  

"""
    ['apples', 'oranges']
"""




References: