Arrays and linked lists are data structures that sequentially arrange elements of a particular type.
However, there are mayor differences, and depending on the requirements, the choice of data structure significantly impacts the memory requirements and performance of the application.
This article answers the following questions:
- What are the differences between array and linked list?
- What are the advantages and disadvantages of one data structure over the other?
- What is the time complexity of the different operations (such as accessing an element, inserting, removing, and determining the size)?
- When should you use which data structure?
Let’s start with a comparison of both data structures…
Difference between Array and Linked List
The following image shows the basic layout of both data structures. I’ve included the linked list as both a singly and doubly linked list:
An array is a contiguous block of memory that directly contains the data elements¹.
A linked list consists of list nodes, each containing a data element¹ and a reference to the next node (and – in the case of a doubly linked list – to the previous node).
The following sections compare the consequences of the layout of the two data structures in terms of the time required to insert and remove elements, the memory required, and the principle of locality (I'll explain what this means in the corresponding section).
¹ A data element can be a primitive element, such as an
char – or a reference to an object.
Array vs. Linked List: Time Complexity
Let's start with the cost of the various operations.
(You can find an introduction to time complexity in the article "Big O Notation and Time Complexity – Easily Explained".)
Accessing a Specific Element ("Random Access")
With an array, we can address each element directly. In terms of effort, it makes no difference how long the array is or at which position we read or write an element.
In the array example, it makes no difference whether we access the "a" or the "p":
The time required is therefore constant. Thus, the time complexity for accessing (writing or reading) a particular element of an array is: O(1)
In a linked list, in contrast, we can only access the first element directly. For all others, we have to follow the list node by node until we reach the desired element.
In the linked list example, we need more steps to reach the "p" than to get to the "a":
With randomly distributed access to the elements, the average cost is proportional to the length of the list. The time complexity is, therefore: O(n)
Adding or Removing an Element
In a linked list, we can insert and remove nodes at any position. The cost is always the same, regardless of how long the list is and at which location we insert.
Thus, the time complexity for inserting into and removing from a linked list is: O(1)
An array cannot change its size. To insert or remove an element, we always have to copy the array into a new, larger or smaller array:
The time required is proportional to the array length. The time complexity is, therefore: O(n)
Data structures such as Java's ArrayList have a strategy for reducing the average time complexity of inserting and removing elements: By reserving space in the array for new elements, both when creating and when expanding, they can reduce the time complexity – at least for insertion and removal at the end of an array-based data structure – to O(1).
With a circular array, we can also reduce the time complexity for insertion and removal at the beginning of an array-based data structure to O(1). That is how the Java ArrayDeque is implemented, for example.
The size of an array is known and can be queried, for example, in Java via array.length. The effort for this is independent of the length of the array, so it is constant.
Thus, the time complexity for determining the length of an array is: O(1)
In the case of a linked list, we have to run through the entire list and count the list nodes. The longer the list, the longer the counting takes.
Thus, the time complexity for determining the length of a linked list is: O(n)
Some data structures based on linked lists (e.g., the Java LinkedList) additionally store the size in a field, which they update on insertion and removal. Therefore, we can query the size of such data structures in constant time, i.e., O(1).
Time Complexity Overview
The following table summarizes the time complexities of the various operations:
|Accessing the nth element:||O(1)||O(n)|
|Inserting an element:||O(n)||O(1)|
|Removing an element:||O(n)||O(1)|
|Determining the size:||O(1)||O(n)|
Thus, accessing an element (reading or writing) and determining length is cheaper with an array – inserting and removing, on the other hand, with a linked list.
Array vs. Linked List: Memory Consumption
In an array, each field requires as much memory as the data type it contains. For example, an array of
int primitives requires 4 bytes per entry:
In a linked list, we must store both the data element and references to each node’s successor (and possibly predecessor) nodes.
If we stay with the int primitives and assume 4 bytes per reference, we reach 8 bytes per element for a singly linked list.
In JVM languages, however, 12 bytes are added per node for the header of the node object – plus 4 fill bytes since objects must occupy a multiple of 8 bytes of memory.¹ Thus, we need a total of 24 bytes per list node.
We need one more reference for a doubly linked list, so we end up with 12 bytes per entry.
For JVM-based languages, we add the 12 bytes for the object header. However, the total remains at 24 bytes since the additional four bytes can use the space previously occupied by the fill bytes.
For JVM-based languages, we add the 12 bytes for the object header. However, the total remains at 24 bytes, since the additional four bytes take up the space previously occupied by the fill bytes.
The following table shows the memory requirements per field for an array and a linked list – each for C/C++ and JVM-based languages:
|Language||Array||Singly linked list||Doubly linked list|
|C/C++:||4 bytes||8 bytes||12 bytes|
|JVM language:||4 bytes||24 bytes¹||24 bytes¹|
Up to this point, the memory consumption speaks for the array – especially in Java.
(¹ For the memory considerations, I'm assuming a 64-bit JVM with Compressed Oops nabled.)
However, the comparison is that clear only if we know the size of the data structure in advance and it does not change.
Array-based data structures whose size can change, e.g., the Java
ArrayList, usually reserve additional array fields for new elements (as mentioned above). With a linked list, however, memory is allocated for each element separately only when an element is inserted.
The same applies to removing elements. In an array-based data structure, the removed field is usually left free for future insert operations. For a linked list, it gets immediately deleted (or released for deletion by the garbage collector).
Linked lists are thus more memory efficient than arrays.
In summary: for the same length, a linked list requires at least twice as much memory as an array – and even six times as much in Java! However, with varying lengths, an array-based data structure can block unused memory, so you must weigh these two factors against each other.
Array vs. Linked List: Locality
To answer the question "Which is faster – an array or a linked list?" we need to consider one more factor: the principle of locality.
Since the memory for an array is allocated in one piece, its elements are located at consecutive memory addresses. When accessing main memory, all array elements on the same memory page are loaded into the CPU cache simultaneously. Thus, once we have accessed one array element, we can access the neighboring elements very quickly.
The nodes of a linked list, in contrast, are allocated at arbitrary locations in memory, i.e., they can be distributed over the entire memory. When traversing a linked list, a new memory page would have to be loaded for each element in the worst case.
Advantages of Linked List over Array
In this and the next section, I’ll summarize the advantages and disadvantages of arrays and linked lists.
Why is a linked list better than an array?
- Elements can be inserted and removed with constant time.
- A linked list does not occupy any unused memory.
Advantages of Array over Linked List
And when is an array better than a linked list?
- We can access any array element ("random access") in constant time.
- We can traverse an array from back to front – this is not possible with a singly linked list, only with a doubly linked one.
- When containing the same number of elements, an array occupies significantly less memory than a linked list (C/C++: factor 2–3; Java: factor 6).
- Due to the principle of locality, we can access elements close to each other much faster in an array.
- The garbage collector can perform a reachability analysis much quicker on an array than on a linked list.
- Deleting an array frees a contiguous memory area, while deleting a linked list leaves fragmented memory.
Conclusion: When to Use an Array and When to Use a Linked List?
The question "Which data structure is better – array or linked list?" can, like so many things, only be answered with an “It depends”.
If elements are often inserted or removed in the middle of the data structure, then a linked list should be the better choice.
For all other use cases, array-based data structures generally deliver better performance and a better memory footprint and should therefore be preferred.
If you suspect that a linked list is better suited for your purpose, just try it out. Take measurements and make a decision based on the results.
If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.