There Are Only 2 Real Data Structures

Aden Huen
4 min readDec 28, 2023

--

Data structures at their core are simply ways to store and manipulate data in a computer. It provides a framework to organise the 1s and 0s into something humans can understand. In this issue, we’re going to explore how data is stored and the 2 fundamental data structures that are needed to build the rest — the array and the linked list.

What is a Data structure?

Systems nowadays are usually 32 or 64-bit, meaning there are 32–64 individual 1s and 0s to represent each character. For simplicity in this article, we’ll call each group of 32/64 bits a memory cell.

The word ‘Bytespring’ spelled out in memory cells

To access a stored character, we’ll need a reference to their address in physical memory. This is a very fast process because the computer knows exactly where to go to find the data.

Accessing data from a known address is a very fast process

Unfortunately, individual memory cells are quite limited in storage, and to reference anything bigger, we’ll need to group these cells together. Data structures are these memory cells stored together in a particular order so that they can solve real-world problems.

Contiguous Memory

The easiest way to solve the storage problem is to have the neighbouring cells also be part of our data (so the computer can access them as a group). This allows us to store lists of numbers, characters or objects and is what we would conventionally call an array.

Accessing data from an address and its neighbours is also very fast!

Access is incredibly fast on any element in the list, as the computer knows how far along the address is from the reference point. This is why in code, when we want to get an element from an array, we also pass in the offset from that memory address.

Note: In this example the computer does some smarts with variable-length elements, it knows the length of each element in order to skip them in memory eg. at index 3 the computer skips over ‘pizza’ jumping 5 cells, then ‘garlic bread’ jumping 12!

However inserting and removing elements from an array can be an issue, as it takes many operations to make room or fill the hole made when inserting and deleting elements.

Inserting and removing requires all subsequent elements to move as well!

In the same vein if you are running out of memory, extending an array can be difficult as it requires all cells to be next to each other!
The only way to do this is to copy the entire array into a new area with a larger size.

Arrays require memory cells to be next to each other, which can be a problem if you don’t have enough space!

Arrays are very beneficial when needing to access and navigate memory cells due to their simple structure and isolated memory blocks. However more work is required when creating or modifying the array, due to the need for contiguous memory. That is the trade-off we make for exceptional read performance.

Non-Contiguous Memory

The other way to store data is by associating the next memory address after every element so that we always know where the next cell is. This similarly allows us to store lists of elements but with different characteristics for access and modification. We call this data structure the linked list.

Linked lists can fit their elements into computer memory more easily than arrays

This data structure allows memory to be stored in smaller chunks around the neighbourhood. Accessing a specific element in a linked list is a little harder, as we still only have a reference to the starting element. A computer has to crawl through each element from the start until it finds the element it is looking for.

The benefit of this structure is that adding and removing elements is very easy once you have an element, as you can simply change where the memory addresses point to.

Linked lists perform much better when inserting and removing elements

Similarly, if we need to extend the length of our linked list we can do so without much issue - just add a reference to the new memory address at the end of the list! As linked lists don’t require a large set of contiguous memory to be set aside, there is never a need to copy arrays or rejig elements to maintain the data structure.

Building on top of these data structures

Data structures are simply ways we organise and store data, you may have seen other structures such as stacks, queues, dictionaries and trees. Under the hood, they are all combinations and specific implementations of arrays and linked lists.

I encourage you to imagine how this is possible. Can you recognise how other data structures implement themselves with only arrays and linked lists?

All other data structures are made with just arrays and linked lists!

I hope you enjoyed this article, if you have any questions or comments please leave it below and follow to see more content like this.

--

--

Aden Huen
Aden Huen

Written by Aden Huen

A software engineer passionate about all things software development!

Responses (1)