LinkedList as Queue and Deque – Dual Use Case in Java

Java’s LinkedList is a unique and versatile collection that acts both as a Queue and a Deque, enabling developers to implement FIFO and LIFO structures using a single class. Understanding this dual-purpose behavior is essential for efficient and flexible data handling in Java.

🔍 Introduction

The LinkedList class is part of the java.util package and implements multiple interfaces: List, Deque, Queue, and Cloneable. This hybrid nature allows it to support indexed access like arrays, and insertion/removal from both ends like a queue or stack.

In this tutorial, you'll learn:

• How LinkedList works internally
• How it supports both Queue and Deque interfaces
• Performance insights and real-world use cases

---

📦 Core Purpose in Java Collections Framework

The LinkedList class is designed to serve as:

• A sequential list of elements (via List)
• A queue-like structure (via Queue)
• A double-ended queue (via Deque)

Its non-contiguous memory model makes it ideal for scenarios where frequent insertions/deletions occur, especially from the start or middle of the collection.

---

🧪 Java Syntax & Behavior

Creating a LinkedList as Queue

Queue<String> queue = new LinkedList<>();
queue.offer("Java");
queue.offer("Python");
System.out.println(queue.poll()); // Output: Java (FIFO)

Using LinkedList as Deque (Stack + Queue)

Deque<String> deque = new LinkedList<>();
deque.addFirst("Front");
deque.addLast("Back");
System.out.println(deque.removeLast()); // Output: Back

LinkedList as Stack

Deque<String> stack = new LinkedList<>();
stack.push("First");
stack.push("Second");
System.out.println(stack.pop()); // Output: Second (LIFO)

---

🧠 Internal Working and Memory Model

• Internally implemented as a doubly linked list
• Each node stores:
  • Element reference
  • Link to the previous node
  • Link to the next node
• No resizing overhead like ArrayList
• Efficient for head/tail operations (O(1))
• Less efficient for random access (O(n))

---

📊 Performance and Big-O Complexity

Operation	Time Complexity
Insertion/Removal (ends)	O(1)
Random access	O(n)
Search	O(n)
Iteration	O(n)

---

💡 Real-World Use Cases

• Undo functionality (stack behavior)
• Message queues (FIFO)
• Double-ended task scheduling
• Sliding window algorithms

---

🔄 Comparisons with Other Collections

Feature	LinkedList	ArrayDeque	ArrayList
Random Access	❌ O(n)	❌ O(n)	✅ O(1)
Queue Support	✅ Yes	✅ Yes	❌ No
Deque Support	✅ Yes	✅ Yes	❌ No
Resizing Cost	❌ None	✅ Moderate	✅ Moderate
Thread Safety	❌ Not synchronized	❌ Not synchronized	❌ Not synchronized

---

🧬 Functional Programming Support

LinkedList<String> languages = new LinkedList<>(List.of("Java", "Python", "Go"));
languages.stream()
         .filter(lang -> lang.startsWith("J"))
         .forEach(System.out::println); // Output: Java

---

⚠️ Anti-Patterns & Misuse Cases

• Avoid using LinkedList for index-based access in tight loops
• Avoid for large collections when memory overhead is a concern
• Don't assume thread safety — use Collections.synchronizedList if needed

---

🛠️ Refactoring Legacy Code

If you see manual linked list node management in older code, you can safely refactor to LinkedList, benefiting from Java's native handling and safety.

---

✅ Best Practices

• Use Deque reference when using LinkedList as stack/queue to avoid accidental list operations.
• Prefer ArrayDeque for better performance if ordering isn’t critical.
• Use Iterator when modifying during iteration to avoid ConcurrentModificationException.

---

📌 What's New in Java Versions?

Java 8

• Introduced Stream, Predicate, and lambda support for all collections.
• Easy integration with LinkedList.

Java 9

• List.of() for immutable initialization.

Java 10+

• var keyword for inference: var list = new LinkedList<String>();

Java 21

• Structured concurrency and scoped values (not specific to LinkedList, but improves parallel workflows where collections are shared).

---

🧾 Conclusion & Key Takeaways

• LinkedList is a flexible collection supporting both Queue and Deque.
• Great for scenarios requiring frequent head/tail operations.
• Trade-off: poor random access performance.

---

❓ FAQ – LinkedList as Queue/Deque

1. Can I use LinkedList as a stack?

Yes. Use push() and pop() via Deque interface.

2. Is LinkedList thread-safe?

No. You must wrap it using Collections.synchronizedList().

3. Which is faster: LinkedList or ArrayDeque?

ArrayDeque is generally faster due to better memory locality.

4. Does LinkedList resize like ArrayList?

No. It's based on nodes, not arrays.

5. Is insertion at the middle efficient?

No. It’s O(n) since traversal is needed.

6. Can I remove elements while iterating?

Yes, use the Iterator.remove() method to avoid exceptions.

7. Should I use it in multithreaded code?

Not directly. Wrap it or use concurrent collections.

8. What is the default capacity?

There’s no fixed capacity; it grows as nodes are added.

9. Can I convert it to array?

Yes. Use toArray() or toArray(new String[0]).

10. Is LinkedList deprecated?

No. It is actively maintained and commonly used.

---