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

Hash Map vs Array vs Linked List for Lookup

📖 Scenario: Imagine you run a small library. You want to find books quickly by their ID numbers. You have three ways to store book IDs and their titles: an array, a linked list, and a hash map. Each way has different speed for finding a book.

🎯 Goal: You will create three data structures: an array, a linked list, and a hash map, each holding the same books. Then, you will write code to look up a book title by its ID in each structure and print the results. This will help you see which way is fastest and easiest for lookup.

📋 What You'll Learn

Create an array of book IDs and titles

Create a linked list of book IDs and titles

Create a hash map of book IDs and titles

Write lookup code to find a book title by ID in each data structure

Print the found book titles for a given ID

💡 Why This Matters

🌍 Real World

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

💼 Career

Software developers must understand data structures to write fast and efficient code for searching and storing data.

1

Create an array of book IDs and titles

Create a 2D array called booksArray with these exact entries: {101, "Java Basics"}, {102, "Data Structures"}, {103, "Algorithms"}.

DSA Java

// Create the 2D array booksArray with book IDs and titles
// Your code here

Hint

Use a 2D String array where each inner array has two elements: the book ID and the title.

2

Create a linked list of book IDs and titles

Create a LinkedList of String[] called booksList and add these exact entries: {"101", "Java Basics"}, {"102", "Data Structures"}, {"103", "Algorithms"}.

DSA Java

import java.util.LinkedList;

String[][] booksArray = {
    {"101", "Java Basics"},
    {"102", "Data Structures"},
    {"103", "Algorithms"}
};

// Create LinkedList booksList and add the same book entries
// Your code here

Hint

Use LinkedList<String[]> and add each book as a String array with ID and title.

3

Create a hash map of book IDs and titles

Create a HashMap called booksMap with String keys and String values. Add these exact entries: key "101" with value "Java Basics", key "102" with value "Data Structures", key "103" with value "Algorithms".

DSA Java

import java.util.LinkedList;
import java.util.HashMap;

String[][] booksArray = {
    {"101", "Java Basics"},
    {"102", "Data Structures"},
    {"103", "Algorithms"}
};

LinkedList booksList = new LinkedList();
booksList.add(new String[]{"101", "Java Basics"});
booksList.add(new String[]{"102", "Data Structures"});
booksList.add(new String[]{"103", "Algorithms"});

// Create HashMap booksMap and add the same book entries
// Your code here

Hint

Use HashMap<String, String> and add each book ID as key and title as value.

4

Lookup and print book titles by ID in all data structures

Write code to find and print the book title for ID "102" from booksArray, booksList, and booksMap. Print the titles in this exact order, each on its own line: first from booksArray, then from booksList, then from booksMap.

DSA Java

import java.util.LinkedList;
import java.util.HashMap;

String[][] booksArray = {
    {"101", "Java Basics"},
    {"102", "Data Structures"},
    {"103", "Algorithms"}
};

LinkedList booksList = new LinkedList();
booksList.add(new String[]{"101", "Java Basics"});
booksList.add(new String[]{"102", "Data Structures"});
booksList.add(new String[]{"103", "Algorithms"});

HashMap booksMap = new HashMap();
booksMap.put("101", "Java Basics");
booksMap.put("102", "Data Structures");
booksMap.put("103", "Algorithms");

// Lookup and print the title for ID "102" from booksArray, booksList, and booksMap
// Your code here

Hint

Use a for loop to find the book in the array and linked list by comparing IDs. Use get method for the hash map. Print the found titles in order.

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