LinkedList in Java

The LinkedList class in Java is a versatile, node-based linear data structure that is part of the Java Collections Framework.

It implements:

• List (ordered collection)
• Deque (double-ended queue)
• Queue (FIFO operations)
• Cloneable & Serializable

Unlike ArrayList, it is not array-backed, but node-backed, making it ideal for insertion and deletion-heavy use cases.

---

What is LinkedList in Java?

A LinkedList is a doubly-linked data structure where each element is stored in a separate node, containing:

• Data
• Pointer to Previous Node
• Pointer to Next Node

Because the nodes are linked dynamically, size can grow or shrink anytime.

Internal Structure of LinkedList

LinkedList Node Structure

Each element in LinkedList is stored as a Node object:

class Node<E> {
    E item;       // Data
    Node<E> next; // Pointer to next
    Node<E> prev; // Pointer to previous
}

Memory Diagram

NULL ← [ Prev | Data: A | Next ] ↔ [ Prev | Data: B | Next ] ↔ [ Prev | Data: C | Next ] → NULL

• LinkedList maintains pointers to:
  • first node → head
  • last node → tail

This allows O(1) insertions at both ends.

LinkedList in Java Collection Hierarchy

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

Because LinkedList implements Deque, it also supports:

• Queue (FIFO)
• Stack (LIFO)

---

Key Features of LinkedList

Feature	Explanation
Dynamic Size	Grows and shrinks automatically
Fast Insert/Delete	No shifting like ArrayList
Slow Access	Because nodes must be traversed
Implements List, Queue, Deque	Very flexible
Allows Null	Yes
Allows Duplicates	Yes
Random Access	Not supported (O(n) performance)

When to Use LinkedList?

Use LinkedList when:

• Frequent insertion/deletion at head/tail
• Implementing Queue (FIFO)
• Implementing Stack (LIFO)
• Real-time data processing
• When you need constant-time insertion
• When key operations are add/remove, not get()

Avoid LinkedList when:

• You need fast random access → use ArrayList
• Memory is limited
• You expect millions of elements (pointer-heavy)
• You do frequent searching → O(n)

How to Create a LinkedList in Java

Example 1: Basic LinkedList

import java.util.LinkedList;

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

        list.add("Java");
        list.add("Python");
        list.add("C++");

        System.out.println(list);
    }
}

Output:

[Java, Python, C++]

---

Important LinkedList Constructors

LinkedList<E> list = new LinkedList<>();          // empty list
LinkedList<E> list2 = new LinkedList<>(list1);    // copy another collection

---

Commonly Used LinkedList Methods

Below are all important methods, grouped with examples.

1. Add Methods

add(E e)

Adds an element to the end of the LinkedList. This is efficient because no shifting is required—just pointer updates.

list.add("PHP");

add(int index, E element)

Inserts an element at a specific index. Requires traversal to reach the position, so it's slower than adding at ends.

list.add(1, "HTML");

addFirst(E e)

Adds an element at the beginning (head) of the list. Operation is very fast (O(1)).

list.addFirst("Start");

addLast(E e)

Adds an element at the end (tail) of the list. Also an O(1) operation.

list.addLast("End");

offer(E e)

Adds an element to the tail in a queue-friendly way; returns boolean instead of throwing exceptions.

list.offer("Data");

offerFirst(E e) Inserts an element at the head safely, returning true/false instead of exceptions.

list.offerFirst("First");

offerLast(E e)

Adds an element at the tail safely with a boolean result.

list.offerLast("Last");

---

2. Get Methods

get(int index)

Returns the element at the specified index; requires traversal because LinkedList has no random access.

list.get(2);

getFirst()

Retrieves the first (head) element of the list; throws exception if list is empty.

list.getFirst();

getLast()

Retrieves the last (tail) element; throws exception if the list is empty.

list.getLast();

peek(), peekFirst(), peekLast()

Returns the head or tail element without removing it, and returns null if empty (safe operations).

list.peek();
list.peekFirst();
list.peekLast();

---

3. Remove Methods

remove()

Removes and returns the first element; throws exception if list is empty.

list.remove();

remove(int index)

Removes the element at the specified position; traversal required to reach index.

list.remove(2);

removeFirst(), removeLast()

Removes and returns the first or last element; both throw exceptions if list is empty.

list.removeFirst();
list.removeLast();

poll(), pollFirst(), pollLast()

Removes and returns the element, but returns null instead of throwing an exception if the list is empty.

list.poll();

---

4. Search Methods

contains(Object o)

Checks whether the element exists in the list; performs a linear search.

list.contains("Java");

indexOf(Object o)

Returns the index of the first occurrence of the element, or -1 if not found.

list.indexOf("Python");

lastIndexOf(Object o)

Returns the index of the last occurrence of the element, or -1 if not found.

list.lastIndexOf("C++");

---

5. Misc Methods

size()

Returns the number of elements currently stored in the LinkedList.

list.size();

clear()

Removes all elements from the list, making it empty.

list.clear();

isEmpty()

Checks whether the list contains no elements; returns true if empty.

list.isEmpty();

---

Time Complexity of LinkedList

Operation	Complexity	Explanation
addFirst / addLast	O(1)	Insertion at head or tail is constant-time because only pointers change.
removeFirst / removeLast	O(1)	Deleting from head or tail updates pointers; no traversal needed.
add(index)	O(n)	List must traverse node-by-node to reach the given index.
remove(index)	O(n)	Needs traversal to find the index before removal.
get(index)	O(n)	No random access; traversal from head or tail is required.
contains()	O(n)	Searches every node until element is found (linear search).

Advantages of LinkedList

• Best for insertion/deletion
• Efficient queue and stack operations
• No size limit
• Useful for real-time apps
• Implements Deque (so can replace Stack/Queue)

---

Disadvantages of LinkedList

• Slow random access
• High memory overhead
• Poor cache locality
• Traversal required

---

Real-World Use Cases of LinkedList

• Playlist navigation (Next/Previous)
• Undo/Redo (MS Word, editors)
• Browser history
• Task scheduling
• Real-time messaging queue
• Job processing (queues)
• Print queue management

---

Complete Example with All Major Operations

import java.util.LinkedList;

public class Demo {
    public static void main(String[] args) {

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

        list.add("A");
        list.add("B");
        list.add("C");

        list.addFirst("Start");
        list.addLast("End");

        System.out.println(list.get(2));
        System.out.println(list.getFirst());
        System.out.println(list.getLast());

        list.remove("B");
        list.removeLast();

        System.out.println(list.contains("C"));

        System.out.println(list);
    }
}