What is the difference between array and linked list

• Array – stores elements in one contiguous block of memory, giving O(1) random access by index but O(n) insertion or deletion because elements must shift.
• Linked list – stores elements as scattered nodes connected by references, giving O(n) access because you must traverse, but O(1) insertion or deletion at a known position.
• Cache locality – arrays benefit from contiguous memory loading; linked lists suffer cache misses.
• Resizing – arrays must be copied to a larger block when full; linked lists grow one node at a time.
• Java implementations – ArrayList is backed by an array; LinkedList is a doubly linked list.

What is an array?

An array stores elements in one contiguous block of memory. Each element is the same size, so accessing the element at index i requires computing baseAddress + i * elementSize, which is a single arithmetic step. This makes random access O(1).

package com.bank.model;

import java.math.BigDecimal;

public class ArrayAccessDemo {
    public static void main(String[] args) {
        BigDecimal[] balances = {
            new BigDecimal("50000.00"),
            new BigDecimal("120000.00"),
            new BigDecimal("35000.00")
        };
        // O(1) access by index
        BigDecimal third = balances[2];
        System.out.println("Balance at index 2: Rs." + third);
    }
}

Balance at index 2: Rs.35000.00

What is a linked list?

A linked list stores elements as separate nodes scattered across memory. Each node holds the data and a reference to the next node. There is no index arithmetic, so reaching the element at position i requires traversing i nodes from the head, making access O(n).

package com.bank.model;

import java.math.BigDecimal;

public class TransactionNode {
    BigDecimal amount;
    TransactionNode next;

    public TransactionNode(BigDecimal amount) {
        this.amount = amount;
    }

    public static void main(String[] args) {
        TransactionNode head = new TransactionNode(new BigDecimal("5000.00"));
        head.next = new TransactionNode(new BigDecimal("12000.00"));
        head.next.next = new TransactionNode(new BigDecimal("8700.00"));

        // O(n) access: must traverse to reach the third node
        TransactionNode current = head;
        for (int i = 0; i < 2; i++) {
            current = current.next;
        }
        System.out.println("Third transaction: Rs." + current.amount);
    }
}

Third transaction: Rs.8700.00

How do insertion and deletion differ?

Inserting into the middle of an array requires shifting every element after the insertion point one position to the right, which is O(n). Inserting at the head of a linked list is O(1) because you only re-point one reference.

// Array: inserting at position 1 requires shifting
// [A, B, C] → insert X at 1 → [A, X, B, C]  (B and C shifted right)

// Linked list: inserting at head requires only re-pointing
// head → B → C → insert A at head → A → B → C  (O(1))

How do they compare side by side?

| Aspect | Array | Linked List |
|---|---|---|
| Memory layout | Contiguous block | Scattered nodes |
| Random access | O(1) | O(n) |
| Insert at head | O(n) (shift all) | O(1) |
| Insert at middle | O(n) (shift half) | O(1) if you hold the node |
| Delete at head | O(n) (shift all) | O(1) |
| Cache locality | Excellent | Poor |
| Memory overhead | None per element | One reference per node |
| Resizing | Copy to larger array | Not needed |

Why does cache locality matter?

Because an array is contiguous, when the CPU loads one element it pulls neighbouring elements into the cache line too. Iterating an array hits the cache almost every time. A linked list scatters nodes across the heap, so each node access is likely a cache miss, making iteration much slower in practice even when the big-O is the same.

When should you use which in banking?

Use an array-backed structure when you need fast random access and iteration, such as reading a specific transaction on Rajesh's statement by page number. Use a linked list when you need fast insertion and removal at the ends, such as a queue of newly arriving transactions that Priya processes in order.

What about ArrayList vs LinkedList in Java?

In Java, ArrayList is backed by a resizable array and LinkedList is a doubly linked list. For most workloads ArrayList wins in practice due to cache locality. LinkedList is used mainly when you need frequent addFirst, removeFirst, addLast, and removeLast operations. Pankaj, as the architect at National Bank of India, recommends ArrayList as the default and switches to LinkedList only when profiling shows it helps.

What should a senior engineer know?

A senior engineer knows that the theoretical O(1) insert advantage of linked lists is often negated by cache misses in practice. Modern CPUs are so fast at sequential memory access that shifting elements in an array can be faster than traversing scattered nodes. The senior also knows about ArrayDeque, which provides O(1) amortised insertion at both ends using a circular array buffer, combining the best of both worlds for deque operations without the cache penalty of a linked list.