A Swing GUI That Shows Exactly How LinkedList Rewires Nodes on add() and remove()

[Java] Showing the Internal Changes of LinkedList When Adding and Removing Elements

Background

I previously wrote [Java] Showing the internal changes of ArrayList when adding elements, which displayed ArrayList's internal changes when adding elements. Later I thought LinkedList's internal changes during add and remove operations could also be presented in GUI form. I used trae to complete this Java code.

Notes

The full code uses the record syntax, so compilation and running require JDK 16+ (including 16).

Main text

How to run

For the flow of the text, the full code section provides the complete code. Save the complete code as LinkedListBehaviorDemo.java. Use the following command to compile it:

javac LinkedListBehaviorDemo.java

After compilation, the following class files are produced:

LinkedListBehaviorDemo.class
LinkedListBehaviorDemo$ChainView.class
LinkedListBehaviorDemo$NodeView.class

Run the main method in LinkedListBehaviorDemo with the following command. (Reflection access to private fields in java.util is restricted by the JDK 9+ module system, so the --add-opens option is required):

java --add-opens=java.base/java.util=ALL-UNNAMED LinkedListBehaviorDemo

Run result examples

Initial state

Constructor

Clicking the new LinkedList<String>() button calls LinkedList's default constructor and produces an instance:

Adding elements

Click one of the following buttons to add an element to the LinkedList:

add("A") button (the string on the button keeps changing; initially "A")
addFirst("A") button (the string on the button keeps changing; initially "A")
add(i, "A") button (the string on the button keeps changing; initially "A")

After clicking, the corresponding LinkedList method is called:

Example after adding elements:

Removing elements

Click one of the following buttons to remove an element from the LinkedList:

removeFirst() button
removeLast() button
remove(i) button

After clicking, the corresponding LinkedList method is called:

`Show logical chain` button

This button shows each node's logical order, including both next references and prev references.

`Show heap scatter` button

This button shows the distribution of nodes (it does not show the real addresses of nodes). The next references of nodes can be displayed:

The prev references of nodes can also be displayed:

Reset button

This button restarts the demo.

Current state

This control shows the size, first, and last fields of the LinkedList:

The size/first/last values come from LinkedList:

Observation points

Background: LinkedList's internal structure

LinkedList internally maintains only four fields:

transient int size
transient Node<E> first
transient Node<E> last
private static final long serialVersionUID (serialVersionUID is a static field)

The following code verifies this (save it as LinkedListFieldsCliDemo.java):

import java.lang.reflect.Field;
import java.lang.reflect.Modifier;
import java.util.LinkedList;

/**
 * Lists the fields declared by java.util.LinkedList via reflection.
 * <p>
 * getDeclaredFields() only reads metadata, not field values, so no
 * setAccessible and no --add-opens are needed:
 * <pre>
 * javac LinkedListFieldsCliDemo.java
 * java  LinkedListFieldsCliDemo
 * </pre>
 */
public class LinkedListFieldsCliDemo {

    public static void main(String[] args) {
        System.out.println("== fields declared by java.util.LinkedList ==");
        for (Field f : LinkedList.class.getDeclaredFields()) {
            System.out.printf("    %-24s %-28s %s%n",
                    Modifier.toString(f.getModifiers()),
                    f.getType().getName(),
                    f.getName());
        }
    }

}

Each node is an independent object:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Nodes are not stored in a contiguous array: each node is an independent object on the heap, and the order of the list exists only in the next/prev references. The GUI provides two switchable views:

Logical chain view (Show logical chain): one box per node, arranged in list order, with forward next arrows and backward prev arrows, ending in null at both ends.
Heap scatter view (Show heap scatter): each node is placed at a pseudo-random position determined by its identity hash, making it directly visible that nodes adjacent in the list are not adjacent in memory.

Facts observable through the demo

add(E)/addLast(E) connects a new node after last.
addFirst(E) connects a new node before first.
add(i, E) first calls node(i) to walk along the links to the target position, then re-links two neighboring nodes (when index == size, it skips the search and links directly at the tail).
removeFirst()/removeLast() remove a node at one end of the list.
remove(i) also finds the corresponding node via node(i), then removes it.
node(i) uses a bidirectional search strategy: when i < size/2, it walks forward from first; otherwise it walks backward from last. The cost is O(n), which is exactly why ArrayList has faster random access.

Full code

// The complete LinkedListBehaviorDemo.java source from the original article
// (Swing UI, ChainView, reflection access, and main method) is included here.

LinkedList class diagram

The following class diagram is based on JDK 21 and ignores generic information:

LinkedList reuses skeleton implementations through AbstractSequentialList -> AbstractList -> AbstractCollection, and implements the List interface and the Deque interface, so it can be used both as a list and as a double-ended queue.

How to draw the class diagram for `java.util.LinkedList`?

I used the code from [Java] How to automatically generate a simple PlantUML class diagram. The key commands are:

javac ClassDiagramGenerator.java
java ClassDiagramGenerator 'java.util.LinkedList'

The output of the second command is (from JDK 21):

@startuml

interface java.util.List
interface java.lang.Cloneable
interface java.lang.Iterable
interface java.util.Queue
interface java.util.SequencedCollection
interface java.io.Serializable
interface java.util.Deque
interface java.util.Collection
abstract java.util.AbstractCollection
abstract java.util.AbstractSequentialList
abstract java.util.AbstractList
class java.util.LinkedList
java.lang.Iterable <|-- java.util.Collection
java.util.Collection <|.. java.util.AbstractCollection
java.util.Collection <|-- java.util.SequencedCollection
java.util.SequencedCollection <|-- java.util.List
java.util.AbstractCollection <|-- java.util.AbstractList
java.util.List <|.. java.util.AbstractList
java.util.AbstractList <|-- java.util.AbstractSequentialList
java.util.Collection <|-- java.util.Queue
java.util.Queue <|-- java.util.Deque
java.util.SequencedCollection <|-- java.util.Deque
java.util.AbstractSequentialList <|-- java.util.LinkedList
java.util.List <|.. java.util.LinkedList
java.util.Deque <|.. java.util.LinkedList
java.lang.Cloneable <|.. java.util.LinkedList
java.io.Serializable <|.. java.util.LinkedList

@enduml

With the PlantUML plugin in IntelliJ IDEA (Community Edition), the puml above can be converted into a class diagram.

References

LinkedList.java in OpenJDK
[Java] Showing the internal changes of ArrayList when adding elements
[Java] How to automatically generate a simple PlantUML class diagram (I used this article as a reference when drawing the java.util.LinkedList class diagram)