Linked List vs Array When to Choose Which in DSA C# - Trade-offs & Analysis

Mental Model

Arrays store items in order in one block of memory, making access fast but changes slow. Linked lists store items scattered in memory, connected by links, making changes fast but access slower.

Analogy: Think of an array like a row of mailboxes all in a line, easy to find any mailbox quickly. A linked list is like a treasure hunt where each clue points to the next location, so you must follow the clues to find the treasure.

Array: [1][2][3][4][5]
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> null

Dry Run Walkthrough

Input: Array: [1, 2, 3], Insert 4 at end; Linked List: 1 -> 2 -> 3, Insert 4 at end

Goal: Show how insertion at the end differs in arrays and linked lists

Step 1: Insert 4 at end of array by placing it in next free slot

[1][2][3][4] (array size increased if possible)

Why: Arrays need space at the end to add new item; if full, must create bigger array and copy

Step 2: Insert 4 at end of linked list by creating new node and linking last node to it

1 -> 2 -> 3 -> 4 -> null

Why: Linked list can add new node by changing last node's link without moving other nodes

Result:

Array: [1][2][3][4]
Linked List: 1 -> 2 -> 3 -> 4 -> null

Annotated Code

DSA C#

using System;

class Node {
    public int data;
    public Node next;
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    public Node head;

    public void InsertAtEnd(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode; // empty list, new node is head
            return;
        }
        Node curr = head;
        while (curr.next != null) {
            curr = curr.next; // move to last node
        }
        curr.next = newNode; // link last node to new node
    }

    public override string ToString() {
        Node curr = head;
        string result = "";
        while (curr != null) {
            result += curr.data + " -> ";
            curr = curr.next;
        }
        result += "null";
        return result;
    }
}

class Program {
    static void Main() {
        // Array insertion
        int[] arr = new int[4] {1, 2, 3, 0};
        arr[3] = 4; // insert 4 at end
        Console.WriteLine("Array: " + "[" + string.Join("][", arr) + "]");

        // Linked list insertion
        LinkedList list = new LinkedList();
        list.InsertAtEnd(1);
        list.InsertAtEnd(2);
        list.InsertAtEnd(3);
        list.InsertAtEnd(4);
        Console.WriteLine("Linked List: " + list.ToString());
    }
}

if (head == null) { head = newNode; return; }

handle empty linked list by setting head to new node

while (curr.next != null) { curr = curr.next; }

advance to last node in linked list

curr.next = newNode;

link last node to new node to insert at end

arr[3] = 4;

insert value at next free index in array

Output

Array: [1][2][3][4]

Linked List: 1 -> 2 -> 3 -> 4 -> null

Complexity Analysis

Time: O(1) for array insertion if space available, O(n) if resizing needed; O(n) for linked list insertion at end because we traverse to last node

Space: O(n) for both because they store n elements; arrays use contiguous memory, linked lists use extra space for pointers

vs Alternative: Arrays provide fast access by index but slow resizing; linked lists allow fast insertions/deletions but slow access by index

Edge Cases

Empty linked list

Insertion sets head to new node

DSA C#

if (head == null) { head = newNode; return; }

Array full, no space to insert

Need to create bigger array and copy elements (not shown in code)

DSA C#

arr[3] = 4; // assumes space available

When to Use This Pattern

When you need fast random access and know size in advance, use arrays; when you need frequent insertions or deletions without shifting, use linked lists.

Common Mistakes

Mistake: Trying to insert in array without checking if space is available
Fix: Ensure array has enough space or resize before inserting

Mistake: Not updating last node's next pointer in linked list insertion
Fix: Traverse to last node and set its next to new node

Summary

Arrays store elements in continuous memory for fast access; linked lists store elements scattered with links for flexible changes.

Use arrays when you need quick access by position and know size; use linked lists when you need frequent insertions or deletions.

The key insight is arrays are like mailboxes in a row, linked lists are like a chain of clues pointing to next.

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