Adding and removing list elements in Python - Time & Space Complexity

Time Complexity: Adding and removing list elements

O(n²)

Understanding Time Complexity

When we add or remove items from a list, the time it takes can change depending on how we do it.

We want to understand how the time grows as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_list = []

# Add elements to the end
for i in range(n):
    my_list.append(i)

# Remove elements from the start
for i in range(n):
    my_list.pop(0)

This code adds n elements to the end of a list, then removes n elements from the start one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding elements at the end with append and removing elements from the start with pop(0).
• How many times: Each operation runs n times in a loop.
• Dominant operation: Removing from the start (pop(0)) because it shifts all remaining elements each time.

How Execution Grows With Input

Adding at the end grows slowly, but removing from the start grows faster as the list gets bigger.

Input Size (n)	Approx. Operations
10	About 10 appends + 55 shifts when popping
100	About 100 appends + 5,050 shifts when popping
1000	About 1000 appends + 500,500 shifts when popping

Pattern observation: Appending grows linearly, but popping from the start grows roughly like the square of n because each pop shifts many elements.

Final Time Complexity

Time Complexity: O(n²)

This means the total time grows roughly like the square of the number of elements when removing from the start repeatedly.

Common Mistake

[X] Wrong: "Removing an element from the start of a list is as fast as removing from the end."

[OK] Correct: Removing from the start makes Python move all the other elements forward, which takes more time as the list grows.

Interview Connect

Understanding how list operations scale helps you choose the right data structure and write efficient code, a skill valued in many coding challenges.

Self-Check

What if we used a deque (double-ended queue) instead of a list for removing elements from the start? How would the time complexity change?

Practice

1. Which method adds an element to the end of a list in Python?

easy

A. append()

B. remove()

C. pop()

D. insert()

Solution

1. Step 1: Understand list addition methods

   The append() method adds an element at the end of the list.

2. Step 2: Differentiate from other methods

   remove() deletes by value, pop() deletes by position, and insert() adds at a specific position.

3. Final Answer:

   append() -> Option A

4. Quick Check:

   append() adds at end [OK]

Hint: append() always adds at the list's end [OK]

Common Mistakes:

• Confusing append() with insert()
• Using remove() to add elements
• Thinking pop() adds elements

2. Which of the following is the correct syntax to insert the value 10 at index 2 in list my_list?

easy

A. my_list.insert(10, 2)

B. my_list.append(2, 10)

C. my_list.insert(2, 10)

D. my_list.add(2, 10)

Solution

1. Step 1: Recall insert() method syntax

   The syntax is list.insert(index, value), so index comes first, then value.

2. Step 2: Match the correct order

   my_list.insert(2, 10) uses my_list.insert(2, 10), which is correct.

3. Final Answer:

   my_list.insert(2, 10) -> Option C

4. Quick Check:

   insert(index, value) correct order [OK]

Hint: insert() takes index first, then value [OK]

Common Mistakes:

• Swapping index and value
• Using append() with two arguments
• Using non-existent add() method

3. What will be the output of the following code?

numbers = [1, 2, 3, 4]
numbers.pop(1)
print(numbers)

medium

A. [1, 2, 3, 4]

B. [1, 3, 4]

C. [1, 2, 4]

D. [2, 3, 4]

Solution

1. Step 1: Understand pop() with index

   pop(1) removes the element at index 1, which is 2.

2. Step 2: Remove element and print list

   After removal, the list becomes [1, 3, 4].

3. Final Answer:

   [1, 3, 4] -> Option B

4. Quick Check:

   pop(1) removes second item [OK]

Hint: pop(index) removes element at that position [OK]

Common Mistakes:

• Thinking pop() removes by value
• Confusing index 1 with 2
• Expecting original list unchanged

4. The following code throws an error. What is the cause?

items = [5, 10, 15]
items.remove(20)
print(items)

medium

A. 20 is not in the list, so remove() causes an error

B. remove() requires index, not value

C. Syntax error in remove() usage

D. pop() should be used instead of remove()

Solution

1. Step 1: Understand remove() behavior

   remove() deletes the first occurrence of the given value.

2. Step 2: Check if value exists

   Value 20 is not in the list, so remove(20) raises a ValueError.

3. Final Answer:

   20 is not in the list, so remove() causes an error -> Option A

4. Quick Check:

   remove(value) fails if value missing [OK]

Hint: remove() fails if value not found in list [OK]

Common Mistakes:

• Thinking remove() removes by index
• Ignoring ValueError on missing value
• Using pop() incorrectly

5. You have a list data = [3, 5, 3, 7, 3]. You want to remove all occurrences of 3. Which code correctly does this without errors?

hard

A. data.remove(3) * 3

B. for i in range(len(data)):
if data[i] == 3:
data.remove(3)

C. data.pop(3)

D. while 3 in data:
data.remove(3)

Solution

1. Step 1: Understand removing all occurrences

   Using a while loop with 3 in data repeatedly removes 3 until none remain.

2. Step 2: Analyze other options

   for i in range(len(data)): if data[i] == 3: data.remove(3) modifies list during iteration causing skipped elements; C and D are incorrect usage.

3. Final Answer:

   while 3 in data: data.remove(3) -> Option D

4. Quick Check:

   Use while loop to remove all occurrences safely [OK]

Hint: Use while loop with 'in' to remove all occurrences [OK]

Common Mistakes:

• Removing items while iterating causes skips
• Using pop() with value instead of index
• Trying to multiply remove() call