Hash Map vs Array vs Linked List for Lookup in DSA C# - Build Both Approaches

Hash Map vs Array vs Linked List for Lookup

📖 Scenario: Imagine you run a small library. You want to quickly find if a book is available by its title. You will compare three ways to store and look up books: an array, a linked list, and a hash map.

🎯 Goal: You will create three data structures to store book titles. Then, you will write code to check if a specific book is in each structure. Finally, you will print the results to see which method finds the book fastest.

📋 What You'll Learn

Create an array of book titles

Create a linked list of book titles

Create a hash map (dictionary) of book titles

Write lookup code to check if a book is in each data structure

Print the lookup results for each data structure

💡 Why This Matters

🌍 Real World

Libraries, stores, and apps often need to quickly find items by name or ID. Choosing the right data structure helps make searches fast and efficient.

💼 Career

Understanding how arrays, linked lists, and hash maps work for lookup is essential for software developers to write efficient code and optimize performance.

1

Create the book data structures

Create an array called bookArray with these exact titles: "C# Basics", "Data Structures", "Algorithms". Then create a linked list called bookLinkedList with the same titles in the same order. Finally, create a dictionary called bookHashMap with the titles as keys and true as values.

DSA C#

# Create bookArray, bookLinkedList, and bookHashMap with the given titles
# Your code here

Hint

Use string[] for the array, LinkedList<string> for the linked list, and Dictionary<string, bool> for the hash map.

2

Set the book to search for

Create a string variable called searchBook and set it to "Data Structures".

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string[] bookArray = { "C# Basics", "Data Structures", "Algorithms" };

        LinkedList bookLinkedList = new LinkedList();
        bookLinkedList.AddLast("C# Basics");
        bookLinkedList.AddLast("Data Structures");
        bookLinkedList.AddLast("Algorithms");

        Dictionary bookHashMap = new Dictionary
        {
            { "C# Basics", true },
            { "Data Structures", true },
            { "Algorithms", true }
        };

        // Create searchBook variable
        // Your code here
    }
}

Hint

Use string searchBook = "Data Structures"; to set the book to find.

3

Check if the book is in each data structure

Write code to check if searchBook is in bookArray, bookLinkedList, and bookHashMap. Create three boolean variables: foundInArray, foundInLinkedList, and foundInHashMap. Use Array.Exists for the array, bookLinkedList.Contains for the linked list, and bookHashMap.ContainsKey for the hash map.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string[] bookArray = { "C# Basics", "Data Structures", "Algorithms" };

        LinkedList bookLinkedList = new LinkedList();
        bookLinkedList.AddLast("C# Basics");
        bookLinkedList.AddLast("Data Structures");
        bookLinkedList.AddLast("Algorithms");

        Dictionary bookHashMap = new Dictionary
        {
            { "C# Basics", true },
            { "Data Structures", true },
            { "Algorithms", true }
        };

        string searchBook = "Data Structures";

        // Check if searchBook is in each data structure
        // Your code here
    }
}

Hint

Use Array.Exists(bookArray, book => book == searchBook) for the array lookup.

Use bookLinkedList.Contains(searchBook) for the linked list lookup.

Use bookHashMap.ContainsKey(searchBook) for the hash map lookup.

4

Print the lookup results

Print the values of foundInArray, foundInLinkedList, and foundInHashMap each on its own line using Console.WriteLine. The output should be exactly True or False for each line.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string[] bookArray = { "C# Basics", "Data Structures", "Algorithms" };

        LinkedList bookLinkedList = new LinkedList();
        bookLinkedList.AddLast("C# Basics");
        bookLinkedList.AddLast("Data Structures");
        bookLinkedList.AddLast("Algorithms");

        Dictionary bookHashMap = new Dictionary
        {
            { "C# Basics", true },
            { "Data Structures", true },
            { "Algorithms", true }
        };

        string searchBook = "Data Structures";

        bool foundInArray = Array.Exists(bookArray, book => book == searchBook);
        bool foundInLinkedList = bookLinkedList.Contains(searchBook);
        bool foundInHashMap = bookHashMap.ContainsKey(searchBook);

        // Print the results
        // Your code here
    }
}

Hint

Use Console.WriteLine(foundInArray);, Console.WriteLine(foundInLinkedList);, and Console.WriteLine(foundInHashMap); to print each result on its own line.

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