LinkedList in Java – Internal Working, Examples & FAQs

In Java, LinkedList is one of the most important data structures provided by the Collection Framework. It belongs to the java.util package and is widely used to store and manipulate dynamic data where elements are frequently inserted and deleted.

LinkedList allows dynamic memory allocation, efficient insertions/deletions, and bidirectional traversal.

This tutorial will walk you through every concept of LinkedList with simple explanations and code examples. So, let’s start from the basics and build up to advanced usage.

What is LinkedList?

LinkedList is a doubly-linked list implementation of the List and Deque interfaces. It stores elements in nodes, and each node contains:

• The data
• A reference to the next node
• A reference to the previous node

Unlike ArrayList, it doesn’t use arrays internally. Instead, it uses node-based memory structure, making insertions and deletions efficient.

Internal Node Structure of LinkedList

Each node in a LinkedList contains:

• The actual data (value to store)
• A reference to the next node
• A reference to the previous node

This structure allows for efficient insertions and deletions because only the links between nodes need to be updated—there’s no need to shift elements like in an array.

Key Characteristics of LinkedList:

• Elements are stored in nodes
• Each node points to the next and previous node
• Great for frequent insertion and deletion
• Slower for random access compared to ArrayList

Class Declaration and Hierarchy of LinkedList

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, Serializable

Implements:

• List (supports index-based operations)
• Deque (can be used as a queue or stack)
• Cloneable (can be cloned)
• Serializable (can be serialized)

Here’s what a node looks like internally (simplified):

private static class Node<E> {
    E item;           // Data stored in the node
    Node<E> next;     // Reference to next node
    Node<E> prev;     // Reference to previous node

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

Visual Representation

Here’s a visual of a LinkedList with 3 elements:

null ← [A] ⇄ [B] ⇄ [C] → null

• “A” is the head (first node)
• “C” is the tail (last node)
• Each node links to the one before and after it

Syntax – How to Declare a LinkedList

To use a LinkedList in Java, import it from the java.util package:

import java.util.LinkedList;

Then, you can declare and initialize it like this:

LinkedList<String> names = new LinkedList<>();

This creates an empty LinkedList of strings.

Basic Operations Example

LinkedList<String> names = new LinkedList<>();

// Adding elements
names.add("Alice");
names.add("Bob");
names.add("Charlie");

// Accessing elements
System.out.println(names.get(1)); // Output: Bob

// Removing elements
names.removeFirst(); // Removes "Alice"
names.removeLast();  // Removes "Charlie"

// Resulting list
System.out.println(names); // [Bob]

Key Features of LinkedList

LinkedList Internal Working

LinkedList is a doubly-linked list implementation of the List, Deque, and Queue interfaces in Java’s Collections Framework.
It stores elements in nodes, where each node contains:

• the data (element),
• a reference to the next node, and
• a reference to the previous node.

Unlike ArrayList, which uses a contiguous block of memory (array), LinkedList uses a node-based structure, making insertions and deletions faster, especially at the beginning or middle of the list

Internal Node Structure

Each node in a LinkedList contains:

• The actual data (value to store)
• A reference to the next node
• A reference to the previous node

This structure allows for efficient insertions and deletions because only the links between nodes need to be updated—there’s no need to shift elements like in an array.

Here’s what a node looks like internally (simplified):

private static class Node<E> {
    E item;           // Data stored in the node
    Node<E> next;     // Reference to next node
    Node<E> prev;     // Reference to previous node

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

Visual Representation

Here’s a visual of a LinkedList with 3 elements:

null ← [A] ⇄ [B] ⇄ [C] → null

• “A” is the head (first node)
• “C” is the tail (last node)
• Each node links to the one before and after it

🛠️ Syntax – How to Declare a LinkedList

To use a LinkedList in Java, import it from the java.util package:

import java.util.LinkedList;

Then, you can declare and initialize it like this:

LinkedList<String> names = new LinkedList<>();

This creates an empty LinkedList of strings.

Structure of a Doubly Linked List

Visual representation of a doubly linked list:

null ← [Node1] ⇄ [Node2] ⇄ [Node3] → null

Each node holds:

1. The actual data (called item)
2. A reference to the next node
3. A reference to the previous node

Node Class in LinkedList

Internally, Java’s LinkedList maintains a private static class called Node inside the LinkedList class. Here’s a simplified version of it:

private static class Node<E> {
    E item;           // The actual data element
    Node<E> next;     // Pointer to the next node
    Node<E> prev;     // Pointer to the previous node

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

🔄 How Nodes Are Connected

When we add elements to a LinkedList, nodes are created and linked in both directions.

Let’s say you add 3 elements:

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");

Behind the scenes, this happens:

1. A Node is created for “A”
2. Then a Node is created for “B”, and “A” is linked to “B”
3. Then a Node is created for “C”, and “B” is linked to “C”

Each link has both forward and backward references:

null ← [A] ⇄ [B] ⇄ [C] → null

• head points to A
• tail points to C

Some LinkedList Operations Internal Working

Let’s see how key operations behave internally:

1. Adding an Element

Case 1: At the end (default)

list.add("D");

• A new Node is created for “D”
• “C”’s next points to “D”
• “D”’s prev points to “C”
• tail is updated to “D”

2. Adding at a Specific Position

list.add(1, "X");  // Inserts at index 1

• The list is traversed to the index
• New node “X” is inserted between A and B
• Pointers are adjusted:
  • A.next = X
  • X.prev = A
  • X.next = B
  • B.prev = X

3. Removing an Element

list.remove("B");

• The node containing “B” is found
• Its previous and next nodes are linked to each other
  • A.next = C
  • C.prev = A
• Node “B” becomes unreachable and is garbage collected

4. Accessing an Element

list.get(2);

• The list starts traversal from the head if the index is in the first half.
• It starts from the tail if the index is in the second half.
• This gives O(n) time complexity.

This is unlike ArrayList, where access is done in O(1) time due to indexing in an array.

Internal Fields of LinkedList Class

Here’s a simplified version of what the LinkedList class maintains:

public class LinkedList<E> extends AbstractSequentialList<E> {
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
}

• first: points to the head node
• last: points to the tail node
• size: total number of elements in the list

Diagram Summary

null ← [Head: "A"] ⇄ [Node: "B"] ⇄ [Tail: "C"] → null

• A.prev = null, A.next = B
• B.prev = A, B.next = C
• C.prev = B, C.next = null

Garbage Collection & Memory Efficiency

When a node is removed, its reference to previous and next is set to null, and the object becomes eligible for garbage collection.

However, due to the overhead of maintaining two references (next and prev), LinkedList uses more memory per element than ArrayList.

Creating a LinkedList

import java.util.LinkedList;

LinkedList<String> fruits = new LinkedList<>();
fruits.add("Apple");
fruits.add("Banana");
System.out.println(fruits); // [Apple, Banana]

Commonly Used LinkedList Methods (with Java version badges)

Examples of LinkedList Usage

1. Add and Iterate

LinkedList<String> names = new LinkedList<>();
names.add("Alice");
names.add("Bob");

for(String name : names) {
    System.out.println(name);
}

🔍 Explanation:

• new LinkedList<>(): Creates an empty LinkedList of type String.
• add("Alice"): Adds “Alice” to the end of the list.
• add("Bob"): Adds “Bob” after “Alice”.

At this point, the list looks like:

["Alice", "Bob"]

for-each loop: Iterates over each element in the list and prints them:

Output:

Alice
Bob

2. Add at First and Last

names.addFirst("Zara");
names.addLast("Eve");

System.out.println(names); // [Zara, Alice, Bob, Eve]

🔍 Explanation:

• addFirst("Zara"): Inserts “Zara” at the beginning of the list.
• addLast("Eve"): Inserts “Eve” at the end of the list.

Now the list becomes:

["Zara", "Alice", "Bob", "Eve"]

System.out.println(names): Displays the current list.

Output:

[Zara, Alice, Bob, Eve]

3. Remove Elements

names.removeFirst();  // Removes Zara
names.removeLast();   // Removes Eve

🔍 Explanation:

• removeFirst(): Removes the first element in the list (“Zara”).
• removeLast(): Removes the last element in the list (“Eve”).

Now the list becomes:

["Alice", "Bob"]

You’ve successfully removed elements from both ends of the linked list.

4. Using Java 8 Stream

names.stream()
     .filter(n -> n.startsWith("A"))
     .forEach(System.out::println); // Alice

🔍 Explanation:

This is using Java 8 Stream API to process the list in a functional style.

• names.stream(): Converts the LinkedList into a stream of elements.
• filter(n -> n.startsWith("A")): Filters only the names that start with the letter “A”.
• forEach(System.out::println): Prints each filtered element.

In our current list:

["Alice", "Bob"]

Only “Alice” starts with “A”, so output will be:

Alice

Summary Table

Traversing a LinkedList

1. Using for-each loop

for(String fruit : fruits) {
    System.out.println(fruit);
}

2. Using Iterator

Iterator<String> it = fruits.iterator();
while(it.hasNext()) {
    System.out.println(it.next());
}

3. Using ListIterator (Forward and Backward)

ListIterator<String> listIt = fruits.listIterator();

System.out.println("Forward:");
while(listIt.hasNext()) {
    System.out.println(listIt.next());
}

System.out.println("Backward:");
while(listIt.hasPrevious()) {
    System.out.println(listIt.previous());
}

LinkedList vs ArrayList

Fail-Fast Behavior

Like other Java collections, LinkedList is fail-fast. If modified while iterating using a regular iterator, it throws ConcurrentModificationException.

Example:

Iterator<String> it = names.iterator();
while(it.hasNext()) {
    names.add("New"); // Throws ConcurrentModificationException
}

Use ListIterator or CopyOnWriteArrayList for fail-safe behavior if needed.

Linked List Example – Maintaining a History Stack

Let’s simulate a browser history using LinkedList.

import java.util.LinkedList;

public class BrowserHistory {
    public static void main(String[] args) {
        LinkedList<String> history = new LinkedList<>();

        history.add("google.com");
        history.add("openai.com");
        history.add("github.com");

        System.out.println("Current History: " + history);

        // Going back
        String lastVisited = history.removeLast();
        System.out.println("Back to: " + history.getLast());
        System.out.println("You just left: " + lastVisited);
    }
}

Output:

Current History: [google.com, openai.com, github.com]
Back to: openai.com
You just left: github.com

❓ FAQs on LinkedList

Q1. Is LinkedList thread-safe?

No, it’s not synchronized. You can make it thread-safe using:

Collections.synchronizedList(new LinkedList<>());

Q2. When should I use LinkedList over ArrayList?

Use LinkedList when:

• You do frequent insertions/deletions.
• You don’t need random access (index-based).

Q3. Can LinkedList contain null elements?

Yes, it allows any number of null elements.

Q4. What interfaces does LinkedList implement?

• List
• Deque
• Queue
• Cloneable
• Serializable

Q5. Is LinkedList faster than ArrayList?

For insertions and deletions, yes.
For access by index, no—ArrayList is faster.

🎯 Summary

Conclusion

Java’s LinkedList is a versatile and efficient data structure when dealing with lots of insertions and deletions. While it’s slower in random access compared to ArrayList, it offers more flexibility when managing dynamic data.