Linked List Collection Frameworks

Why Use Built-in Implementations?

Every major language ships a production-quality linked list implementation in its standard library. These implementations are:

• ›Tested — battle-hardened against edge cases you might miss
• ›Optimized — memory-efficient internal representations
• ›Feature-rich — dozens of utility methods built in
• ›Thread-safe variants — available where concurrency matters

In interviews and production code, you almost never implement a linked list from scratch. You use the built-in and focus on the algorithm. Understanding what the built-in provides — and its complexity for each operation — is what separates strong engineers from beginners.

Language Overview

Language    Primary Class         Secondary / Alternatives
────────────────────────────────────────────────────────────────
Java        LinkedList<E>         ArrayDeque<E>, Deque<E>
Python      collections.deque     list (array-backed, not linked)
C++         std::list<T>          std::forward_list<T>
JavaScript  No built-in LL        Array (array-backed), custom class

JavaScript has no built-in linked list — the native Array is array-backed. For interview problems in JavaScript, implement a simple Node class or use the Array with awareness of its O(n) shift costs.

Java: LinkedList<E>

Java's LinkedList is a doubly linked list that implements both the List and Deque interfaces. It gives you list operations (index access, insert at position) and deque operations (O(1) add/remove at both ends) in one class.

Declaration and Initialization

Output (Java):
Names: [Alice, Bob, Charlie]
Size:  3

Java LinkedList — Core Operations

Output (Java):
After adds:    [10, 20, 25, 30, 40]
First:         10
Last:          40
Index 2:       25
After removes: [20, 30]
Poll:          1
Contains Bob:  true

Java LinkedList as Stack and Queue

Output (Java):
Stack top: 30
Pop:       30
Stack:     [20, 10]
Queue front: 10
Dequeue:     10
Queue:       [20, 30]

Java: ArrayDeque<E> — Usually Preferred Over LinkedList

ArrayDeque is a resizable array-backed deque. For stack and queue use cases, it outperforms LinkedList in practice because it avoids per-node memory allocation and has better cache locality.

LinkedList<E>:
  Memory: ~48 bytes per node (prev pointer, next pointer, data, object header)
  Cache: poor — nodes scattered across heap
  Use when: frequent mid-list insertion/deletion with held iterators

ArrayDeque<E>:
  Memory: array of references, no per-node overhead
  Cache: excellent — elements stored contiguously
  Use when: stack or queue operations (push/pop/offer/poll at ends only)

Rule of thumb:
  Need a Queue?  → ArrayDeque (faster, less memory)
  Need a Stack?  → ArrayDeque (Java docs explicitly recommend it over Stack)
  Need index access or mid-list insert?  → LinkedList or ArrayList

C++: std::list vs std::forward_list

C++ provides two linked list types with different memory tradeoffs:

std::list<T>          — doubly linked list
  Nodes: prev + data + next  (~24 bytes per node on 64-bit)
  Bidirectional iterators
  Operations: push/pop front and back, insert/erase at iterator
  size(): O(1)

std::forward_list<T>  — singly linked list (C++11)
  Nodes: data + next  (~16 bytes per node on 64-bit)
  Forward iterators only
  Operations: push/pop front only, insert_after/erase_after
  size(): NOT PROVIDED — use std::distance (O(n))
  Use when: memory is critical and backward traversal not needed

Complete API Comparison Table

*O(1) given an iterator already at position — O(n) to find the position.

When to Use Each

Java:
  LinkedList  → when you need mid-list insertion with held iterators,
                or implementing LRU cache (uses both List and Deque ops)
  ArrayDeque  → stack, queue, or deque use only (faster than LinkedList)
  ArrayList   → when random access is frequent (most other cases)

Python:
  deque       → any stack, queue, or sliding window needing O(1) both ends
  list        → general use with random access
  Never use list.pop(0) or list.insert(0, x) in a loop — O(n) each

C++:
  std::list        → bidirectional traversal, frequent mid-insert with iterators
  std::forward_list → memory-critical singly linked, no backward traversal needed
  std::deque       → O(1) both ends AND O(1) random access (array-of-blocks)
  std::vector      → general purpose with random access (most other cases)

JavaScript:
  Array             → all general use cases (no built-in linked list)
  Custom Node class → interview problems specifically about linked list structure
  Map-based Deque   → O(1) front and back operations without O(n) array shifting

Common Mistakes Beginners Make

Using LinkedList as a queue with remove() instead of poll() in Java. remove() throws NoSuchElementException if the list is empty. poll() returns null. In production code, always use poll() for safe dequeue — it does not require a separate empty check.

Using Python list with pop(0) or insert(0, x) in a loop. These are O(n) operations. A loop of n iterations where each calls pop(0) gives O(n²) total. Use collections.deque for O(1) popleft() and appendleft().

Using std::forward_list::size() — it does not exist. forward_list has no size() method. You must use std::distance(fl.begin(), fl.end()) which is O(n), or track the count manually.

Using list.get(i) in Java inside a loop. LinkedList.get(i) is O(n) — iterating n times over indices with get() gives O(n²). Use an iterator (for (int x : list)) for O(n) traversal.

Preferring LinkedList over ArrayDeque for Java queue/stack. ArrayDeque is faster, uses less memory, and the Java documentation explicitly recommends it over LinkedList for stack and queue use cases.

Interview Questions

Q: When would you use LinkedList instead of ArrayList in Java?

LinkedList when: (1) you frequently insert or delete from the middle while already holding an iterator (O(1) with iterator vs O(n) for ArrayList), (2) you need O(1) operations at both ends as a deque, or (3) you are implementing a data structure like LRU cache that requires both list traversal and deque operations. ArrayList is preferred for almost everything else — random access is O(1) vs O(n) and cache locality is far better.

Q: Why is collections.deque preferred over list for queue operations in Python?

Python's built-in list uses a dynamic array internally. list.pop(0) (dequeue from front) and list.insert(0, x) (enqueue at front) are both O(n) — every element shifts. collections.deque is implemented as a doubly linked list of fixed-size blocks, giving O(1) popleft() and appendleft(). For n dequeue operations in a loop: list.pop(0) gives O(n²); deque.popleft() gives O(n).

Q: What is the difference between std::list and std::forward_list in C++?

std::list is a doubly linked list — each node has prev and next pointers, enabling bidirectional iteration, push_back, pop_back, and back(). std::forward_list is a singly linked list — each node has only next, enabling only forward iteration and front operations. forward_list uses about 33% less memory per node and is faster for simple forward traversal. It sacrifices push_back, back(), size(), and reverse iteration. Use forward_list when memory is critical and backward traversal is never needed.

FAQs

Does Java's LinkedList implement both List and Deque?

Yes. LinkedList<E> implements List<E>, Deque<E>, and Queue<E>. This makes it uniquely versatile — you can use it for index-based list operations (get(i), add(i, e)), queue operations (offer, poll, peek), stack operations (push, pop), and deque operations (addFirst, addLast, removeFirst, removeLast). The downside is that List operations like get(i) are O(n), which traps developers who assume array-like random access.

Is Python's deque actually a linked list?

Not exactly. CPython's deque is implemented as a doubly linked list of fixed-size blocks (each holding 64 elements). This gives O(1) append and popleft with better cache performance than a classic node-per-element linked list. Accessing elements by index (d[i]) is O(n) for middle elements but O(1) for the first and last — consistent with linked list semantics.

Why doesn't JavaScript have a built-in linked list?

JavaScript was designed primarily for the browser where DOM manipulation and event handling dominate. A doubly linked list was not considered essential enough for the core library. The built-in Array covers most use cases. For interview problems involving linked list structure (reversing, cycle detection, merging), implement a ListNode class from scratch — that is the expected approach in JavaScript interviews.

Quick Quiz

Question 1: In Java, which class is recommended for use as a stack or queue instead of LinkedList?

• ›A) ArrayList
• ›B) Stack
• ›C) ArrayDeque
• ›D) PriorityQueue

Answer: C) ArrayDeque. Java's own documentation recommends ArrayDeque over LinkedList for stack and queue use. It is faster (no per-node allocation, better cache locality) and uses less memory. Stack is a legacy class extending Vector — avoid it.

Question 2: What is the time complexity of Python list.pop(0) vs collections.deque.popleft()?

• ›A) Both O(1)
• ›B) list.pop(0) is O(n), deque.popleft() is O(1)
• ›C) Both O(n)
• ›D) list.pop(0) is O(1), deque.popleft() is O(n)

Answer: B) list.pop(0) is O(n), deque.popleft() is O(1). Python list is a dynamic array — removing from index 0 shifts all remaining elements left, costing O(n). deque is a linked list of blocks — popleft simply updates a pointer, costing O(1).

Question 3: Which C++ container provides O(1) random access AND O(1) push/pop at both ends?

• ›A) std::list
• ›B) std::forward_list
• ›C) std::deque
• ›D) std::vector

Answer: C) std::deque. std::deque is an array-of-blocks structure giving O(1) amortized push/pop at front and back, plus O(1) random access via operator[]. std::list has no O(1) random access. std::vector has O(n) push/pop at front.

Question 4: In Java's LinkedList, what is the complexity of get(index)?

• ›A) O(1) — same as ArrayList
• ›B) O(log n) — binary search on nodes
• ›C) O(n) — must traverse from head or tail to the index
• ›D) O(1) amortized — cached after first access

Answer: C) O(n). LinkedList.get(i) starts from head (or tail if i > size/2) and follows next (or prev) pointers until reaching index i. For index n/2 (middle), it takes n/2 steps. Using get(i) in a loop over n indices results in O(n²) — always use an iterator for O(n) full traversal.

Summary

Every major language provides built-in linked list implementations. The choice between them depends on whether you need bidirectional traversal, random access, thread safety, or minimal memory per node.

Key decisions to carry forward:

• ›Java — use ArrayDeque for stack/queue (faster), LinkedList for mid-list insert with iterators or LRU cache
• ›Python — always use collections.deque for queue/stack; never use list.pop(0) in a loop (O(n²))
• ›C++ — std::list for bidirectional doubly linked, std::forward_list for memory-critical singly linked, std::deque for O(1) both ends + random access
• ›JavaScript — no built-in; use Array (aware of O(n) shift/unshift) or implement ListNode class for interview problems
• ›LinkedList.get(i) in Java is O(n) — never call it in a loop; use iterators
• ›std::forward_list has no size(), no push_back(), no back(), no reverse iterator
• ›collections.deque supports a maxlen parameter for bounded circular buffers — no other language has this built in

In the next topic, you will explore Traversal and Searching — the patterns for walking linked lists, finding elements, and the two-pointer techniques that dominate linked list interview problems.