List generic collection in C Sharp (C#) - Time & Space Complexity

Time Complexity: List generic collection

O(n)

Understanding Time Complexity

When working with a List in C#, it's important to know how the time to do actions changes as the list grows.

We want to understand how fast operations like adding or searching items happen as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

List<int> numbers = new List<int>();
for (int i = 0; i < n; i++)
{
    numbers.Add(i);
}
int index = numbers.IndexOf(target);
    

This code adds numbers from 0 to n-1 into a list, then searches for a target number's position.

Identify Repeating Operations

• Primary operation: Adding items in a loop and searching through the list.
• How many times: Adding happens n times; searching may check up to n items.

How Execution Grows With Input

Adding items grows roughly in a straight line with n, because each add is quick most times.

Searching grows in a straight line too, because it may check each item until it finds the target.

Input Size (n)	Approx. Operations
10	About 10 adds, up to 10 checks to find target
100	About 100 adds, up to 100 checks to find target
1000	About 1000 adds, up to 1000 checks to find target

Pattern observation: Both adding and searching grow linearly as the list size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to add or search grows directly with the number of items in the list.

Common Mistake

[X] Wrong: "Adding items to a List always takes the same time no matter how big it is."

[OK] Correct: Most adds are fast, but sometimes the list needs to resize its storage, which takes more time.

Interview Connect

Understanding how List operations scale helps you explain your choices clearly and shows you know how data grows in real programs.

Self-Check

"What if we used a LinkedList instead of a List? How would the time complexity for adding and searching change?"

Practice

1. What is the main feature of a List<T> in C#?

easy

A. It can only hold a fixed number of items.

B. It stores only unique items and does not allow duplicates.

C. It automatically sorts items when added.

D. It stores items in order and allows easy access by position.

Solution

1. Step 1: Understand List<T> behavior

   A List<T> stores items in the order they are added and allows access by index.

2. Step 2: Compare options with List<T> features

   Only It stores items in order and allows easy access by position. correctly describes this behavior; others describe different collection types or incorrect features.

3. Final Answer:

   It stores items in order and allows easy access by position. -> Option D

4. Quick Check:

   List<T> = ordered, indexed collection [OK]

Hint: Remember List<T> keeps order and supports indexing [OK]

Common Mistakes:

• Thinking List<T> enforces uniqueness
• Assuming List<T> auto-sorts items
• Believing List<T> has fixed size

2. Which of the following is the correct way to declare a List of integers in C#?

easy

A. List<int> numbers = new List<int>();

B. List numbers = new List<int>();

C. List<int> numbers = List<int>();

D. List<int> numbers = new List();

Solution

1. Step 1: Recall correct List<T> syntax

   In C#, to declare a generic List, you must specify the type and use the new keyword with constructor.

2. Step 2: Check each option for syntax correctness

   List<int> numbers = new List<int>(); correctly declares and initializes a List of int. Others miss type, constructor, or use wrong syntax.

3. Final Answer:

   List<int> numbers = new List<int>(); -> Option A

4. Quick Check:

   Generic List declaration = new List<T>() [OK]

Hint: Use new List<T>() with type specified [OK]

Common Mistakes:

• Omitting new keyword
• Not specifying generic type in constructor
• Using non-generic List without type

3. What will be the output of this C# code?

var fruits = new List<string> { "apple", "banana", "cherry" };
fruits.RemoveAt(1);
Console.WriteLine(fruits[1]);

medium

A. banana

B. IndexOutOfRangeException

C. cherry

D. apple

Solution

1. Step 1: Understand RemoveAt effect on list

   RemoveAt(1) removes the item at index 1, which is "banana". The list becomes ["apple", "cherry"].

2. Step 2: Access the item at index 1 after removal

   After removal, fruits[1] is "cherry" because the list shifted left.

3. Final Answer:

   cherry -> Option C

4. Quick Check:

   RemoveAt shifts items left, fruits[1] = cherry [OK]

Hint: RemoveAt shifts list left; index 1 now points to next item [OK]

Common Mistakes:

• Assuming removed item still exists
• Expecting original index items unchanged
• Confusing RemoveAt with Remove

4. Identify the error in this C# code snippet using List<string>:

List<string> colors = new List<string>();
colors.Add("red");
colors[1] = "blue";
Console.WriteLine(colors[1]);

medium

A. IndexOutOfRangeException because index 1 does not exist yet.

B. Syntax error in Add method usage.

C. Cannot assign string to List<string> element.

D. No error; code runs and prints 'blue'.

Solution

1. Step 1: Analyze list content after Add

   After colors.Add("red"), list has one element at index 0 only.

2. Step 2: Check assignment to colors[1]

   colors[1] does not exist yet, so assigning to it causes IndexOutOfRangeException.

3. Final Answer:

   IndexOutOfRangeException because index 1 does not exist yet. -> Option A

4. Quick Check:

   Assigning to non-existing index throws exception [OK]

Hint: List index must exist before assignment; use Add to add items [OK]

Common Mistakes:

• Trying to assign to index without adding
• Confusing Add and index assignment
• Expecting automatic list expansion

5. Given a List<int> named numbers containing {1, 2, 3, 4, 5}, which code snippet correctly doubles each number in the list?

hard

A. numbers = numbers.Select(n => n * 2).ToList();

B. for (int i = 0; i < numbers.Count; i++) { numbers[i] = numbers[i] * 2; }

C. foreach (int n in numbers) { n = n * 2; }

D. numbers.ForEach(n => n = n * 2);

Solution

1. Step 1: Understand how to modify List elements

   Using a for loop with index allows modifying elements directly by assignment.

2. Step 2: Evaluate each option's effect

   for (int i = 0; i < numbers.Count; i++) { numbers[i] = numbers[i] * 2; } modifies elements in place. foreach (int n in numbers) { n = n * 2; } modifies copy of elements (no effect). numbers = numbers.Select(n => n * 2).ToList(); creates a new list but requires LINQ and ToList(). numbers.ForEach(n => n = n * 2); modifies copies in ForEach (no effect).

3. Final Answer:

   for (int i = 0; i < numbers.Count; i++) { numbers[i] = numbers[i] * 2; } -> Option B

4. Quick Check:

   Use for loop with index to update List elements [OK]

Hint: Use for loop with index to update List items directly [OK]

Common Mistakes:

• Using foreach expecting to modify list items
• Using ForEach with lambda that doesn't assign back
• Not creating new list when using LINQ Select