{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreichtbnyvqglvokycw2q2325frgsccithqonfld24siok33bxsw4p4",
    "uri": "at://did:plc:25rdn5elo5izoxrmtis34zuk/app.bsky.feed.post/3mogkbs4h3n22"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreidl65jnoo6inp5olkmprhwn3x5gufghvhgynasnocw62jw3nr5vee"
    },
    "mimeType": "image/webp",
    "size": 156304
  },
  "path": "/markyu/frontend-linear-data-structures-deep-dive-arrays-stacks-queues-and-linked-lists-mp2",
  "publishedAt": "2026-06-16T19:23:49.000Z",
  "site": "https://dev.to",
  "tags": [
    "computerscience",
    "algorithms",
    "beginners",
    "javascript"
  ],
  "textContent": "##  The Big Picture\n\nBefore diving into stacks, queues, and linked lists, it helps to know where they sit in the landscape.\n\n**Linear structures** - arrays, linked lists, stacks, queues - arrange elements one after another. Each node has exactly one predecessor and one successor.\n\n**Non-linear structures** - trees and graphs - are a different story for another day.\n\n##  Arrays\n\nArrays are the workhorse of JS. They use contiguous memory and give you direct access to any element by index - no traversal needed.\n\n###  Adding Elements\n\n**`push`** - appends to the end.\n\nSimple enough, but there's a catch: arrays are initialized with a fixed capacity. When you exceed it, JS triggers a resize: allocate a bigger block, copy everything over, free the old space. It's not free.\n\nLinked lists don't have this problem - they allocate memory per node, dynamically.\n\n**`unshift`** - prepends to the beginning.\n\nEvery existing element has to shift right by one to make room. The longer the array, the worse the performance. Fine for small arrays; avoid it in hot paths.\n\n**`splice`** - the Swiss Army knife.\n\n\n\n    array.splice(startIndex, deleteCount, ...itemsToAdd)\n\n\n  * `startIndex`: where to begin\n  * `deleteCount`: how many to remove (pass `0` to insert without deleting)\n  * `...itemsToAdd`: optional elements to insert\n\n\n\nKey things to know: `splice` mutates the original array and returns the deleted elements as a new array (empty array if nothing was deleted). Like all native array methods - `push`, `pop`, `unshift`, `shift` - it's **not** a pure function.\n\n\n\n    const arr = [1, 2];\n\n    arr.splice(1, 0, 3);   // insert 3 at index 1\n    console.log(arr);      // [1, 3, 2]\n\n    arr.splice(1, 1);      // delete element at index 1\n    console.log(arr);      // [1, 2]\n\n\n##  Stack\n\nA stack is LIFO - **Last In, First Out**. Think of it like a stack of plates: you can only add or remove from the top.\n\n\n\n    push → [bottom ... top] ← pop\n\n\nIn JS, implement with a plain array:\n\n\n\n    const stack = [];\n\n    stack.push('A');\n    stack.push('B');\n    stack.push('C');\n\n    while (stack.length) {\n      console.log(stack.pop()); // C, B, A\n    }\n\n\n  * `push` to add to the top\n  * `pop` to remove from the top\n  * Peek without removing: `stack[stack.length - 1]`\n\n\n\n##  Queue\n\nA queue is FIFO - **First In, First Out**. Like a checkout line: first in, first served.\n\n\n\n    push → [back ... front] → shift\n\n\n\n    const queue = [];\n\n    queue.push('Alice');\n    queue.push('Bob');\n    queue.push('Charlie');\n\n    while (queue.length) {\n      console.log(queue.shift()); // Alice, Bob, Charlie\n    }\n\n\n**Heads up:** `shift` has an O(n) cost - every element shifts left by one index after removal. For small arrays, no big deal. At scale, this becomes a bottleneck. If you're building a high-throughput queue, a linked list implementation is the right call.\n\n##  Linked Lists\n\n###  Why Not Just Use Arrays?\n\nArrays are great when you need fast random access. But inserting or deleting anywhere except the tail requires shifting elements - O(n) work.\n\nLinked lists flip the tradeoff:\n\n| Array | Linked List\n---|---|---\n**Memory** | Contiguous (if uniform types) | Scattered, node-by-node\n**Random access** | O(1) | O(n) - must traverse\n**Insert/delete** | O(n) at non-tail positions | O(1) once you have the node\n**Best for** | Frequent reads, small data | Frequent writes, large data\n\n###  Structure\n\nEach node holds two things:\n\n  * `val`: the data\n  * `next`: a pointer to the next node (`null` if it's the tail)\n\n\n\nIn JS, a linked list is just nested objects:\n\n\n\n    {\n      val: 1,\n      next: {\n        val: 2,\n        next: null\n      }\n    }\n\n\nTo access any element, you start at `head` and follow `next` pointers until you reach your target. There's no shortcut - no index to jump to directly.\n\n###  Basic Implementation\n\n\n    function ListNode(val) {\n      this.val = val;\n      this.next = null;\n    }\n\n    const head = new ListNode(1);\n    head.next = new ListNode(2);\n    // 1 -> 2 -> null\n\n\n###  Insert\n\nFind the predecessor node, point its `next` to the new node, then point the new node's `next` to the original successor. No data movement, just pointer reassignment - O(1).\n\n###  Delete\n\nFind the predecessor, skip the target by pointing `next` directly to the target's successor. Done - O(1).\n\nThe expensive part with linked lists isn't insert/delete - it's **finding the right node** , which always costs O(n).\n\n##  Two JS Gotchas Worth Knowing\n\n###  Array Memory Isn't Always Contiguous\n\nJS engines optimize for uniform-type arrays. Mix types and the engine may fall back to a hash map structure internally, losing the contiguous memory layout.\n\n\n\n    const fast = [1, 2, 3, 4];           // likely contiguous\n    const slower = ['a', 1, { b: 2 }];   // likely hash map internally\n\n\nDon't mix types in performance-sensitive arrays.\n\n###  `sort()` Sorts Strings by Default\n\n\n    [10, 2, 5].sort()                    // [10, 2, 5] - ASCII order, wrong\n    [10, 2, 5].sort((a, b) => a - b)     // [2, 5, 10] - correct\n\n\nAlways pass a comparator when sorting numbers.\n\n##  Quick Reference\n\nStructure | Add | Remove | Access | Rule\n---|---|---|---|---\nArray |  `push` O(1)* |  `pop` O(1) | O(1) by index | -\nStack | `push` | `pop` | O(n) | LIFO\nQueue | `push` |  `shift` O(n) | O(n) | FIFO\nLinked List | O(1) once positioned | O(1) once positioned | O(n) traversal | -\n\n*Amortized - occasional resize at O(n)\n\n##  Common Pitfalls\n\n  * **`unshift` is slow at scale** - it shifts every element. Use sparingly.\n  * **Array-based queues degrade** - `shift` is O(n). For high volume, use a linked list.\n  * **All native array methods mutate** - `push`, `pop`, `shift`, `unshift`, `splice` all modify in place. None are pure functions.\n  * **Don't mix array element types** - you lose the contiguous memory advantage.\n  * **Stacks and queues aren't separate data structures** - they're arrays (or linked lists) with constrained access rules.\n  * **Linked list insert/delete is fast; finding the node isn't** - the O(n) cost is in traversal, not the operation itself.\n\n",
  "title": "Frontend Linear Data Structures Deep Dive: Arrays, Stacks, Queues, and Linked Lists"
}