← Back to Home

LinkedList

LinkedList is a doubly linked list implementation of the List and Deque interfaces in the Java Collections Framework. It is optimized for frequent insertions and deletions, making it suitable for dynamic data manipulation scenarios. This is a high-frequency interview topic, especially when compared with ArrayList.

What Is LinkedList?

  • Doubly linked list implementation
  • Maintains insertion order
  • Allows duplicate elements
  • Allows multiple null values
  • Implements List and Deque
  • Part of java.util package
LinkedList<String> list = new LinkedList<>();

Position in Collection Hierarchy

Iterable
   └── Collection
        └── List
             └── LinkedList
        └── Deque
             └── LinkedList

Key Characteristics of LinkedList

  • Elements stored as nodes (data + prev + next)
  • No shifting of elements
  • Slower random access
  • Faster insertion/deletion

How LinkedList Works Internally (Interview Favorite)

Each node contains:

  • Data
  • Reference to previous node
  • Reference to next node
prev ← [data] → next
  • ✔ Efficient insertion and removal
  • ✔ Extra memory overhead for pointers

Creating a LinkedList

LinkedList<Integer> list = new LinkedList<>();

Commonly Used LinkedList Methods

Adding Elements

list.add(10);
list.addFirst(5);
list.addLast(20);

Removing Elements

list.remove();        // first element
list.removeFirst();
list.removeLast();

Accessing Elements

list.get(0);
list.getFirst();
list.getLast();

Queue / Deque Operations

list.offer(30);
list.poll();
list.peek();

✔ Supports FIFO and LIFO operations

Iterating a LinkedList

for (Integer i : list) {
    System.out.println(i);
}

Performance Complexity (Important)

Operation Time Complexity
get(index) O(n)
add/remove (beginning) O(1)
add/remove (middle) O(n)
search O(n)

LinkedList vs ArrayList (Key Interview Comparison)

Aspect LinkedList ArrayList
Internal structure Doubly linked list Dynamic array
Random access Slow Fast
Insertion/deletion Fast Slow (middle)
Memory usage Higher Lower
Use case Frequent modifications Frequent reads

Thread Safety

  • Not synchronized
  • Not thread-safe

Thread-safe alternatives: Collections.synchronizedList(), ConcurrentLinkedDeque

When to Use LinkedList

  • Frequent insertions/deletions
  • Implementing stack, queue, deque
  • Data size changes frequently
  • Sequential access patterns

When NOT to Use LinkedList

  • Heavy random access
  • Memory-constrained environments
  • Large datasets with frequent reads

Common Beginner Mistakes

  • Using LinkedList for random access
  • Assuming faster in all cases
  • Ignoring memory overhead
  • Using it like an ArrayList
  • Concurrent modification without care

Interview-Ready Answers

Short Answer

LinkedList is a doubly linked list implementation of the List interface.

Detailed Answer

In Java, LinkedList implements both List and Deque interfaces. It stores elements as nodes with previous and next references, allowing fast insertion and deletion but slower random access compared to ArrayList.

Key Takeaway

Use LinkedList when modification speed matters more than access speed. Choose wisely based on access pattern and performance needs.