Linked List vs Array When to Choose Which in DSA C# - Complexity Comparison

Time Complexity: Linked List vs Array When to Choose Which

O(1) for array access/add, O(n) for linked list access/add at end

Understanding Time Complexity

We want to understand how the time to do operations changes when using a linked list versus an array.

Which data structure is faster for different tasks?

Scenario Under Consideration

Analyze the time complexity of adding and accessing elements in arrays and linked lists.

// Adding element at end of array
void AddToArray(int[] arr, int value, ref int size) {
    if (size < arr.Length) {
        arr[size] = value;
        size++;
    }
}

// Adding element at end of linked list
void AddToLinkedList(Node head, int value) {
    Node current = head;
    while (current.Next != null) {
        current = current.Next;
    }
    current.Next = new Node(value);
}

// Access element at index in array
int AccessArray(int[] arr, int index) {
    return arr[index];
}

// Access element at index in linked list
int AccessLinkedList(Node head, int index) {
    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.Next;
    }
    return current.Value;
}

This code shows adding elements at the end and accessing elements by index in arrays and linked lists.

Identify Repeating Operations

Look at loops and repeated steps in the code.

• Primary operation: Traversing nodes in linked list to reach the end or a specific index.
• How many times: For linked list add or access, it repeats up to n times where n is the list size.
• Array access and add at end do not loop; they do direct access.

How Execution Grows With Input

As the number of elements grows, the time to add or access changes differently for arrays and linked lists.

Input Size (n)	Array Add/Access	Linked List Add/Access
10	~1 operation (direct access)	Up to 10 operations (traversal)
100	~1 operation (direct access)	Up to 100 operations (traversal)
1000	~1 operation (direct access)	Up to 1000 operations (traversal)

Pattern observation: Array operations stay constant time, linked list operations grow linearly with size.

Final Time Complexity

Time Complexity: O(1) for array access/add, O(n) for linked list access/add at end

This means arrays are faster for direct access and adding at the end if space allows, while linked lists take longer as size grows.

Common Mistake

[X] Wrong: "Linked lists are always faster because they don't need resizing like arrays."

[OK] Correct: While linked lists avoid resizing, accessing or adding at the end requires walking through many nodes, which takes more time as the list grows.

Interview Connect

Understanding when to use arrays or linked lists shows you can pick the right tool for the job, a skill interviewers appreciate.

Self-Check

"What if we kept a pointer to the last node in the linked list? How would that change the time complexity for adding at the end?"

Practice

1. Which data structure is better when you need fast random access to elements by index?

easy

A. Array

B. Linked List

C. Stack

D. Queue

Solution

1. Step 1: Understand random access in arrays

   Arrays store elements in contiguous memory, so accessing any element by index is fast and direct.

2. Step 2: Compare with linked list access

   Linked lists require traversal from the head to reach an element, making random access slower.

3. Final Answer:

   Array -> Option A

4. Quick Check:

   Fast random access = Array [OK]

Hint: For fast index access, choose Array [OK]

Common Mistakes:

• Thinking linked list supports fast random access
• Confusing stack or queue with random access
• Assuming linked list nodes are contiguous

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

easy

A. List<int> list = new LinkedList<int>();

B. LinkedList<int> list = new LinkedList<int>();

C. LinkedList list = new List<int>();

D. List list = new LinkedList();

Solution

1. Step 1: Recall C# syntax for generic linked list

   The correct syntax uses LinkedList<T> with type parameter and new LinkedList<T>() to create an instance.

2. Step 2: Check each option for correctness

   LinkedList<int> list = new LinkedList<int>(); correctly declares and initializes a LinkedList<int>. Others mix types or omit generics.

3. Final Answer:

   LinkedList<int> list = new LinkedList<int>(); -> Option B

4. Quick Check:

   Correct generic linked list syntax = LinkedList<int> list = new LinkedList<int>(); [OK]

Hint: Use LinkedList<T> with new LinkedList<T>() [OK]

Common Mistakes:

• Mixing List and LinkedList types
• Omitting generic type parameter
• Using non-generic LinkedList without type

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

var list = new LinkedList<int>();
list.AddLast(10);
list.AddLast(20);
list.AddFirst(5);
foreach(var item in list) { Console.Write(item + " "); }

medium

A. 5 10 20

B. 10 20 5

C. 20 10 5

D. 5 20 10

Solution

1. Step 1: Trace linked list insertions

   First, 10 is added at the end, then 20 at the end, so list is [10, 20]. Then 5 is added at the front, making list [5, 10, 20].

2. Step 2: Output the list elements in order

   The foreach prints elements in order: 5, 10, 20 separated by spaces.

3. Final Answer:

   5 10 20 -> Option A

4. Quick Check:

   LinkedList order after AddFirst and AddLast = 5 10 20 [OK]

Hint: AddFirst puts element at start, AddLast at end [OK]

Common Mistakes:

• Assuming AddLast adds at front
• Confusing order of AddFirst and AddLast
• Forgetting foreach prints in list order

4. Identify the error in this code snippet that tries to add an element at index 2 in a linked list:

var list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
list.AddLast(3);
list.Add(2, 99);

medium

A. AddLast requires index parameter

B. AddLast cannot be called multiple times

C. List must be initialized with size

D. LinkedList does not have Add method with index parameter

Solution

1. Step 1: Check LinkedList methods in C#

   LinkedList<T> does not support Add with index; it only supports AddFirst, AddLast, or AddBefore/After nodes.

2. Step 2: Understand why Add(2, 99) causes error

   Calling Add with two parameters is invalid for LinkedList; this method exists in List<T> but not LinkedList.

3. Final Answer:

   LinkedList does not have Add method with index parameter -> Option D

4. Quick Check:

   LinkedList Add with index = invalid [OK]

Hint: LinkedList uses AddFirst/AddLast, no index Add [OK]

Common Mistakes:

• Using List methods on LinkedList
• Assuming Add can take index in LinkedList
• Confusing List<T> and LinkedList<T> APIs

5. You need to frequently insert and delete elements in the middle of a large collection. Which data structure is more efficient and why?

hard

A. Array, because it uses less memory

B. Array, because it allows fast random access

C. Linked List, because it allows fast insertions and deletions without shifting elements

D. Linked List, because it stores elements contiguously

Solution

1. Step 1: Analyze insertion and deletion in arrays

   Arrays require shifting elements after insertion or deletion in the middle, which is slow for large collections.

2. Step 2: Analyze linked list behavior

   Linked lists can insert or delete nodes by changing pointers without shifting, making these operations faster in the middle.

3. Final Answer:

   Linked List, because it allows fast insertions and deletions without shifting elements -> Option C

4. Quick Check:

   Fast middle insert/delete = Linked List [OK]

Hint: For frequent middle changes, choose Linked List [OK]

Common Mistakes:

• Choosing array for fast middle insert/delete
• Thinking linked list stores elements contiguously
• Ignoring cost of shifting in arrays