Lesson 4: Array-Based Linked List Storage

A linked list can be represented using arrays. This approach is sometimes called an array implementation of a linked list or a cursor-based linked list.

Instead of using actual memory pointers, the structure uses indexes.

Key and Next Arrays

Two parallel arrays are commonly used:

A special index such as head marks the start of the list. Another special marker may represent the end of the list.

For example:

next[head] = 4
key[4] = "A"
next[4] = 3
key[3] = "L"

This means the first item after head is stored at index 4, and that item contains A. The next item is at index 3, containing L.

Why Use This Representation?

Array-based linked lists help students understand how links work without using actual pointer syntax. They also show that the logical order of a list does not need to match the physical order of values in storage.

Example: Reading an Array-Based List

Suppose the list uses these records:

Starting from HEAD, follow the next values:

HEAD -> A -> L -> I -> S -> TAIL

The list order is based on links, not on index order.

---