Arrays and Linked Lists

Why this lesson matters

In Introduction to Data Structures and Algorithms, you saw that choosing the right structure changes how fast and clean your solution can be.

Now we’ll study two foundational structures:

• Arrays: values stored in an ordered, index-based sequence
• Linked lists: values stored in nodes connected by references

These show up everywhere in easy and medium DSA problems. More importantly, they teach a core tradeoff: fast access vs flexible insertion/removal.

By the end, you should be able to look at a problem and ask: “Do I need random access, or do I mostly walk and rearrange items?”

Arrays: ordered slots

An array is like a row of labeled boxes:

index:   0    1    2    3
value: [10] [20] [30] [40]

The big advantage is direct index access. If you know you want index 2, JavaScript can jump straight there.

Common array operations:

• Read by index: usually O(1)
• Update by index: usually O(1)
• Append to end with push: usually O(1) amortized
• Insert/remove at front: usually O(n) because elements shift

JavaScript arrays are flexible and convenient, but the mental model of indexed slots is still the one you’ll use in interviews and problem solving.

```javascript
const prices = [101, 105, 98, 110];

console.log("First price:", prices[0]);
console.log("Third price:", prices[2]);

prices[2] = 99;
console.log("After update:", prices);

prices.push(115);
console.log("After append:", prices);

prices.unshift(95);
console.log("After front insert:", prices);
```

You have an array with n items. Which operation usually requires shifting many elements?

Linked lists: connected nodes

A linked list stores data in nodes. Each node points to the next node.

head
 ↓
[10 | next] → [20 | next] → [30 | null]

A node usually contains:

• value: the data
• next: a reference to the next node

Unlike arrays, linked lists do not give you instant access to “index 5.” To find something, you start at head and follow next links.

That means linked lists are strong when you already have the position and need to reconnect nodes, but weaker when you need frequent random access.

A tiny linked list in JavaScript

JavaScript does not have a built-in linked list type, but we can build one with objects.

The key idea is simple: each node knows only its own value and where the next node is.

Below, append walks to the end of the list and attaches a new node. The toArray helper is just for readable output.

```javascript
class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  append(value) {
    const newNode = new ListNode(value);

    if (this.head === null) {
      this.head = newNode;
      return;
    }

    let current = this.head;
    while (current.next !== null) {
      current = current.next;
    }
    current.next = newNode;
  }

  toArray() {
    const result = [];
    let current = this.head;

    while (current !== null) {
      result.push(current.value);
      current = current.next;
    }

    return result;
  }
}

const list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);

console.log(list.toArray());
```

True or false: In a singly linked list, accessing the 10th element is always O(1) because nodes are connected by next references.

Arrays vs linked lists

Neither structure is “better” in every situation. The better choice depends on the operations your problem performs most often.

Need Array Linked List Access by index Excellent Weak Append at end Usually excellent Good if tail is tracked Insert/remove at front Costly Excellent Search by value Linear Linear Memory simplicity Compact mental model Extra references

A useful interview habit: before coding, name the dominant operation.

• “I keep reading by index” → array is likely natural
• “I keep removing from the front” → linked list may fit
• “I need both ends” → that idea will return when we study Stacks and Queues next

Fill in the blank.

In JavaScript, the array method that removes the first element and shifts the remaining elements left is:

arr.____()

Traversal is the linked list superpower

Most linked list problems begin the same way:

1. Start at head
2. Keep a current pointer
3. Move with current = current.next
4. Stop when current === null

This pattern is small, but it powers many medium-level linked list tasks: searching, counting, deleting, merging, and detecting structure.

Here is a standalone search example.

```javascript
function contains(head, target) {
  let current = head;

  while (current !== null) {
    if (current.value === target) {
      return true;
    }
    current = current.next;
  }

  return false;
}

const head = {
  value: "A",
  next: {
    value: "B",
    next: {
      value: "C",
      next: null
    }
  }
};

console.log("Contains B?", contains(head, "B"));
console.log("Contains Z?", contains(head, "Z"));
```

What to remember

You now have two core sequence structures in your toolkit.

Arrays

• Best when you need indexed access
• Great for compact ordered data
• Front insertions/removals can be expensive

Linked lists

• Best when you mostly traverse and reconnect nodes
• No instant index access
• Built from references rather than contiguous indexed slots

The big lesson is not memorizing operations in isolation. It is matching the structure to the behavior of the problem.

Next, we’ll build on this sequence thinking with Stacks and Queues, where access is intentionally restricted to make certain workflows simpler.