Arrays vs Linked Lists : A Complete Guide

Which one should you use?

6 min readMay 1, 2024

Introduction
What is an Array Really?
What is a Linked List?
Summary

Introduction

Arrays and Linked Lists are one of the first data structures that any programmer learns. They are fundamental to any algorithm or system.

In this article, I will explore each of these data structures and discuss the differences in their usage. However, for the lazier readers, while I do encourage you to read the whole article, here is a quick spoiler.

When to use arrays and linked lists

Arrays are preferred when quick access to elements by index is needed. Additionally, if memory is a concern, an array should be then used.
Linked Lists are preferred when frequent insertions and deletions are performed. Similarly, if the number of elements change dynamically (not constant), then using a linked list would be the wiser choice.

Now, hopefully, you have decided to continue reading and ingest extra knowledge so next, I will discuss how arrays and linked lists are structured.

What is an Array Really?

An array is a data structure that is used to store elements in contiguous memory locations. What this essentially means, is that each element is stored in a memory location adjacent to one another. Additionally, the size of an array is unchangeable and is declared beforehand. This can be conceptualised easily with the below illustration.

This is an example of an array of size 6 with each box corresponding to adjacent memory locations. As you can see, the array was initially declared to have size 6, but only indexes 0–4 are occupied. However, while index 5 is empty and has no value, is it still reserved in memory address 105. This offers several advantages and disadvantages, which will be discussed below.

Access

When accessing an element, arrays are extremely efficient and take constant time O(1).

This is due to the sequential nature of each memory location. For example, let’s say we want to retrieve the element at index 4. Then using the base address of the array (the memory address of the first element), we can deduce the memory address of the index with just simple arithmetic.

Sequential memory allows for highly efficient element access in arrays. This is something linked lists fail to achieve, but we will get to that later.

Insertion

Inserting an element into an array uses an average time complexity of O(n).

This is because, if an element is inserted at the beginning of an array, the whole array must shift to the right one space resulting in a worst time complexity of O(n).

However, if we wanted to add the element 5 to the end of the array then it would be easy as no elements would have to be shifted resulting in a best time complexity of O(1).

This is just a very special case, however, as in reality, elements will be inserted at all places, the mean index being 0.5n. Therefore, it is accurate to conclude that the number of elements that require shifting will be proportional to n resulting in a total average time complexity of O(n).

Array Memory Efficiency

Arrays are fairly memory efficient when it comes to storing data. However, since the size of the array must be declared, the possibility of over-sizing looms.

Take for example our previous example.

In this array of size 6, only 5 memory addresses are being usefully used, the last memory address 105 serves as a waste of space. These type of occurrences are common with arrays especially when handling dynamic data and is an issue that does not occur with linked lists.

Let’s do some maths.

Later on we will see how this compares with the memory of linked lists.

What is a Linked List?

Unlike arrays, linked lists do not store elements in contiguous memory locations, but instead uses pointers to store the memory address of the next element. The linked list is built from 4 fundamental characteristics.

Head: A pointer that stores the memory address of the first element.
Data: This stores the value of the element.
Link/Next: A pointer to the memory address of the next element.
Node: This is the collective name of the data and link.

In this example, I have represented the elements from the array example in a linked list structure.

To explain what’s going on.

First the head points to the memory address of the first node. This node contains the data value and the link, which is a pointer for next node.
The proceeding node holds the data value of the second element as well as the link that points to the memory address of the third node.
This continues until the last node.
At the last node, since there are no more proceeding nodes, the link points to null.

By using the linked list data structure, various pros and cons arise. One upside being faster insertion and deletion. Let’s dive into more detail.

Access

Due to the contiguous nature or arrays, access is very fast. However, with linked lists, the memory address of a given index cannot be known with simple arithmetic.

In order to access an element, the computer must follow the pointer at each node starting from the head pointer until it has reached the desired index. Hence, access is directly proportional to the size of the linked list.

The best time complexity would be a constant time O(1) if the beginning elements were being accessed and the worst time complexity would be O(n) when accessing the final elements of the linked list. Overall, the average time complexity is O(n) as the average index being accessed is n/2.

Insertion

Inserting an element into a linked list is more efficient that in arrays and requires less manoeuvring. This can be attributed to their pointer format.

When inserting a new element into a linked lists, the pointer of the previous node must change to the address of the newly added node. However, to get to that position, you must first traverse the linked list until the desired index of insertion, therefore, taking an O(n) average time.

In this example, a new node is being inserted into the middle of the linked list. As you can see, the pointer of the previous node changed to acquaint the new node.

Similarly, if a new node is inserted at the beginning of the linked list, then the head pointer will be replaced in order to point to the memory address of the new starting node. This results in a best time complexity of O(1).

Linked List Memory Efficiency

While arrays solely need to store the data values, linked lists must store not only the data values but also the memory addresses stored in each pointer. This increases overall memory usage, however, unlike in arrays, all memory is useful since size is dynamic, there is never unused memory.

Let’s do some maths.

In a 4-element linked list, there are 5 pointers including the head pointer and then 4 data values. This results in a usage of 56 bytes for a 64-bit computer or 36 bytes for a 32-bit system.

Summary

To summarise, I have created a table that nicely compares each data structure over various metrics. By understanding the pros and cons of each data structure, you should be able to make a sensible and informed decision on which data structure is most suitable for your requirements.