What are the advantages of array over linked list

A linked list is appropriate for many use cases independent of performance considerations. In addition to examples given by other answers here, consider that a given object (an instance) can be in more than one linked list (internally linked as well as externally linked) but can only be in one array (it can be pointed to by multiple arrays, but that's not the same, for many use cases).

Consider these diagrams from the book The Design Of An Optimizing Compiler (Wulf, Johnsson, Weinstock, Hobbs) (1973) - first is the multiply-internally-linked symbol table, second is the multiply-internally-linked "graph table" used for recognizing common subexpressions - the "threads" are multiple semantically different, semantically important traversals of the same data structure implemented by separate linked lists into the same objects each representing a symbol or a syntax tree node.

BTW, IMO it is a design mistake to consider performance of a data structure before considering appropriateness. But I can see that it frequently happens, probably because of the way CS/programming is taught, in many cases by teachers and textbooks, in which performance characteristics are prioritized over appropriateness, and in fact, appropriateness is given short shrift. See for example many industry "interview questions" which are considered properly answered by discussions of O-bounded performance, where the data structure to use is just assumed to be "obvious". Or in many many examples in textbooks, websites, and language libraries that have good support for external data structures (linked lists, arrays, dictionaries, hash tables) and never mention at all much less support internally linked data structures as used above. (Note that as in the diagrams above hash tables and trees can be represented using internal links if that is appropriate - it's just never done anymore not because it is wrong by mainly because there's no language or library support.)

If you're implementing a pure stack (where you only ever access the first item), or a pure queue (where you only access the first or last), then you have O(1) access regardless of whether you've implemented it as an array or a linked list

As you mentioned, using an array has the disadvantage of having to resize when the data structure grows beyond what you've already allocated. However, you can reduce the frequency of resizing by always doubling the size. If you initially allocate enough space to handle your typical stack size, then resizing is infrequent, and in most cases one resize operation will be sufficient. And if you're worried about having too much memory allocated, you can always add some logic that will reduce the size if the amount of memory allocated far exceeds the number of items in the data structure.

Linked lists have definite benefits, but each addition to the linked list requires an allocation (and removal, a deallocation), which takes some time and also can lead to heap fragmentation. In addition, each linked list node has a next pointer, making the amount of memory per item more than what would be required for an array. Finally, each individual allocation has some memory overhead. All in all, a linked list of n items will occupy more memory than an array of n items.

So there are benefits and drawbacks of each approach. I won't say that either can be considered "best," but there are very good reasons to implement these data structures with arrays rather than linked lists. Correctly implemented, an array-based stack or queue can be faster and more memory efficient than a linked list implementation.

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…

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:

Array – singly linked list – 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).

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":

Accessing a specific element in an array ("random access")

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":

Accessing a specific element of a linked list ("random access")

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.

Inserting an element into a linked list: O(1)

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:

Inserting an element into an array: O(n)

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.

Determining Size

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:

Operation	Array	Linked List
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.

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:

Memory consumption of an int array: 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.

Memory consumption of a single linked list in Java: 24 bytes per 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.

Memory consumption of a doubly linked list in Java: 24 bytes per node

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.

Memory Efficiency

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.

Array vs. linked list: memory efficiency

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.

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.

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.

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.

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.