Linked Structures

In the previous chapter we studied arrays.

Now we move to a different storage model where elements are connected by references.

---

The Core Idea

A linked structure is built from nodes.

Each node contains:

• a value
• a reference to the next node

In a singly linked list, each node points forward to one next node.

graph LR
  A[Node A] --> B[Node B] --> C[Node C] --> D[null]

---

Why Linked Structures Are Useful

Because nodes are connected by references rather than fixed positions:

• insertion can be efficient when you already have a pointer to the location
• deletion can also be efficient by relinking pointers

This is often better than shifting many array elements.

---

Traversal Behavior

The main tradeoff is access pattern.

To reach element k, you usually traverse step by step from the head.

So random access is slower than arrays.

---

Dynamic Memory Perspective

Linked structures are often associated with dynamic allocation.

Nodes can be created as needed, which offers flexibility for changing data sizes.

But this also introduces pointer management complexity.

---

When to Use Them

Linked structures are useful when:

• insertions/deletions happen frequently
• strict contiguous storage is not required
• sequential traversal is acceptable

They are less ideal when fast index-based lookup is critical.

---

Key Ideas to Remember

• Linked structures connect nodes through references.
• Singly linked lists support forward traversal.
• Insertions/deletions can be efficient with known pointers.
• Random indexing is typically slow compared to arrays.
• They trade direct access for structural flexibility.

---

What Comes Next

Linked structures teach pointer-based organization.

Next we focus on order-constrained structures used everywhere in systems:

stacks and queues.