45:"/_next/static/chunks/33yus346z0l_n.js" 46:"/_next/static/chunks/2j22cxchii_xx.js" 47:"/_next/static/chunks/0iv56yrji_20j.js" 48:"/_next/static/chunks/32izpn90gvm22.js" 49:"/_next/static/chunks/3j8bi-zu9bqs4.js" 4a:"/_next/static/chunks/1z-pox7hqp2x3.js" 4b:"/_next/static/chunks/20w4eaqlekefm.js" 4c:"/_next/static/chunks/1tn-0fivsxsv1.js" 4d:"/_next/static/chunks/09nq57stwzkgf.js" 4e:"/_next/static/chunks/3m1xjj5kw5fie.js" 4f:"/_next/static/chunks/0gafyzg9j9yqj.js" 50:"/_next/static/chunks/3k2gyg36fnag_.js" 51:"/_next/static/chunks/3bgoyiso1rhn7.js" 52:"/_next/static/chunks/3cstd6xzfli_o.js" 53:"/_next/static/chunks/253gnmj0-cj17.js" 54:"/_next/static/chunks/0hlb44ca7-4a2.js" 55:"/_next/static/chunks/20329i6m_04t6.js" 56:"/_next/static/chunks/40mq7ggq-ozo4.js" 57:"/_next/static/chunks/082jo-0ajazgr.js" 58:"/_next/static/chunks/2ozcrjb_hh74t.js" 59:"/_next/static/chunks/01a-3hvnqu8wl.js" 5a:"/_next/static/chunks/05i8en-x14ibi.js" 5b:"/_next/static/chunks/3m0r7x0jt5wm7.js" 5c:"/_next/static/chunks/2k8pepwc4pxns.js" 5d:"/_next/static/chunks/0wa9m1-tphf9u.js" 5e:"/_next/static/chunks/30jdm3dwz834g.js" 5f:"/_next/static/chunks/0k9bl6dipnsvu.js" 60:"/_next/static/chunks/18ggtgz2yf759.js" 61:"/_next/static/chunks/0i3-eynrkvqi7.js" 62:I[593304,["$2a","$2b","$2c","$2d","$2e","$2f","$45","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61"],"OwnedHydration"] 63:T468,In our exploration of array-based queues, we encountered a fundamental tension: **linear arrays waste space**, and **circular queues add complexity**. Every dequeue operation in a linear array leaves a 'ghost slot' that cannot be reclaimed without expensive shifting operations. Circular queues solve this through modular arithmetic—but at the cost of more intricate pointer management and the need to distinguish between full and empty states. There exists a more elegant solution: the **linked list-based queue**. By leveraging the dynamic nature of linked lists, we can implement queues that: - **Never waste space**: Each node holds exactly one element, no empty slots - **Grow and shrink organically**: Memory is allocated and freed on demand - **Achieve true O(1) operations**: No amortization, no occasional expensive resizes - **Eliminate full/empty ambiguity**: The distinction is trivially clear The linked list queue represents one of the most natural marriages between a data structure and an abstract data type. Once you understand how singly linked lists work, implementing a queue becomes almost self-evident.64:T4a6,**Detailed analysis:** **Linear Array Queue Problems:** - After several dequeues, the front of the array accumulates 'dead' space - Either shift elements (O(n) per dequeue) or periodically compact (still expensive) - Fundamentally unsuitable for queues with significant throughput **Circular Array Queue Trade-offs:** - Elegant solution to the space problem using modular arithmetic - Requires careful handling of wrap-around - Distinguishing full from empty requires either wasting one slot or maintaining a separate count - Resizing is complicated—elements may wrap across the array boundary **Linked List Queue Advantages:** - No null slots, no wrap-around, no empty/full ambiguity - Each node allocated independently—grows without resizing - Pure O(1) operations with no edge cases for wrap-around - Shrinks automatically as elements are dequeued (memory returned to system) **Linked List Queue Disadvantages:** - Each node requires pointer storage (typically 8 bytes on 64-bit systems) - Nodes are scattered in memory—poor cache locality - Frequent small allocations may stress the memory allocator - Slightly higher constant factor per operation due to pointer dereferencing65:T420,// Generic Node class for a linked list queue public class QueueNode { T data; // The value stored in this node QueueNode next; // Reference to the next node (toward rear) public QueueNode(T data) { this.data = data; this.next = null; } @Override public String toString() { return "QueueNode(" + data + ")"; } } // Example usage: // For a queue of integers: QueueNode numberNode = new QueueNode<>(42); // For a queue of strings: QueueNode stringNode = new QueueNode<>("customer-request-001"); // For a queue of tasks (common real-world scenario): class Task { String id; int priority; Object payload; java.time.Instant createdAt; Task(String id, int priority, Object payload) { this.id = id; this.priority = priority; this.payload = payload; this.createdAt = java.time.Instant.now(); } } QueueNode taskNode = new QueueNode<>( new Task("task-123", 1, Map.of("action", "processOrder")) );66:T545,from typing import TypeVar, Generic, Optional T = TypeVar('T') class LinkedQueue(Generic[T]): """Queue implementation using a singly linked list with tail pointer""" def __init__(self) -> None: self._head: Optional[QueueNode[T]] = None # Front of queue self._tail: Optional[QueueNode[T]] = None # Rear of queue self._count: int = 0 # Element count # Core queue operations (to be implemented in detail) def enqueue(self, element: T) -> None: """Add element to the rear of the queue""" ... def dequeue(self) -> T: """Remove and return element from the front""" ... def front(self) -> T: """Return front element without removing""" ... def is_empty(self) -> bool: """Check if queue is empty""" ... def size(self) -> int: """Return number of elements in queue""" ... # Optional utility methods def clear(self) -> None: """Remove all elements from queue""" ... def peek(self) -> T: """Alias for front()""" return self.front() def __len__(self) -> int: """Support len() function""" return self._count def __str__(self) -> str: """String representation""" ...43:["$","$L62",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792298664646,"state":{"data":{"json":{"id":"seed_b6fa32e25c400ed418730661e1954b54","slug":"linked-list-queue-implementation","category":"Data Structures & Algorithms","topic":"Linked List-Based Queue Implementation","title":"Linked List-Based Queue Implementation","description":"Master the art of implementing queues using singly linked lists. Understand how maintaining both head and tail pointers enables O(1) enqueue and dequeue operations, explore the critical role of the tail pointer, and discover why linked list queues elegantly solve the space wastage problems inherent in array-based implementations.","difficulty":"INTERMEDIATE","estimatedMinutes":55,"pages":[{"id":"seed_395d0d596ce828fda5abfdf4058f55c5","title":"Using a Singly Linked List to Implement a Queue","order":0,"content":[{"id":"opening-hook","title":"From Arrays to Linked Lists: A Natural Evolution","content":[{"data":{"content":"$63"},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand why singly linked lists are ideally suited for queue implementation. You'll see how the structural properties of linked lists—specifically, efficient operations at both ends—map directly to queue semantics. You'll appreciate the elegance of this approach and understand the fundamental design decisions that make it work.","variant":"info"},"type":"callout"}]},{"id":"revisiting-queue-requirements","title":"Revisiting Queue Requirements","content":[{"data":{"content":"Before we dive into the linked list implementation, let's sharpen our understanding of what a queue truly requires. Unlike stacks, which access only one end, **queues demand efficient access to both ends**:\n\n**The Queue Contract (ADT Perspective):**"},"type":"text"},{"data":{"rows":[["`enqueue(element)`","Add element to the **rear**","O(1)"],["`dequeue()`","Remove and return element from the **front**","O(1)"],["`front()` / `peek()`","View front element without removing","O(1)"],["`isEmpty()`","Check if queue is empty","O(1)"],["`size()`","Return number of elements","O(1)"]],"headers":["Operation","Semantics","Required Complexity"]},"type":"table"},{"data":{"content":"The critical observation: **enqueue happens at one end, dequeue at the other**. This two-ended access pattern is what distinguishes queues from stacks and creates the implementation challenge we must address."},"type":"text"},{"data":{"height":"220px","mermaidSyntax":"graph LR\n subgraph Queue Operations\n ENQUEUE[\"enqueue(x)\"] --> REAR[\"REAR\"]\n FRONT[\"FRONT\"] --> DEQUEUE[\"dequeue()\"]\n end\n \n subgraph Queue Structure\n FRONT --> A[\"Element 1\"] --> B[\"Element 2\"] --> C[\"Element 3\"] --> REAR\n end\n \n style FRONT fill:#4CAF50,stroke:#2E7D32,color:#fff\n style REAR fill:#FF9800,stroke:#F57C00,color:#fff\n style A fill:#2196F3,stroke:#1565C0,color:#fff\n style B fill:#2196F3,stroke:#1565C0,color:#fff\n style C fill:#2196F3,stroke:#1565C0,color:#fff\n style ENQUEUE fill:#9C27B0,stroke:#7B1FA2,color:#fff\n style DEQUEUE fill:#9C27B0,stroke:#7B1FA2,color:#fff"},"type":"mermaid-excalidraw"},{"data":{"content":"**Why arrays struggle with this pattern:**\n\nArrays excel at random access and operations at one end (the high-index end). But queues need efficient operations at *both* ends:\n\n1. **Insertion at rear**: Arrays can do this in O(1) at the high end (if capacity permits)\n2. **Removal from front**: Arrays must shift all remaining elements—O(n)\n\nCircular arrays solve this by treating the array as a ring, but they introduce complexity around wrapping, capacity management, and distinguishing empty from full states.\n\n**Linked lists offer a more direct solution.** Instead of fighting against the array's structure, we use a data structure whose very nature supports the operations we need."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Core Insight","content":"A queue needs O(1) access to two ends: front (for dequeue) and rear (for enqueue). A singly linked list with a head pointer gives us O(1) access to the front. If we also maintain a tail pointer, we get O(1) access to the rear. This is the key architectural decision that makes linked list queues work.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"singly-linked-list-foundation","title":"The Singly Linked List Foundation","content":[{"data":{"content":"Let's refresh our understanding of singly linked lists and examine how their properties map to queue requirements.\n\n**Singly Linked List Structure:**\n\nA singly linked list consists of nodes, where each node contains:\n1. **Data**: The value stored in this node\n2. **Next**: A reference to the next node in the sequence (or null if this is the last node)\n\nThe list typically maintains a **head pointer** that references the first node. Operations at the head are O(1): we can insert a new node at the front or remove the front node by simply updating the head pointer."},"type":"text"},{"data":{"height":"180px","mermaidSyntax":"graph LR\n HEAD[\"HEAD\npointer\"] --> A[\"Node A\ndata: 10\nnext: →\"]\n A --> B[\"Node B\ndata: 20\nnext: →\"]\n B --> C[\"Node C\ndata: 30\nnext: →\"]\n C --> NULL[\"null\"]\n style HEAD fill:#4CAF50,stroke:#2E7D32,color:#fff\n style A fill:#2196F3,stroke:#1565C0,color:#fff\n style B fill:#2196F3,stroke:#1565C0,color:#fff\n style C fill:#2196F3,stroke:#1565C0,color:#fff\n style NULL fill:#9E9E9E,stroke:#616161,color:#fff"},"type":"mermaid-excalidraw"},{"data":{"content":"**Standard Singly Linked List Operation Complexities:**"},"type":"text"},{"data":{"rows":[["Insert at head","O(1)","Create node, link to old head, update head"],["Remove from head","O(1)","Update head to head.next"],["Insert at tail","O(n)","Must traverse entire list to find the last node"],["Remove from tail","O(n)","Must traverse to find the second-to-last node"],["Access by index","O(n)","Must traverse from head to desired position"]],"caption":"Singly Linked List Operations (Head Pointer Only)","headers":["Operation","Time Complexity","Why?"]},"type":"table"},{"data":{"content":"**The problem for queues:**\n\nWith only a head pointer, we can efficiently:\n- **Dequeue (remove from front)**: O(1) — This maps perfectly to removing from head\n- **Enqueue (add to rear)**: O(n) — We must traverse to find the tail!\n\nThis asymmetry means that a standard singly linked list with only a head pointer *cannot* implement an efficient queue. We'd get O(n) enqueue operations, making the data structure impractical for any serious use case.\n\n**The solution: maintain a tail pointer.**\n\nBy keeping track of both the first *and* last nodes, we gain O(1) access to both ends—exactly what queues require."},"type":"text"},{"data":{"icon":"AlertCircle","title":"Critical Design Decision","content":"A singly linked list with ONLY a head pointer gives O(n) tail insertion—unsuitable for queues. You MUST maintain a tail pointer to achieve O(1) enqueue. This is not optional; it's essential for the data structure to be practical.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"adding-tail-pointer","title":"Adding the Tail Pointer: The Key to Efficiency","content":[{"data":{"content":"The transformation from a head-only linked list to a queue-capable structure requires exactly one addition: **a tail pointer**.\n\n**Enhanced Singly Linked List for Queues:**\n\nWe maintain two pointers:\n1. **Head (Front of Queue)**: Points to the first node — where dequeues happen\n2. **Tail (Rear of Queue)**: Points to the last node — where enqueues happen\n\nThis simple addition changes our operation complexities dramatically:"},"type":"text"},{"data":{"height":"200px","mermaidSyntax":"graph LR\n HEAD[\"HEAD\n(front)\"] --> A[\"Node A\ndata: 10\"]\n A --> B[\"Node B\ndata: 20\"]\n B --> C[\"Node C\ndata: 30\"]\n C --> NULL[\"null\"]\n TAIL[\"TAIL\n(rear)\"] --> C\n style HEAD fill:#4CAF50,stroke:#2E7D32,color:#fff\n style A fill:#2196F3,stroke:#1565C0,color:#fff\n style B fill:#2196F3,stroke:#1565C0,color:#fff\n style C fill:#2196F3,stroke:#1565C0,color:#fff\n style TAIL fill:#FF9800,stroke:#F57C00,color:#fff\n style NULL fill:#9E9E9E,stroke:#616161,color:#fff"},"type":"mermaid-excalidraw"},{"data":{"rows":[["Insert at head","O(1)","No change"],["Remove from head","O(1)","No change"],["Insert at tail","O(1) ✓","Improved from O(n)!"],["Remove from tail","O(n)","Still O(n) — explained below"],["Access by index","O(n)","No change"]],"caption":"Singly Linked List Operations (With Tail Pointer)","headers":["Operation","Time Complexity","Change from Head-Only"]},"type":"table"},{"data":{"content":"**Why tail insertion becomes O(1):**\n\nWith a tail pointer, inserting at the end no longer requires traversal:\n\n```\n1. Create a new node with the given data\n2. Set the current tail's next pointer to the new node\n3. Update the tail pointer to the new node\n```\n\nNo traversal needed—we go directly to the tail and append. This is the key operation for `enqueue`.\n\n**Why tail removal remains O(n):**\n\nEven with a tail pointer, removing the last node requires finding the *second-to-last* node (to become the new tail). In a singly linked list, there's no back pointer—we can't go backwards from the tail. We'd need to traverse from the head to find it.\n\n**For queues, this doesn't matter!** We remove from the *front* (head), not the rear (tail). Dequeue is O(1).\n\nThis is the elegant match: queues need insertion at one end and removal at the other. With head and tail pointers, we get O(1) for both critical operations."},"type":"text"},{"data":{"icon":"Sparkles","title":"The FIFO Pattern Saves Us","content":"Queues follow FIFO: the first element in is the first one out. This means we always INSERT at the tail and REMOVE from the head. Since singly linked lists support O(1) insertion at tail (with tail pointer) and O(1) removal from head, the match is perfect. If queues required tail removal, we'd need a doubly linked list.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"mapping-operations","title":"Mapping Queue Operations to Linked List Operations","content":[{"data":{"content":"Now let's explicitly map each queue operation to its linked list equivalent. This mapping reveals why the implementation is so natural.\n\n**The Complete Mapping:**"},"type":"text"},{"data":{"rows":[["enqueue(element)","Insert at tail","O(1)","Create node, attach to current tail, update tail pointer"],["dequeue()","Remove from head","O(1)","Store head's data, update head to head.next, return data"],["front() / peek()","Read head's data","O(1)","Return head.data (without modifying structure)"],["isEmpty()","Check if head is null","O(1)","head == null means empty queue"],["size()","Return counter","O(1)","Maintain a size counter (increment on enqueue, decrement on dequeue)"]],"caption":"Queue ADT to Linked List Implementation Mapping","headers":["Queue Operation","Linked List Equivalent","Time","Description"]},"type":"table"},{"data":{"content":"**Visualizing the flow:**\n\nConsider a queue with elements [10, 20, 30] where 10 is at the front (first to be dequeued):\n\n```\nFRONT (head) --> [10] --> [20] --> [30] <-- REAR (tail)\n```\n\n**Enqueue(40)**:\n- Create node with value 40\n- Current tail (30) points to new node\n- Update tail pointer to new node\n\n```\nFRONT (head) --> [10] --> [20] --> [30] --> [40] <-- REAR (tail)\n```\n\n**Dequeue()**:\n- Store value at head (10)\n- Update head to point to next node (20)\n- Return stored value (10)\n\n```\nFRONT (head) --> [20] --> [30] --> [40] <-- REAR (tail)\n```\n\nThe structure grows and shrinks dynamically, with memory allocated and freed per operation."},"type":"text"},{"data":{"left":[{"data":{"items":["**True O(1)** for all operations—no amortization","**No capacity limits**—grows with system memory","**No wasted space**—each node holds exactly one element","**No full/empty ambiguity**—empty means head is null","**Simple pointer updates**—no modular arithmetic"],"title":{"icon":"CheckCircle","text":"What This Mapping Gives Us","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["**Pointer overhead**—extra 8 bytes per element (on 64-bit)","**Cache locality**—nodes scattered in memory","**Allocation overhead**—new allocation per enqueue","**No random access**—can't index into middle","**Memory fragmentation potential**—many small allocations"],"title":{"icon":"XCircle","text":"What We Give Up","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"}]},"type":"two-column"},{"data":{"icon":"Lightbulb","title":"The Trade-off Summary","content":"Linked list queues trade memory overhead and cache performance for simplicity, flexibility, and guaranteed O(1) operations. For most applications, this trade-off is favorable. The exceptions are embedded systems with severe memory constraints, or high-frequency trading systems where cache performance is paramount.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"comparison-array-queues","title":"Comparison with Array-Based Queues","content":[{"data":{"content":"To fully appreciate the linked list approach, let's contrast it with the array-based implementations we studied earlier. This comparison will solidify your understanding of when each approach is appropriate."},"type":"text"},{"data":{"rows":[["enqueue complexity","O(1) amortized","O(1) amortized","O(1) worst-case"],["dequeue complexity","O(n) — shifting required","O(1)","O(1) worst-case"],["Space efficiency","Poor — leaves gaps","Good — reuses space","Good — no gaps"],["Maximum capacity","Fixed or resizable","Fixed or resizable","Unbounded"],["Memory per element","Element size only","Element size only","Element + pointer"],["Cache performance","Excellent","Excellent","Poor"],["Implementation complexity","Simple","Moderate","Simple"],["Full/empty detection","Simple","Tricky (various methods)","Trivial"]],"caption":"Linked List Queue vs. Array-Based Queues","headers":["Characteristic","Linear Array Queue","Circular Array Queue","Linked List Queue"]},"type":"table"},{"data":{"content":"$64"},"type":"text"},{"data":{"icon":"Info","title":"When Cache Matters","content":"For high-performance systems processing millions of operations per second, the cache penalty of linked lists can be significant. In such cases, circular arrays (possibly with block allocation) may outperform linked lists despite their additional complexity. For typical application development, linked list simplicity and flexibility usually win.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"node-structure","title":"The Node Structure: Building Block of Our Queue","content":[{"data":{"content":"With the conceptual foundation established, let's define the concrete building block of our queue: the **Node**.\n\nA node in our linked list queue is identical to a standard singly linked list node—a simple container with two components:\n1. **data**: The value stored in this queue slot\n2. **next**: A reference to the next node in the queue (toward the rear), or null if this is the rear\n\n**Generic Node Definition:**"},"type":"text"},{"data":{"languages":[{"code":"// Generic Node class for a linked list queue\nclass QueueNode {\n data: T; // The value stored in this node\n next: QueueNode | null; // Reference to the next node (toward rear)\n \n constructor(data: T) {\n this.data = data;\n this.next = null;\n }\n}\n\n// Example usage:\n// For a queue of numbers:\nconst numberNode = new QueueNode(42);\n\n// For a queue of strings:\nconst stringNode = new QueueNode(\"customer-request-001\");\n\n// For a queue of tasks (common real-world scenario):\ninterface Task {\n id: string;\n priority: number;\n payload: unknown;\n createdAt: Date;\n}\n\nconst taskNode = new QueueNode({\n id: \"task-123\",\n priority: 1,\n payload: { action: \"processOrder\" },\n createdAt: new Date()\n});","label":"TypeScript","value":"typescript"},{"code":"from typing import TypeVar, Generic, Optional\nfrom dataclasses import dataclass\nfrom datetime import datetime\n\nT = TypeVar('T')\n\nclass QueueNode(Generic[T]):\n \"\"\"Generic Node class for a linked list queue\"\"\"\n \n def __init__(self, data: T):\n self.data: T = data # The value stored\n self.next: Optional['QueueNode[T]'] = None # Reference to next node\n \n def __repr__(self) -> str:\n return f\"QueueNode({self.data})\"\n\n# Example usage:\n# For a queue of numbers:\nnumber_node = QueueNode(42)\n\n# For a queue of strings:\nstring_node = QueueNode(\"customer-request-001\")\n\n# For a queue of tasks (common real-world scenario):\n@dataclass\nclass Task:\n id: str\n priority: int\n payload: dict\n created_at: datetime\n\ntask_node = QueueNode(Task(\n id=\"task-123\",\n priority=1,\n payload={\"action\": \"processOrder\"},\n created_at=datetime.now()\n))","label":"Python","value":"python"},{"code":"$65","label":"Java","value":"java"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"**Memory considerations:**\n\nEach node consumes:\n- Size of the data element (varies by type)\n- Size of a pointer/reference (typically 8 bytes on 64-bit systems)\n\nFor a queue storing 64-bit integers:\n- Array-based queue: 8 bytes per element\n- Linked list queue: 8 bytes (int) + 8 bytes (next pointer) = 16 bytes per element\n\nThis 2x overhead per element is the price of dynamic flexibility. For larger objects (strings, complex records, serialized data), the pointer overhead becomes proportionally smaller.\n\n**Real-world observation:** In task queues, message queues, and event systems, the payload is typically much larger than 8 bytes. A 1KB task payload makes the 8-byte pointer overhead negligible (< 1%)."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Encapsulation Best Practice","content":"In production code, the QueueNode class is typically defined as a private inner class within the Queue class. This prevents external code from directly manipulating nodes—preserving the queue abstraction and preventing invariant violations. Users should only interact through enqueue, dequeue, and peek methods.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"queue-class-skeleton","title":"LinkedQueue Class Skeleton","content":[{"data":{"content":"With our Node structure defined, let's outline the LinkedQueue class itself. This skeleton shows the fields and method signatures—we'll implement each method in detail in subsequent pages.\n\n**Key design decisions:**\n\n1. **head (front) pointer**: Points to the first node—where dequeues occur\n2. **tail (rear) pointer**: Points to the last node—where enqueues occur\n3. **size counter**: Provides O(1) size queries without traversal\n4. **Generic typing**: Queue is parameterized by element type T"},"type":"text"},{"data":{"languages":[{"code":"class LinkedQueue {\n private head: QueueNode | null; // Front of queue (first to dequeue)\n private tail: QueueNode | null; // Rear of queue (last enqueued)\n private count: number; // Number of elements in queue\n \n constructor() {\n this.head = null; // Empty queue: no front\n this.tail = null; // Empty queue: no rear \n this.count = 0; // No elements initially\n }\n \n // Core queue operations (to be implemented in detail)\n enqueue(element: T): void { /* Add to rear */ }\n dequeue(): T { /* Remove from front */ }\n front(): T { /* View front without removing */ }\n isEmpty(): boolean { /* Check if queue is empty */ }\n size(): number { /* Return element count */ }\n \n // Optional utility methods\n clear(): void { /* Remove all elements */ }\n peek(): T { /* Alias for front() */ }\n toString(): string { /* String representation */ }\n}","label":"TypeScript","value":"typescript"},{"code":"$66","label":"Python","value":"python"},{"code":"public class LinkedQueue {\n private QueueNode head; // Front of queue (first to dequeue)\n private QueueNode tail; // Rear of queue (last enqueued)\n private int count; // Number of elements in queue\n \n public LinkedQueue() {\n this.head = null; // Empty queue: no front\n this.tail = null; // Empty queue: no rear\n this.count = 0; // No elements initially\n }\n \n // Core queue operations (to be implemented in detail)\n public void enqueue(T element) { /* Add to rear */ }\n public T dequeue() { /* Remove from front */ }\n public T front() { /* View front without removing */ }\n public boolean isEmpty() { /* Check if queue is empty */ }\n public int size() { /* Return element count */ }\n \n // Optional utility methods\n public void clear() { /* Remove all elements */ }\n public T peek() { return front(); } // Alias for front()\n \n @Override\n public String toString() { /* String representation */ }\n}","label":"Java","value":"java"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"**Critical invariants we must maintain:**\n\n1. **If the queue is empty**: Both `head` and `tail` are null, `count` is 0\n2. **If the queue has one element**: `head` and `tail` point to the SAME node\n3. **If the queue has multiple elements**: `head` points to the front, `tail` to the rear, and following `next` pointers from head eventually reaches tail\n4. **The tail's `next` is always null**: It's the last node\n5. **`count` always equals the number of reachable nodes from head**\n\nThese invariants are essential for correctness. Every method must preserve them, and we can use them to detect bugs during testing."},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Single-Element Edge Case","content":"The most common source of bugs in linked list queues is the single-element case. When enqueueing into an empty queue or dequeueing the last element, both head AND tail pointers must be updated. Forgetting to update tail when head becomes/was null (and vice versa) leads to subtle, hard-to-diagnose bugs. Always handle this case explicitly.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary-path-forward","title":"Summary: The Foundation Is Set","content":[{"data":{"content":"We've established the conceptual foundation for implementing queues using singly linked lists. Let's consolidate our key insights:"},"type":"text"},{"data":{"type":"ordered","items":["**Queues need two-end access**: Enqueue at rear, dequeue at front—unlike stacks which only access one end.","**Simple linked lists aren't enough**: A head-only linked list gives O(n) tail insertion—unsuitable for queues.","**The tail pointer is essential**: By maintaining both head AND tail pointers, we achieve O(1) for both enqueue (at tail) and dequeue (at head).","**FIFO matches linked list asymmetry**: We insert at tail (O(1) with tail pointer) and remove from head (O(1)). The fact that tail removal is O(n) doesn't matter for queues.","**No capacity limits**: Unlike circular arrays, linked queues grow indefinitely (bound only by system memory).","**Trade-offs exist**: We sacrifice cache locality and add per-element pointer overhead in exchange for simplicity and guaranteed O(1) operations."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's next:**\n\nWith the conceptual model established, we'll now examine the specific roles of the head and tail pointers in greater detail. Understanding how `head` serves as our front pointer and `tail` as our rear pointer—and executing the invariant-preserving updates during enqueue and dequeue—is crucial for correct implementation."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand why singly linked lists with tail pointers are an elegant and efficient choice for implementing queues. The structural properties align perfectly with FIFO semantics, enabling guaranteed O(1) operations with unlimited capacity. Next, we'll explore the specific roles of head as front and tail as rear.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_301018e8d422acbd7d28df89028fa346","title":"Head as Front, Tail as Rear","order":1,"content":null,"isLocked":true},{"id":"seed_6e37b49540433c43342ed61bd58e5278","title":"Enqueue and Dequeue in O(1)","order":2,"content":null,"isLocked":true},{"id":"seed_b29abc1ed19c8a55e68b181fea8f5749","title":"Tail Pointer Necessity","order":3,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792298664645,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"linked-list-queue-implementation"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"linked-list-queue-implementation\"},\"type\":\"query\"}]"},{"dehydratedAt":1792298664647,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792298664643,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_b6fa32e25c400ed418730661e1954b54"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_b6fa32e25c400ed418730661e1954b54\"},\"type\":\"query\"}]"},{"dehydratedAt":1792298664647,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792298664643,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_301018e8d422acbd7d28df89028fa346"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_301018e8d422acbd7d28df89028fa346\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792298664647,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792298664643,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_301018e8d422acbd7d28df89028fa346"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_301018e8d422acbd7d28df89028fa346\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792298664647,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792298664643,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_301018e8d422acbd7d28df89028fa346"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_301018e8d422acbd7d28df89028fa346\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792298664647,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_301018e8d422acbd7d28df89028fa346","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_301018e8d422acbd7d28df89028fa346\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@67"}]},"children":"$L68"}]