Linked List vs Array When to Choose Which in DSA Typescript - Expert Trade-off Analysis

Overview - Linked List vs Array When to Choose Which

What is it?

Linked lists and arrays are two ways to store collections of items. An array keeps items in a fixed order in continuous memory, while a linked list connects items with pointers, allowing flexible order and size. Both let you store multiple values, but they work differently under the hood. Choosing between them depends on how you want to add, remove, or access items.

Why it matters

Choosing the right structure affects how fast your program runs and how much memory it uses. Without knowing when to use arrays or linked lists, your program might be slow or waste resources. For example, if you pick an array but need to add items often, it can be slow. Using the right one makes your code efficient and easier to maintain.

Where it fits

Before this, you should understand basic data storage and how memory works. After this, you can learn about more complex structures like trees and hash tables that build on these ideas.

Mental Model

Core Idea

Arrays store items in a fixed, continuous block of memory for fast access, while linked lists store items scattered in memory connected by links for flexible size and easy insertion or deletion.

Think of it like...

Think of an array like a row of mailboxes lined up on a street, each with a fixed address you can quickly find. A linked list is like a treasure hunt where each clue (node) tells you where to find the next clue, so you follow the chain step by step.

Array: [Item0][Item1][Item2][Item3]

Linked List:
[Item0|Next] -> [Item1|Next] -> [Item2|Next] -> [Item3|null]

Build-Up - 7 Steps

1

Foundation

Understanding Arrays Basics

Concept: Introduce arrays as fixed-size collections stored in continuous memory locations.

An array is like a row of boxes where each box holds one item. All boxes are next to each other in memory. You can quickly find any item by its position number (index). For example, in TypeScript: const arr = [10, 20, 30]; arr[1] gives 20 instantly.

Result

You can access any item fast by its index, but adding or removing items in the middle requires shifting others.

Understanding arrays' fixed size and continuous memory explains why access is fast but insertion or deletion can be slow.

2

Foundation

Understanding Linked Lists Basics

Concept: Introduce linked lists as collections where each item points to the next, allowing flexible size.

A linked list is a chain of nodes. Each node holds data and a link (pointer) to the next node. The nodes can be anywhere in memory. To find an item, you start at the first node and follow links until you reach it. For example, a node can be: class Node { value: number; next: Node | null; constructor(value: number) { this.value = value; this.next = null; } }

Result

You can add or remove items easily by changing links, but accessing an item by position takes time because you must follow the chain.

Knowing linked lists use pointers to connect nodes clarifies why they are flexible but slower to access by position.

3

Intermediate

Comparing Access Speed

🤔Before reading on: do you think accessing the 5th item is faster in an array or a linked list? Commit to your answer.

Concept: Explain how arrays allow direct access by index, while linked lists require traversal.

Arrays store items in continuous memory, so the computer calculates the address of any item instantly using its index. Linked lists store nodes scattered in memory, so to get the 5th item, you must start at the first node and follow 4 links one by one.

Result

Accessing the 5th item in an array is very fast (constant time), but in a linked list it is slower (linear time).

Understanding this difference helps decide when fast random access is needed versus when flexible size matters more.

4

Intermediate

Insertion and Deletion Differences

🤔Before reading on: do you think adding an item in the middle is easier in an array or a linked list? Commit to your answer.

Concept: Show how linked lists allow easy insertion and deletion by changing links, while arrays require shifting items.

In arrays, inserting or deleting an item in the middle means moving all later items to keep them continuous. This can be slow. In linked lists, you just change the 'next' pointer of the previous node to point to the new node or skip the removed node, which is fast.

Result

Linked lists handle insertions and deletions in the middle efficiently, while arrays do not.

Knowing this difference guides choosing linked lists when frequent insertions or deletions happen.

5

Intermediate

Memory Usage and Allocation

Concept: Explain how arrays and linked lists differ in memory use and allocation.

Arrays allocate a fixed block of memory upfront, which can waste space if not fully used or require resizing if too small. Linked lists allocate memory for each node separately as needed, which uses memory more flexibly but adds overhead for storing pointers.

Result

Arrays can be memory efficient if size is known, but resizing is costly. Linked lists use memory dynamically but with extra space per node.

Understanding memory tradeoffs helps pick the right structure based on expected data size and operations.

6

Advanced

When to Choose Arrays vs Linked Lists

🤔Before reading on: do you think arrays or linked lists are better for implementing undo features? Commit to your answer.

Concept: Summarize practical scenarios where one structure is better than the other.

Use arrays when you need fast access by index, fixed size, or simple iteration. Use linked lists when you expect many insertions and deletions, or when size changes often. For example, undo features often use linked lists to add or remove states quickly. Arrays are better for storing images or fixed data where quick access matters.

Result

Choosing the right structure improves performance and code simplicity in real applications.

Knowing practical use cases prevents inefficient designs and helps write better programs.

7

Expert

Hybrid and Modern Alternatives

🤔Before reading on: do you think modern languages still use raw linked lists often? Commit to your answer.

Concept: Discuss how modern systems combine arrays and linked lists or use other structures for best results.

Many modern systems use dynamic arrays (like JavaScript arrays) that resize automatically, combining array speed with flexibility. Some use linked lists internally for queues or undo stacks. Hybrid structures like linked arrays or skip lists improve performance further. Raw linked lists are less common alone but still important for understanding.

Result

Modern data structures blend array and linked list ideas to balance speed and flexibility.

Understanding these hybrids helps grasp advanced data structures and optimize real-world systems.

Under the Hood

Arrays allocate a single continuous block of memory where each element is stored one after another. The computer calculates the address of any element by adding the index times the element size to the start address. Linked lists allocate memory for each node separately anywhere in memory. Each node stores data plus a pointer to the next node's memory address. Traversing a linked list means following these pointers one by one.

Why designed this way?

Arrays were designed for fast random access when size is known upfront, minimizing overhead. Linked lists were designed to allow flexible size and efficient insertions/deletions without shifting elements. The tradeoff is between speed of access and flexibility of size. Early computers had limited memory, so these designs balanced hardware constraints and programming needs.

Array Memory Layout:
┌─────────┬─────────┬─────────┬─────────┐
│ Item 0  │ Item 1  │ Item 2  │ Item 3  │
└─────────┴─────────┴─────────┴─────────┘

Linked List Memory Layout:
[Node1] -> [Node2] -> [Node3] -> null
Each node:
┌─────────────┬─────────────┐
│ Data        │ Pointer     │
└─────────────┴─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Is accessing the middle element in a linked list as fast as in an array? Commit to yes or no.

Common Belief: Linked lists provide fast access to any element just like arrays.

Reality: Linked lists require traversing from the start to reach a middle element, making access slower than arrays.

Why it matters: Assuming fast access in linked lists can lead to slow programs when frequent random access is needed.

Quick: Do linked lists always use less memory than arrays? Commit to yes or no.

Common Belief: Linked lists use less memory because they allocate only what is needed.

Reality: Linked lists use extra memory for pointers in each node, often making them use more memory than arrays.

Why it matters: Ignoring pointer overhead can cause unexpected memory bloat in large linked lists.

Quick: Can arrays easily grow without performance cost? Commit to yes or no.

Common Belief: Arrays can grow dynamically without any slowdown or copying.

Reality: Dynamic arrays must copy all elements to a new larger block when resizing, which is costly.

Why it matters: Not accounting for resizing cost can cause performance issues in programs that add many items.

Quick: Are linked lists always better for insertions? Commit to yes or no.

Common Belief: Linked lists always make insertions faster than arrays.

Reality: Linked lists are faster only if you have a pointer to the insertion point; otherwise, you must traverse the list first.

Why it matters: Assuming always faster insertions can lead to inefficient code if traversal cost is ignored.

Expert Zone

1

Linked lists suffer from poor cache locality because nodes are scattered in memory, slowing down traversal compared to arrays.

2

Dynamic arrays often double their size when full to amortize resizing cost, balancing speed and memory use.

3

Some languages use linked lists internally for immutable data structures to efficiently share parts without copying.

When NOT to use

Avoid linked lists when you need frequent random access or when memory overhead is critical; use arrays or balanced trees instead. Avoid arrays when size changes unpredictably and insertions/deletions are frequent; consider linked lists or dynamic arrays.

Production Patterns

In production, arrays are used for buffers, image data, and lookup tables. Linked lists appear in undo stacks, adjacency lists in graphs, and task scheduling. Hybrid structures like vectors with linked nodes or skip lists combine benefits for complex systems.

Connections

Hash Tables

Builds-on arrays and linked lists

Hash tables often use arrays for buckets and linked lists to handle collisions, showing how these structures combine for efficient lookup.

Memory Management

Underlying hardware concept

Understanding how memory is allocated and accessed helps explain why arrays have fast access and linked lists have pointer overhead.

Supply Chain Logistics

Similar pattern of fixed routes vs flexible paths

Arrays are like fixed conveyor belts delivering items quickly, while linked lists are like trucks following flexible routes, illustrating tradeoffs between speed and flexibility.

Common Pitfalls

#1 Trying to access a linked list element by index directly.

Wrong approach:

function getElement(list: Node | null, index: number): number | null {
return list[index]; // wrong: linked lists don't support direct indexing
}

Correct approach:

function getElement(list: Node | null, index: number): number | null {
let current = list;
let count = 0;
while (current !== null) {
if (count === index) return current.value;
current = current.next;
count++;
}
return null;
}

Root cause:

Misunderstanding that linked lists do not have continuous memory or direct indexing.

#2 Inserting into an array by just assigning to a new index beyond its length without resizing.

Wrong approach:

const arr = [1, 2, 3];
arr[5] = 10; // creates holes, unexpected behavior

Correct approach:

const arr = [1, 2, 3];
arr.push(4); // adds item properly without holes

Root cause:

Not understanding arrays have fixed length and how to properly add items.

#3 Assuming linked lists use less memory and ignoring pointer size.

Wrong approach:

// Using linked list for large data without considering pointer overhead
class Node {
value: number;
next: Node | null;
constructor(value: number) {
this.value = value;
this.next = null;
}
}
// Large memory usage unnoticed

Correct approach:

// Use array if memory is tight and size is known
const arr: number[] = new Array(1000);

Root cause:

Ignoring that each linked list node stores extra pointer data increasing memory use.

Key Takeaways

Arrays store items in continuous memory allowing fast access by index but have fixed size and costly insertions or deletions in the middle.

Linked lists store items scattered in memory connected by pointers, allowing flexible size and efficient insertions or deletions but slower access by position.

Choosing between arrays and linked lists depends on your needs: fast random access favors arrays, frequent insertions/deletions favor linked lists.

Modern systems often use dynamic arrays or hybrid structures to balance speed and flexibility.

Understanding memory layout and operation costs prevents common performance and memory mistakes.

Practice

1. Which data structure is better when you need fast random access to elements by index?

easy

A. Stack

B. Linked List

C. Array

D. Queue

Solution

1. Step 1: Understand random access in arrays

   Arrays store elements in contiguous memory, so accessing by index is fast and direct.

2. Step 2: Understand random access in linked lists

   Linked lists require traversal from the head to reach an index, which is slower.

3. Final Answer:

   Array -> Option C

4. Quick Check:

   Fast random access = Array [OK]

Hint: Arrays give fast index access; linked lists do not [OK]

Common Mistakes:

• Thinking linked lists allow fast index access
• Confusing stack or queue with arrays
• Assuming all data structures have same access speed

2. Which of the following is the correct way to declare an empty linked list node in TypeScript?

easy

A. const node = new LinkedListNode(null);

B. const node = new LinkedListNode();

C. const node = LinkedListNode();

D. const node = LinkedListNode(null);

Solution

1. Step 1: Understand TypeScript class instantiation

   To create an instance, use the 'new' keyword with constructor parameters.

2. Step 2: Check constructor parameters

   LinkedListNode usually requires a value; null can represent empty data.

3. Final Answer:

   const node = new LinkedListNode(null); -> Option A

4. Quick Check:

   Use 'new' with constructor args for instances [OK]

Hint: Use 'new' keyword with constructor parameters to create nodes [OK]

Common Mistakes:

• Omitting 'new' keyword
• Calling class like a function without 'new'
• Passing no arguments when constructor expects one

3. Given this TypeScript code, what is the printed output?

class Node {
  value: number;
  next: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

const head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);

let current = head;
const result: number[] = [];
while (current !== null) {
  result.push(current.value);
  current = current.next;
}
console.log(result);

medium

A. [1, 2, 3]

B. [3, 2, 1]

C. [1, 3, 2]

D. []

Solution

1. Step 1: Build the linked list nodes

   Nodes created with values 1, 2, 3 linked in order: 1 -> 2 -> 3 -> null.

2. Step 2: Traverse and collect values

   Loop pushes values 1, then 2, then 3 into result array.

3. Final Answer:

   [1, 2, 3] -> Option A

4. Quick Check:

   Traverse linked list in order = [1, 2, 3] [OK]

Hint: Traverse linked list from head to null to get values in order [OK]

Common Mistakes:

• Confusing order of nodes
• Not updating current pointer correctly
• Expecting reversed output

4. This TypeScript code tries to insert a new node at the start of a linked list but has a bug. What is the error?

class Node {
  value: number;
  next: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

let head = new Node(1);
head.next = new Node(2);

function insertAtStart(newValue: number) {
  const newNode = new Node(newValue);
  newNode.next = head.next;
  head = newNode;
}

insertAtStart(0);

let current = head;
const result: number[] = [];
while (current !== null) {
  result.push(current.value);
  current = current.next;
}
console.log(result);

medium

A. head should not be reassigned inside the function

B. newNode.next should point to head, not head.next

C. Node constructor missing initialization of next

D. insertAtStart should return the new head

Solution

1. Step 1: Analyze insertion logic

   New node's next is set to head.next, skipping the current head node.

2. Step 2: Correct pointer assignment

   To insert at start, newNode.next must point to current head, preserving the list.

3. Final Answer:

   newNode.next should point to head, not head.next -> Option B

4. Quick Check:

   Insert at start = newNode.next = head [OK]

Hint: New head's next must link to old head, not old head's next [OK]

Common Mistakes:

• Setting newNode.next to head.next causes node loss
• Not updating head reference properly
• Confusing next pointers in linked list

5. You need to frequently insert and delete elements in the middle of a large collection. Which data structure is better and why? A) Array, because it allows fast random access. B) Linked List, because it supports binary search efficiently. C) Array, because it uses less memory. D) Linked List, because it allows fast insertion and deletion without shifting elements.

hard

A. Array, because it allows fast random access.

B. Linked List, because it supports binary search efficiently.

C. Array, because it uses less memory.

D. Linked List, because it allows fast insertion and deletion without shifting elements.

Solution

1. Step 1: Consider insertion and deletion in arrays

   Arrays require shifting elements when inserting or deleting in the middle, which is slow.

2. Step 2: Consider linked list advantages

   Linked lists can insert or delete nodes by changing pointers without shifting elements, making these operations faster.

3. Final Answer:

   Linked List, because it allows fast insertion and deletion without shifting elements. -> Option D

4. Quick Check:

   Frequent middle insert/delete = Linked List [OK]

Hint: Linked lists excel at middle insert/delete without shifting [OK]

Common Mistakes:

• Choosing array for frequent middle insert/delete
• Thinking linked lists support binary search efficiently
• Ignoring cost of shifting elements in arrays