A World Without Linked Lists

To get a sense of how important Linked Lists are, it might be useful to imagine a world without Linked Lists.

Suppose we want to build a Stack. A Stack is a collection of objects in a sequence, where the last object added is also the first object removed. The common term is “Last in, first out”, or “LIFO.”

A commonly used real-world example for a Stack is a stack of pancakes. When pancakes are placed on top of each other, the last pancake added is the one on the very top. This very top pancake is also the first to be eaten.

How would we implement a Stack without using Linked Lists ?

Let’s say we are allowed to use an Array to implement our Stack. How big should our array be at the start ?

By its definition, a Stack implies that its size varies with the addition or removal of objects. What if our Stack outgrows our initial Array size ?

If we are able to solve the problem of our Stack outgrowing our Array size, what then if our Stack eventually shrinks significantly ? Would we have hold a large number of empty elements in our Array ?

With some thought, we are able to implement our Stack using just an Array. Here is one implementation:

The main takeaway is that we double the array size whenever we reach our limit, and we shrink to a quarter whenever half of the array is empty (we shrink to a quarter instead of a half so that we aren’t teetering on the edge of doubling or shrinking the array with a single add or drop in the stack). In expanding or reducing the array, we make use of the “resize” method, which makes a copy of the entire array, temporarily doubling the space cost.

Let’s look at another collection of objects – a queue. A Queue is “First in, first out”, or “FIFO”. A queue in the real world could be people lining up to see a movie. The first person in line is also the first person to get into the theater.

We run across the same sizing questions as the Stack – and can handle them similarly.

In the Stack implementation, the last element of the Array was always the element being popped, and the element being pushed was always added at the end of the Array. For a Queue, we need to keep the position of the “head” and “tail” of the queue. If the beginning element of the array is removed when we “dequeue”, what do we do with the empty elements at the beginning of the array as we continue to dequeue ?

Here is one implementation of a Queue using Arrays:

We have to be more careful with our tail and head position of the array. Whenever we resize our array or whenever our head position reaches our tail position, we shift our head position back to the beginning of the array. The length of our queue is determined by our head position less our tail position. After these differences, we handle our sizing decisions are similar to our Stack implementation.

Boy – that’s a lot of resizing and keeping track of positions! A world without Linked Lists is tough!
Can Linked Lists make things easier ? What are Linked Lists ?

Leave a Reply