Internal Working of LinkedList in Java

Introduction

A LinkedList in Java is a part of the java.util package and is used to store elements in a doubly linked list structure. Unlike ArrayList, which uses a dynamic array, LinkedList consists of nodes that store data and references to the next and previous nodes.

---

1. Data Structure Used

LinkedList is implemented using a doubly linked list where each node contains:

• Data (Element Value)
• Pointer to Next Node
• Pointer to Previous Node (in a doubly linked list)

Implementation in Java:

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

When a LinkedList is created, it maintains references to:

• First Node (head)
• Last Node (tail)

---

2. How Elements are Stored and Accessed

Adding an Element

When add() is called:

1. A new node is created.
2. If the list is empty, the new node becomes both head and tail.
3. Otherwise, the new node is added at the end, and tail is updated.

Example:

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

Retrieving an Element

Elements are accessed using the get(index) method, which traverses from head (O(n) time complexity):

System.out.println(list.get(1)); // Output: Banana

Unlike ArrayList, LinkedList does not support direct indexing (O(1)).

Removing an Element

When remove(index) is called:

1. The node at the given index is located (requires traversal).
2. The previous node’s next pointer is updated to skip the removed node.
3. The next node’s prev pointer is updated to maintain the chain.

Example:

list.remove(1); // Removes "Banana"
System.out.println(list); // Output: [Apple, Cherry]

---

3. Performance Analysis

Operation	Time Complexity
Add at End	O(1)
Add at Index	O(n) (Traversal required)
Get Element	O(n) (Sequential Traversal)
Remove Element	O(n) (Traversal + Re-linking)

Comparison with ArrayList

Feature	LinkedList (O(n) Access)	ArrayList (O(1) Access)
Access by Index	❌ Slow (O(n))	✅ Fast (O(1))
Insert at End	✅ Fast (O(1))	✅ Fast (O(1))
Insert at Beginning	✅ Fast (O(1))	❌ Slow (O(n))
Memory Overhead	❌ High (Extra Node Pointers)	✅ Low

---

4. Key Takeaways

✔ LinkedList is better for frequent insertions/deletions, especially at the beginning or middle.

✔ Uses a doubly linked list, requiring extra memory for node pointers.

✔ Does not support direct access (O(n)), unlike ArrayList (O(1)).

✔ Use LinkedList when insertions and deletions are frequent, and ArrayList when random access is needed.

Understanding the internal working of LinkedList helps in making better decisions when choosing data structures for Java applications.