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

Mental Model

Arrays store items in order in one block of memory, while linked lists store items scattered in memory connected by pointers.

Analogy: An array is like a row of mailboxes all in a line, easy to find by number. A linked list is like a treasure hunt where each clue points to the next location.

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

Dry Run Walkthrough

Input: Compare adding a new item at the start and accessing the third item in both array and linked list of 5 elements

Goal: Show when arrays or linked lists are better for adding and accessing elements

Step 1: Access third item in array directly by index

[1][2][3][4][5]

Why: Arrays allow direct access by index quickly

Step 2: Access third item in linked list by following pointers from head

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

Why: Linked lists require moving step-by-step to reach an item

Step 3: Add new item '0' at start of array by shifting all items right

[0][1][2][3][4][5]

Why: Arrays need to move all items to insert at start

Step 4: Add new item '0' at start of linked list by creating new node pointing to head

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null

Why: Linked lists can add at start quickly by changing pointers

Result:

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

Annotated Code

DSA Java

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

public class LinkedListVsArray {
    // Access third element in array
    static int accessArray(int[] arr) {
        return arr[2]; // direct access by index
    }

    // Access third element in linked list
    static int accessLinkedList(Node head) {
        Node curr = head;
        for (int i = 0; i < 2; i++) {
            if (curr == null) throw new IllegalArgumentException("List too short");
            curr = curr.next; // move to next node
        }
        if (curr == null) throw new IllegalArgumentException("List too short");
        return curr.val;
    }

    // Insert at start of array by shifting
    static int[] insertAtStartArray(int[] arr, int val) {
        int[] newArr = new int[arr.length + 1];
        newArr[0] = val; // new first element
        for (int i = 0; i < arr.length; i++) {
            newArr[i + 1] = arr[i]; // shift elements right
        }
        return newArr;
    }

    // Insert at start of linked list by pointer change
    static Node insertAtStartLinkedList(Node head, int val) {
        Node newNode = new Node(val);
        newNode.next = head; // new node points to old head
        return newNode; // new node is new head
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);

        System.out.println("Access 3rd in array: " + accessArray(arr));
        System.out.println("Access 3rd in linked list: " + accessLinkedList(head));

        int[] newArr = insertAtStartArray(arr, 0);
        System.out.print("Array after insert at start: ");
        for (int v : newArr) System.out.print("[" + v + "]");
        System.out.println();

        Node newHead = insertAtStartLinkedList(head, 0);
        System.out.print("Linked list after insert at start: ");
        Node curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " -> ");
            curr = curr.next;
        }
        System.out.println("null");
    }
}

return arr[2]; // direct access by index

directly access third element in array by index

curr = curr.next; // move to next node

advance pointer to reach third node in linked list

newArr[0] = val; // new first element

place new value at start of new array

newArr[i + 1] = arr[i]; // shift elements right

shift existing elements right to make space

newNode.next = head; // new node points to old head

link new node to current head for quick insert

return newNode; // new node is new head

return new node as new head of linked list

Output

Access 3rd in array: 3

Access 3rd in linked list: 3

Array after insert at start: [0][1][2][3][4][5]

Linked list after insert at start: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null

Complexity Analysis

Time: O(1) for array access because index is direct; O(n) for linked list access because we must follow pointers step-by-step; O(n) for inserting at start in array due to shifting; O(1) for inserting at start in linked list by pointer change

Space: O(n) for both because they store n elements; array may need extra space when resizing for insert; linked list uses extra space per node for pointers

vs Alternative: Arrays are faster for random access but slower for insertions at start; linked lists are slower for access but faster for insertions and deletions at start

Edge Cases

empty array or linked list

accessing third element fails or returns error; inserting at start works by creating new structure

DSA Java

return arr[2]; // direct access by index

single element linked list

accessing third element moves past null causing error; inserting at start adds new head safely

DSA Java

curr = curr.next; // move to next node

When to Use This Pattern

When a problem needs fast random access, think arrays; when frequent insertions or deletions at start or middle are needed, think linked lists because they handle pointer changes efficiently.

Common Mistakes

Mistake: Trying to access linked list elements by index directly like an array
Fix: Traverse the linked list node by node until reaching the desired position

Mistake: Inserting at start of array without shifting elements
Fix: Shift all elements right to make space before inserting

Summary

Compares when to use arrays or linked lists based on access and insertion needs

Use arrays for fast direct access and linked lists for fast insertions/deletions

Arrays store items contiguously for quick access; linked lists use pointers for flexible insertion

Practice

1. Which data structure is better when you need fast random access to elements by index?

easy

A. Linked List

B. Array

C. Stack

D. Queue

Solution

1. Step 1: Understand random access requirement

   Random access means accessing any element directly by its position quickly.

2. Step 2: Compare Array and Linked List access times

   Arrays allow direct access by index in constant time, while linked lists require traversal.

3. Final Answer:

   Array -> Option B

4. Quick Check:

   Random access = Array [OK]

Hint: Arrays provide fast index access, linked lists do not [OK]

Common Mistakes:

• Thinking linked lists allow fast random access
• Confusing stack or queue with arrays
• Ignoring access time differences

2. Which of the following is the correct way to declare an array of integers in Java?

easy

A. int[] arr = new int[5];

B. int arr = new int[5];

C. int arr[] = new int();

D. array int arr = new int[5];

Solution

1. Step 1: Recall Java array declaration syntax

   In Java, arrays are declared with type[], variable name, and size with new keyword.

2. Step 2: Check each option for syntax correctness

   int[] arr = new int[5]; matches correct syntax: int[] arr = new int[5]; others have errors.

3. Final Answer:

   int[] arr = new int[5]; -> Option A

4. Quick Check:

   Java array syntax = int[] arr = new int[5]; [OK]

Hint: Remember Java arrays use type[] name = new type[size]; [OK]

Common Mistakes:

• Missing brackets [] after type
• Using parentheses instead of brackets
• Wrong keyword 'array' instead of type

3. Consider this Java code using a linked list:

LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.add(20);
list.add(30);
System.out.println(list.get(1));

What will be the output?

medium

A. 10

B. 30

C. IndexOutOfBoundsException

D. 20

Solution

1. Step 1: Understand list contents after adds

   Elements added in order: 10 at index 0, 20 at index 1, 30 at index 2.

2. Step 2: Identify element at index 1

   list.get(1) returns the element at index 1, which is 20.

3. Final Answer:

   20 -> Option D

4. Quick Check:

   list.get(1) = 20 [OK]

Hint: Indexing starts at 0; second element is index 1 [OK]

Common Mistakes:

• Assuming index starts at 1
• Confusing add order with index
• Expecting runtime error incorrectly

4. The following Java code tries to remove an element from an array but causes an error:

int[] arr = {1, 2, 3, 4};
arr.remove(2);

What is the main issue here?

medium

A. Arrays do not have a remove method

B. Index 2 is out of bounds

C. Array elements cannot be integers

D. Syntax error in array declaration

Solution

1. Step 1: Check if arrays support remove method

   Java arrays have fixed size and do not support remove method.

2. Step 2: Identify correct way to remove elements

   To remove elements, use ArrayList or create a new array without the element.

3. Final Answer:

   Arrays do not have a remove method -> Option A

4. Quick Check:

   Arrays fixed size = no remove method [OK]

Hint: Arrays fixed size, no remove method; use ArrayList [OK]

Common Mistakes:

• Thinking arrays support remove like lists
• Assuming index 2 is invalid
• Confusing syntax errors with method errors

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. Linked List, because it uses contiguous memory

C. Linked List, because it allows fast insertions and deletions without shifting elements

D. Array, because it supports random access

Solution

1. Step 1: Analyze insertion and deletion costs

   Arrays require shifting elements for insert/delete in middle, which is slow for large data.

2. Step 2: Understand linked list advantages

   Linked lists use nodes with pointers, so insert/delete in middle is fast without shifting.

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: Linked lists excel at middle insert/delete without shifting [OK]

Common Mistakes:

• Choosing array for frequent middle insert/delete
• Confusing memory layout of linked lists
• Ignoring shifting cost in arrays