Linear Structures Implementation

Beyond the Basics

You know that arrays store data in a neat, contiguous block of memory. This is their superpower. Accessing any element is incredibly fast because the computer can calculate its exact address with simple arithmetic. An element's address is just (starting_address) + (index * element_size).

This physical layout makes arrays a great fit for how modern CPUs work. Processors don't fetch data from memory one byte at a time. Instead, they pull in larger chunks, called cache lines, and store them in a small, super-fast memory cache right on the chip. Because array elements are neighbors in memory, when you access one, you likely pull its neighbors into the cache for free. This phenomenon, known as cache locality, means subsequent accesses to nearby elements are almost instantaneous.

Arrays are fast because of their predictable, packed-together memory layout, which plays nicely with CPU caching.

But this strength is also a weakness. What happens when your array is full and you need to add one more item? You can't just stick it on the end if that memory spot is already taken. The solution is to create a dynamic array (often called a vector or ArrayList in programming languages). When it runs out of space, it performs a resizing operation.

A new, larger block of memory is allocated. A common strategy is to double the current capacity.
All elements from the old array are copied to the new one.
The old memory block is freed.

This sounds expensive. Copying every single element just to add one more seems horribly inefficient. And for that one specific add operation, it is. But most of the time, adding an element is a simple, fast operation. The expensive resizes happen so infrequently that the cost is spread out over many cheap additions.

Amortized

adjective

The average cost of an operation over a sequence of operations, rather than the worst-case cost of a single operation. It helps analyze algorithms where occasional expensive operations are offset by many cheap ones.

This concept is called amortized time complexity. If you average the cost of adding millions of elements, the final cost per addition is constant, or $O(1)$ . The expensive doublings become statistical noise. It's like your commute: most days it's 20 minutes, but one day a traffic jam makes it 90 minutes. You wouldn't say your commute is 90 minutes; you'd average it out.

Pointers and Chains

Linked lists take the opposite approach. They abandon contiguous memory entirely. Each element, or node, is a small, separate object containing two things: the data itself and a pointer (a memory address) to the next node in the sequence. The list is a chain of these nodes scattered across memory.

This structure completely solves the resizing problem. To add an element, you just create a new node anywhere in memory and update a couple of pointers. Deleting is just as easy. But this flexibility comes at a cost.

First, there's the memory overhead. Each node must store at least one pointer in addition to the actual data. In a doubly linked list, where each node points to both the next and the previous element, you store two pointers per node. If your data is small (like a single character), the pointers can take up significantly more space than the data itself.

Second, cache locality is gone. Since nodes can be anywhere in memory, traversing a linked list involves jumping from one random address to another. This is called pointer chasing, and it's a performance killer. Each jump is likely to cause a , forcing the CPU to wait for data to be fetched from slow main memory.

Feature	Dynamic Array	Linked List
Memory Layout	Contiguous	Scattered
Access (`get` index)	$O(1)$	$O(n)$
Insertion/Deletion	At end: $O(1)$ amortized. Middle: $O(n)$	Anywhere: $O(1)$ (if node is known)
Cache Locality	Excellent	Poor
Memory Overhead	Low (only for unused capacity)	High (1-2 pointers per element)

Taming Edge Cases

Implementing linked lists involves careful pointer management. Special logic is often needed for operations at the boundaries, like inserting at the head of the list or deleting the last element. The code to handle these edge cases can make the implementation messy.

A clever technique to simplify this is using (also called dummy nodes). A sentinel node is a placeholder node that is always present at the beginning (and sometimes the end) of the list. It doesn't hold any real data.

With a sentinel head node, the list is never truly "empty." The head pointer always points to the sentinel, whose next pointer points to the first real element. Now, inserting a new element at the front is no different from inserting one in the middle. You're always inserting after some existing node (the sentinel).

Consider deleting the last node in a list without a sentinel. You have to find the second-to-last node, change its next pointer to null, and handle the case where the list only has one element. With sentinels, every node, including the last one, has a non-null neighbor, unifying the logic.

// Deletion without a sentinel
if (head == nodeToDelete) {
    head = head.next; // Special case for head
} else {
    Node prev = findPrevious(nodeToDelete);
    prev.next = nodeToDelete.next; // General case
}

// Deletion with a sentinel
// No special cases needed!
Node prev = findPrevious(nodeToDelete); // This will always work
prev.next = nodeToDelete.next;

Choosing between an array and a linked list is a classic engineering trade-off. If you need fast, random access and can predict the size reasonably well, arrays are superior. If you need to perform frequent insertions and deletions in the middle of a large dataset, a linked list is often the better choice. Understanding their memory-level behavior is the key to making the right decision.

Time to test your knowledge on these core concepts.

Quiz Questions 1/6

What is the primary reason that accessing elements in an array is significantly faster than in a linked list?

Quiz Questions 2/6

The phenomenon where accessing an array element also loads adjacent elements into the CPU's fast memory is known as __________.

Understanding these low-level details is what separates a programmer who uses data structures from one who truly understands them.

Applied Data Structures and Algorithms