Hash Map vs Array vs Linked List for Lookup in DSA C# - Trade-offs & Analysis

Mental Model

Lookup means finding a value quickly. Arrays check positions directly, linked lists check one by one, and hash maps jump to the right spot using a key.

Analogy: Imagine looking for a book in a library: an array is like checking a specific shelf number, a linked list is like scanning books one by one on a shelf, and a hash map is like using a catalog that tells you exactly where the book is.

Array: [0] -> val0, [1] -> val1, [2] -> val2, ...
Linked List: val0 -> val1 -> val2 -> null
Hash Map: key1 -> bucket1 -> valX
          key2 -> bucket2 -> valY

Dry Run Walkthrough

Input: Lookup value 3 in structures containing values [1, 2, 3, 4]

Goal: Show how each structure finds value 3 and how fast it is

Step 1: Array checks index 2 directly

[0] -> 1, [1] -> 2, [2] -> [3 found] -> 3, [3] -> 4

Why: Array uses direct index to find value quickly

Step 2: Linked list starts at head and checks each node

1 -> [2] -> 2 -> 3 -> 4 -> null

Why: Linked list must check nodes one by one

Step 3: Linked list moves to next node

1 -> 2 -> [3 found] -> 3 -> 4 -> null

Why: Continue checking nodes until value is found

Step 4: Hash map uses key to find bucket and checks bucket

key3 -> bucketX -> [3 found]

Why: Hash map jumps directly to bucket using key

Result:

Array: found 3 at index 2
Linked List: found 3 after checking 3 nodes
Hash Map: found 3 directly in bucket

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    // Array lookup by value
    static int ArrayLookup(int[] arr, int value)
    {
        for (int i = 0; i < arr.Length; i++)
        {
            if (arr[i] == value)
                return i; // found at index i
        }
        return -1; // not found
    }

    // Linked list node
    class Node
    {
        public int val;
        public Node next;
        public Node(int v) { val = v; next = null; }
    }

    // Linked list lookup by traversal
    static Node LinkedListLookup(Node head, int value)
    {
        Node curr = head;
        while (curr != null)
        {
            if (curr.val == value)
                return curr; // found node
            curr = curr.next; // move to next node
        }
        return null; // not found
    }

    // Hash map lookup using Dictionary
    static bool HashMapLookup(Dictionary<int, int> map, int key, out int value)
    {
        return map.TryGetValue(key, out value); // direct lookup
    }

    static void Main()
    {
        int[] arr = {1, 2, 3, 4};
        Console.WriteLine("Array lookup for 3 at index: " + ArrayLookup(arr, 3));

        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        Node foundNode = LinkedListLookup(head, 3);
        Console.WriteLine("Linked list lookup for 3: " + (foundNode != null ? "found" : "not found"));

        var map = new Dictionary<int, int> {{1, 1}, {2, 2}, {3, 3}, {4, 4}};
        if (HashMapLookup(map, 3, out int val))
            Console.WriteLine("Hash map lookup for key 3: found value " + val);
        else
            Console.WriteLine("Hash map lookup for key 3: not found");
    }
}

if (arr[i] == value) return i; // found at index i

check each array element until value found

while (curr != null) { if (curr.val == value) return curr; curr = curr.next; }

traverse linked list nodes until value found or end

return map.TryGetValue(key, out value);

directly check hash map bucket for key

Output

Array lookup for 3 at index: 2

Linked list lookup for 3: found

Hash map lookup for key 3: found value 3

Complexity Analysis

Time: Array: O(n) because we may check each element; Linked List: O(n) because we traverse nodes one by one; Hash Map: O(1) average because it jumps directly to bucket

Space: Array: O(n) for storing elements; Linked List: O(n) for nodes with pointers; Hash Map: O(n) for buckets and entries

vs Alternative: Hash map is faster for lookup than array or linked list because it avoids scanning elements; array is faster than linked list for direct index access but slower if searching by value

Edge Cases

Empty array or linked list

Lookup returns not found quickly

DSA C#

while (curr != null) { ... } in LinkedListLookup

Value not present in structure

Lookup returns -1 or null or false indicating not found

DSA C#

return -1; in ArrayLookup and return null; in LinkedListLookup

Hash map key missing

TryGetValue returns false safely

DSA C#

return map.TryGetValue(key, out value);

When to Use This Pattern

When a problem asks for fast lookup by key or value, consider hash maps for average O(1) speed, arrays for index-based access, and linked lists when order and easy insertion matter but lookup is slower.

Common Mistakes

Mistake: Assuming linked list lookup is as fast as array lookup
Fix: Remember linked list requires checking nodes one by one, so it's slower for lookup

Mistake: Using array index to lookup value without knowing the index
Fix: Use search loop or hash map if index is unknown

Summary

Compares how hash maps, arrays, and linked lists find values.

Use hash maps for fast key-based lookup, arrays for direct index access, and linked lists when insertion order matters.

Hash maps jump directly to data, arrays use index, linked lists check nodes one by one.

Practice

1. Which data structure provides the fastest average lookup time for a key-value pair?

easy

A. Stack

B. Array

C. Linked List

D. Hash Map

Solution

1. Step 1: Understand lookup times for each data structure

   Hash Map uses hashing to find keys quickly, averaging O(1) time. Arrays require searching or indexing, O(1) if index known but O(n) if searching by value. Linked Lists require traversal, O(n) time.

2. Step 2: Compare average lookup times

   Hash Map is fastest on average for key-value lookup due to direct hashing. Arrays and Linked Lists are slower for key-based lookup.

3. Final Answer:

   Hash Map -> Option D

4. Quick Check:

   Fastest lookup = Hash Map [OK]

Hint: Hash Map uses hashing for O(1) average lookup [OK]

Common Mistakes:

• Confusing array index lookup with key lookup
• Assuming linked list lookup is fast
• Ignoring average vs worst-case lookup times

2. Which of the following is the correct way to declare a HashMap (Dictionary) in C#?

easy

A. var map = new Dictionary();

B. var map = new HashMap();

C. var map = new Map();

D. var map = new Array();

Solution

1. Step 1: Recall C# syntax for dictionary declaration

   C# uses Dictionary class for hash maps, declared as new Dictionary().

2. Step 2: Check each option for correctness

   var map = new Dictionary(); uses Dictionary correctly. Options A and C use non-existent classes HashMap and Map. var map = new Array(); uses Array incorrectly.

3. Final Answer:

   var map = new Dictionary(); -> Option A

4. Quick Check:

   C# Dictionary syntax = var map = new Dictionary(); [OK]

Hint: Use Dictionary for hash maps in C# [OK]

Common Mistakes:

• Using Java or other language classes like HashMap
• Confusing Map with Dictionary
• Trying to use Array for key-value pairs

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

var list = new LinkedList<int>();
list.AddLast(10);
list.AddLast(20);
list.AddLast(30);

bool found = list.Contains(20);
Console.WriteLine(found);

medium

A. 20

B. True

C. False

D. Compilation Error

Solution

1. Step 1: Understand LinkedList operations

   Elements 10, 20, 30 are added to the linked list. The Contains method checks if 20 exists in the list.

2. Step 2: Evaluate the Contains method result

   Since 20 was added, Contains(20) returns true. Console.WriteLine prints True.

3. Final Answer:

   True -> Option B

4. Quick Check:

   list.Contains(20) = True [OK]

Hint: LinkedList.Contains returns true if element exists [OK]

Common Mistakes:

• Assuming Contains returns the element instead of bool
• Confusing AddLast with AddFirst
• Expecting output 20 instead of True

4. Identify the error in this C# code snippet that tries to find a value in an array:

int[] arr = {1, 2, 3, 4};
if(arr.Contains(5))
{
    Console.WriteLine("Found");
}

medium

A. Contains method returns index, not bool

B. Array does not have Contains method

C. Contains method requires using System.Linq namespace

D. Array must be converted to List before Contains

Solution

1. Step 1: Check if Array.Contains is available by default

   Array itself does not have Contains method unless System.Linq is used which adds extension methods.

2. Step 2: Identify missing namespace

   Without 'using System.Linq;', Contains method call causes a compile error. Adding the namespace fixes it.

3. Final Answer:

   Contains method requires using System.Linq namespace -> Option C

4. Quick Check:

   Missing System.Linq causes Contains error [OK]

Hint: Add 'using System.Linq;' to use Contains on arrays [OK]

Common Mistakes:

• Thinking Array has Contains by default
• Confusing Contains return type
• Trying to convert array unnecessarily

5. You need to store a large collection of unique user IDs and quickly check if a user ID exists. Which data structure is best and why?

Choose the best option:

hard

A. Hash Map (Dictionary), because it provides O(1) average lookup time for existence checks

B. Linked List, because it allows easy insertion and deletion

C. Stack, because it supports fast push and pop operations

D. Array, because it uses less memory and supports fast index lookup

Solution

1. Step 1: Analyze requirements for storing unique IDs and fast existence check

   We need to quickly check if a user ID exists, so lookup speed is critical. Also, uniqueness is important.

2. Step 2: Compare data structures for lookup efficiency and uniqueness

   Array requires linear search for existence, O(n). Linked List also O(n). Stack is LIFO, not suitable for lookup. Hash Map (Dictionary) offers O(1) average lookup and can enforce uniqueness by keys.

3. Final Answer:

   Hash Map (Dictionary), because it provides O(1) average lookup time for existence checks -> Option A

4. Quick Check:

   Fast unique lookup = Hash Map [OK]

Hint: Use Hash Map for fast unique key existence checks [OK]

Common Mistakes:

• Choosing array for fast lookup without key index
• Confusing insertion speed with lookup speed
• Selecting stack which is not for lookup