Hash Map vs Array vs Linked List for Lookup in DSA Java - Visual Comparison

Concept Flow - Hash Map vs Array vs Linked List for Lookup

Start Lookup

↓

Index

↓

Direct

↓

Access

↓

Return

↓

Value

↓

End Lookup

Lookup starts and chooses data structure: Array uses direct index, Linked List traverses nodes, Hash Map uses hash key to find bucket, then returns value.

Execution Sample

DSA Java

int lookupArray(int[] arr, int index) {
  return arr[index];
}

class Node {
  int key;
  String value;
  Node next;
  Node(int key, String value) {
    this.key = key;
    this.value = value;
    this.next = null;
  }
}

String lookupLinkedList(Node head, int key) {
  Node current = head;
  while(current != null) {
    if(current.key == key) return current.value;
    current = current.next;
  }
  return null;
}

String lookupHashMap(HashMap<Integer, String> map, int key) {
  return map.get(key);
}

Shows lookup in array by index, linked list by traversal, and hash map by key.

Execution Table

Step	Operation	Data Structure	Pointer/Index	Action	Visual State
1	Lookup in Array	Array	Index=2	Access arr[2]	[10, 20, 30, 40, 50]
2	Return value	Array	Index=2	Return 30	[10, 20, 30, 40, 50]
3	Lookup in Linked List	Linked List	current=head	Check node key=1	1->"A" -> 2->"B" -> 3->"C" -> null
4	Traverse next	Linked List	current=2	Check node key=2	1->"A" -> 2->"B" -> 3->"C" -> null
5	Traverse next	Linked List	current=3	Check node key=3	1->"A" -> 2->"B" -> 3->"C" -> null
6	Return value	Linked List	current=3	Return "C"	1->"A" -> 2->"B" -> 3->"C" -> null
7	Lookup in Hash Map	Hash Map	Hash key=2	Access bucket for key=2	{1:"A", 2:"B", 3:"C"}
8	Return value	Hash Map	Hash key=2	Return "B"	{1:"A", 2:"B", 3:"C"}
9	End Lookup	-	-	-	-

💡 Lookup ends after returning value or null if not found.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 4	After Step 5	After Step 7	Final
index	-	2	-	-	-	-	2
current (Linked List)	head (key=1)	head	node key=1	node key=2	node key=3	-	node key=3
hash key	-	-	-	-	-	2	2
array	[10,20,30,40,50]	[10,20,30,40,50]	-	-	-	-	[10,20,30,40,50]
linked list	1->"A"->2->"B"->3->"C"->null	same	same	same	same	-	same
hash map	{1:"A",2:"B",3:"C"}	same	same	same	same	same	same

Key Moments - 3 Insights

Why does array lookup use direct index but linked list needs traversal?

Array elements are stored in continuous memory, so accessing by index is direct (see steps 1-2). Linked list nodes are scattered, so we must check each node until key matches (see steps 3-6).

How does hash map find the value faster than linked list?

Hash map uses a hash function to jump directly to the bucket for the key (step 7), avoiding traversal of all elements unlike linked list (steps 3-6).

What happens if the key is not found in linked list or hash map?

Linked list traversal ends at null and returns null (not shown here). Hash map returns null if key is missing (not shown). Both indicate 'not found' after full search or bucket check.

Visual Quiz - 3 Questions

Look at the execution table, what value does the array return at step 2?

A 20

B 30

C 40

D 50

💡 Hint

Check the 'Return value' row for Array at step 2 in execution_table.

At which step does the linked list pointer reach the node with key=3?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at 'Traverse next' operations and pointer values in execution_table rows 4 and 5.

If the hash map did not have key=2, what would happen at step 7?

A Return null immediately

B Traverse all buckets like linked list

C Throw an error

D Return value from index 2

💡 Hint

Hash map lookup returns null if key not found, no traversal needed (see key moments explanation).

Concept Snapshot

Lookup in Array: direct access by index (fast O(1))
Lookup in Linked List: traverse nodes until key found (slow O(n))
Lookup in Hash Map: use hash function to find bucket, then direct access (average O(1))
Arrays require continuous memory; linked lists use nodes with pointers
Hash maps combine array and linked list concepts for fast lookup

Full Transcript

This visualization compares lookup operations in three data structures: array, linked list, and hash map. Array lookup uses a direct index to access the value quickly. Linked list lookup requires checking each node one by one until the key is found or the list ends. Hash map lookup uses a hash function to jump directly to the bucket containing the key, then returns the value. The execution table shows step-by-step how pointers or indices move and how values are returned. Key moments clarify why arrays are fast for lookup, linked lists are slower due to traversal, and hash maps combine speed with flexibility. The quiz tests understanding of these steps and outcomes.

Practice

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

easy

A. Hash Map

B. Array

C. Linked List

D. Stack

Solution

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

   Hash Map uses hashing to find keys quickly, usually in constant time O(1). Arrays require searching by index or linear search for values, O(1) for index but O(n) for value lookup. Linked Lists require linear search O(n).

2. Step 2: Compare average lookup times

   Hash Map average lookup is O(1), Array lookup by index is O(1) but by value is O(n), Linked List lookup is O(n).

3. Final Answer:

   Hash Map -> Option A

4. Quick Check:

   Fastest lookup = Hash Map [OK]

Hint: Hash Map uses keys for O(1) lookup, arrays and lists do not [OK]

Common Mistakes:

• Confusing array index lookup with value lookup
• Assuming linked list lookup is fast
• Thinking stack is for key-value lookup

2. Which of the following is the correct way to declare a HashMap in Java for storing Integer keys and String values?

easy

A. HashMap map = new HashMap();

B. HashMap map = new HashMap<>();

C. HashMap map = new HashMap();

D. HashMap map = new HashMap<>();

Solution

1. Step 1: Check generic types in HashMap declaration

   Java uses wrapper classes like Integer, not primitive int, for generics. So HashMap is invalid.

2. Step 2: Check constructor syntax

   Using diamond operator <> is correct for type inference. HashMap map = new HashMap<>(); is valid and preferred.

3. Final Answer:

   HashMap map = new HashMap<>(); -> Option D

4. Quick Check:

   Correct generic syntax = HashMap map = new HashMap<>(); [OK]

Hint: Use wrapper classes and diamond operator for HashMap declaration [OK]

Common Mistakes:

• Using primitive types like int in generics
• Omitting diamond operator causing raw type warning
• Swapping key and value types in constructor

3. What will be the output of the following Java code snippet?

import java.util.*;
public class Test {
  public static void main(String[] args) {
    List<Integer> list = Arrays.asList(10, 20, 30);
    Map map = new HashMap<>();
    for (int i = 0; i < list.size(); i++) {
      map.put(list.get(i), "Value" + i);
    }
    System.out.println(map.get(20));
  }
}

medium

A. Value0

B. 20

C. Value1

D. null

Solution

1. Step 1: Understand the loop and map population

   The loop runs i from 0 to 2. For each i, map puts key list.get(i) and value "Value" + i. So keys 10, 20, 30 map to "Value0", "Value1", "Value2" respectively.

2. Step 2: Check the output of map.get(20)

   Key 20 maps to "Value1" so printing map.get(20) outputs "Value1".

3. Final Answer:

   Value1 -> Option C

4. Quick Check:

   map.get(20) = Value1 [OK]

Hint: Map keys match list values; index i forms value string [OK]

Common Mistakes:

• Confusing key with value in map.get()
• Assuming map stores values in insertion order
• Expecting numeric output instead of string

4. Identify the error in the following Java code snippet that tries to find if a value exists in a LinkedList:

LinkedList<String> list = new LinkedList<>();
list.add("apple");
list.add("banana");
if (list.contains("orange")) {
  System.out.println("Found orange");
} else {
  System.out.println("Orange not found");
}

medium

A. No error; code works correctly

B. LinkedList does not have contains() method

C. Must use list.search("orange") instead of contains()

D. Contains method only works for integers

Solution

1. Step 1: Check LinkedList methods

   Java's LinkedList class inherits from Collection and has a contains() method to check if an element exists.

2. Step 2: Verify code logic

   The code adds "apple" and "banana" to list, then checks if "orange" is contained. Since "orange" is not in list, it prints "Orange not found". This is correct behavior.

3. Final Answer:

   No error; code works correctly -> Option A

4. Quick Check:

   LinkedList.contains() works as expected [OK]

Hint: LinkedList inherits contains() from Collection interface [OK]

Common Mistakes:

• Thinking contains() is not available for LinkedList
• Using non-existent search() method
• Assuming contains() only works for integers

5. You need to store a large dataset of user IDs (integers) and their names (strings) for fast lookup by user ID. Which data structure is best and why? Choose the best option considering lookup speed, memory, and insertion time.

hard

A. Array, because it provides O(1) lookup by index

B. Hash Map, because it provides average O(1) lookup by key

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

D. Binary Search Tree, because it keeps data sorted

Solution

1. Step 1: Analyze lookup requirements

   We need fast lookup by user ID (key). Array lookup by index is O(1), but user IDs are not guaranteed to be continuous indices.

2. Step 2: Compare data structures for key-based lookup

   Linked List lookup is O(n), too slow. Binary Search Tree lookup is O(log n), slower than Hash Map average O(1). Hash Map stores key-value pairs with fast average lookup.

3. Step 3: Consider insertion and memory

   Hash Map has good insertion time and reasonable memory overhead. Array wastes memory if IDs are sparse. BST keeps data sorted but slower lookup.

4. Final Answer:

   Hash Map, because it provides average O(1) lookup by key -> Option B

5. Quick Check:

   Best for fast key lookup = Hash Map [OK]

Hint: Use Hash Map for fast key-based lookup, not arrays or lists [OK]

Common Mistakes:

• Choosing array assuming user IDs are continuous
• Ignoring lookup time differences
• Preferring BST for speed over Hash Map