Common Java Data Structures and Their Core Operations

Recently I organized knowledge about data structures and decided to illustrate the data flow processes with animations, focusing on common Java collections based on JDK 8.

1. LinkedList – Implements a classic doubly‑linked list suitable for random insertions and deletions; sequential access is slower than ArrayList . Key methods:

add(E) / addLast(E)

add(index, E) – Optimizes traversal by checking whether the index is closer to the head or tail.

get(index) – Also chooses traversal direction; iteration via Iterator is recommended.

remove(E)

Optimization code for add(index, E) :

if (index < (size >> 1)) {
    Node
x = first;
    for (int i = 0; i < index; i++)
        x = x.next;
    return x;
} else {
    Node
x = last;
    for (int i = size - 1; i > index; i--)
        x = x.prev;
    return x;
}

2. ArrayList – Backed by a resizable array; fast random access, but insertions/deletions in the middle require element shifting. Important aspects:

add(index, E) – Shifts subsequent elements.

Capacity defaults to 10 and grows by a factor of 1.5 on expansion.

remove(E) – Traverses the array to find the element; slower than LinkedList for deletions.

3. Stack – Extends Vector (array‑based) and follows LIFO order. Default capacity is 10 and expands automatically. Core operations:

push(E)

pop()

4. Postfix Expression Evaluation (using Stack) – Demonstrates converting an infix expression to postfix and then evaluating it. The algorithm outlines handling numbers, operators, parentheses, and operator precedence.

5. Queue – FIFO structure; differs from Stack as removal occurs at the head while insertion occurs at the tail. Example implementation: ArrayBlockingQueue for producer‑consumer scenarios.

Key methods and code snippets:

final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
    while (count == items.length)
        notFull.await();
    enqueue(e);
} finally {
    lock.unlock();
}

Method take() updates takeIndex in a circular fashion without shifting array elements.

private E dequeue() {
    final Object[] items = this.items;
    E x = (E) items[takeIndex];
    items[takeIndex] = null;
    if (++takeIndex == items.length)
        takeIndex = 0;
    count--;
    notFull.signal();
    return x;
}

6. HashMap – The most widely used hash table; combines an array with singly linked lists (and red‑black trees for buckets > 8 in JDK 8). Important operations:

put(K, V)

Resize (dynamic expansion) doubles the table size and rehashes entries.

Resize algorithm distinguishes entries whose new hash bit is 0 (stay in the same bucket) from those with bit 1 (move to bucket index + oldCap). Sample code shows splitting the old bucket into lo and hi chains and linking them into the new table.

do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null) loHead = e; else loTail.next = e;
        loTail = e;
    } else {
        if (hiTail == null) hiHead = e; else hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);
if (loTail != null) { loTail.next = null; newTab[j] = loHead; }
if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }

7. LinkedHashMap – Extends HashMap by maintaining a doubly linked list to preserve insertion order or access order (LRU). Operations:

put(K, V)

get(K) – When accessOrder is true, moves the accessed entry to the tail.

removeEldestEntry – Allows automatic removal of the oldest entry.

Overall, the article provides a visual and code‑driven walkthrough of these core Java collections, highlighting their internal structures, typical use‑cases, and performance trade‑offs.