🧠 Mastering Data Structures in Java: LinkedList - Part 3

🔍 What Is a LinkedList?

A LinkedList in Java is a linear data structure where elements (called nodes) are connected using references (links).
Each node stores:

The data itself, and

A reference (or pointer) to the next (and previous) node in the sequence.

In Java, LinkedList is a doubly-linked list — meaning each node knows both its previous and next neighbor.

You’ll find it in the Java Collections Framework:

import java.util.LinkedList;


---

⚙️ Example

import java.util.LinkedList;

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

        tasks.add("Write code");
        tasks.add("Test code");
        tasks.add("Deploy app");

        System.out.println(tasks); // [Write code, Test code, Deploy app]

        tasks.addFirst("Plan feature");
        tasks.addLast("Refactor");
        System.out.println(tasks); // [Plan feature, Write code, Test code, Deploy app, Refactor]

        tasks.remove("Test code");
        System.out.println(tasks); // [Plan feature, Write code, Deploy app, Refactor]
    }
}

---

🧩 How It Works Internally

A LinkedList consists of nodes linked together.
Each node contains:

[ previous | data | next ]


When adding/removing elements:

ArrayList shifts elements → O(n)

LinkedList just changes links → O(1) (if position is known)

However, random access like get(index) is slower → O(n).

---

⚙️ Common Methods

Method	Description
add(E e)	Adds an element at the end
addFirst(E e) / addLast(E e)	Adds at beginning or end
remove() / removeFirst() / removeLast()	Removes elements
get(int index)	Retrieves element by index
getFirst() / getLast()	Retrieves first or last element
size()	Returns list size
clear()	Removes all elements

---

⚖️ LinkedList vs ArrayList

Feature	ArrayList	LinkedList
Structure	Dynamic array	Doubly-linked list
Access time	O(1)	O(n)
Insert/remove (middle)	O(n)	O(1) if node known
Memory usage	Less	More (extra pointers)
Use case	Frequent access	Frequent insert/delete

✅ Rule of thumb:

Choose ArrayList → when you read data often.

Choose LinkedList → when you insert or remove elements often.

---

🌍 Real-World Use Cases

Music players: Playlist queue (next/previous song navigation)

Undo/Redo systems: Navigating previous and next actions

Web browsers: Forward and backward page navigation

Task scheduling: Maintaining dynamic to-do or job queues

Memory management systems: Storing free/used memory blocks dynamically

---

Example:

LinkedList<String> browserHistory = new LinkedList<>();
browserHistory.add("Google");
browserHistory.add("StackOverflow");
browserHistory.add("GitHub");

---

⚡ Pro Tips

Use LinkedList for queues and stacks — it implements both Deque and List interfaces.

Deque<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
System.out.println(queue.remove()); // 1

• Avoid random access like list.get(1000) — it’s slow.
• Can contain null elements.
• Not thread-safe, so use Collections.synchronizedList() if needed.

---

🧮 Performance Summary

Operation	Time Complexity
Add/Remove First	O(1)
Add/Remove Last	O(1)
Add/Remove Middle	O(n)
Get by Index	O(n)
Iteration	O(n)

---

💡 Final Thought

Think of LinkedList as a flexible train — you can easily attach or detach wagons (nodes) without rearranging the entire train.
It might not be as fast to jump between wagons, but it’s perfect when the structure itself keeps changing.