Array vs Linked List [When to use What]

Wondering when to use what Array vs. Linked list? Discover key differences between arrays and linked lists and learn when to use each data structure effectively.  

Linked lists and arrays are two of the most basic data structures in the field of computing. Understanding when to utilize one over the other can significantly improve the effectiveness of your code.

Arrays and linked lists are two of the most commonly used data structures in programming. Both perform the same function of storing data in the memory but they go about it in different ways, and that’s why they’re used for various purposes. There are cases when using an array data structure makes more sense, and vice versa.

The biggest difference between them is the way they store data- Array uses contiguous memory locations while elements can be stored anywhere in the case of linked lists. Every sort of data structure has advantages and disadvantages. For these reasons, it's important to understand the benefits and drawbacks of various data structures while creating, refining, and growing programs.

In this article, we’ll talk about more such differences between arrays and linked lists and figure out what works where.

First, let’s understand them one by one.

Array

Arrays are one of the most fundamental and important data structures in computer programming.

A collection of data components or data objects kept in contiguous memory is known as an array. One of the most basic data structures is an array, where we can quickly retrieve a data element by utilizing simply its index number.

They store elements of the same data type in contiguous memory locations.

Arrays can be either a linear sequence of objects like chairs in a row or a rectangular arrangement of objects in rows and columns, like a chessboard.

Focus on the ‘same data type’ part because if you try to store values of different types in an array, it will throw a compile-time error.  

Arrays make good use of computer addressing logic because the memory in most modern computers and external storage devices is in the form of a one-dimensional array of words.

One huge advantage of an array is that it allows you to randomly access any element by using its index. As a result, the time complexity to access any element in an array is constant, unlike stacks, where we need to start from the top to get the bottom elements.

Linked List

A linked list is a type of data structure in which elements are linked to one another using pointers. Each element (called a node) consists of two parts: data and a link to the next node.

Each entry in a linked list, which is a linear, non-primitive data structure where each element points to the next, gets assigned periodically. It is a data structure made up of a collection of nodes that simultaneously represent a sequence, in other words.

The interesting thing about a linked list is that the elements can be placed anywhere in the list and still be connected to another element in a faraway position. This is because one element carries an address to the other element, instead of necessarily being placed in contiguous locations.

A linked list can be visualized as a chain of nodes, with each node containing a data field and a reference link to the next node in the list.

The first node in the series is referred to as the 'Head.' And the last node can be identified as the one that points to 'Null.'

As it maintains the order of the elements using reference links, we can easily insert or remove elements from random positions by changing the reference links. This is in contrast with arrays where insertion and deletion are rather difficult. (We’ll get to that later)

Linked lists can be of different types as well, such that:

• Singly linked list
• Doubly linked list
• Circular linked list
• Doubly circular linked list

(Refer to this article to know about all the types and their various applications)

For now, we’ll get to the bout between arrays and linked lists:

Array vs Linked List

Round 1: Accessing an element

Let’s say we have an array arr[8] containing 8 elements. As indexing in an array starts with 0, we denote the first element as arr[0]. So, the ‘nth element in an array will be indexed as arr[n-1].

If we want to access the 7th element, we’ll simply use arr[6] and we’ll get the desired output. The same process goes for every other element.

Here we can see that accessing any element in an array is easy, and will have a 0(1) time complexity.

Whereas accessing a node in a linked list is quite complicated, as they’re not in contiguous locations. There’s not a series of addresses, instead, there are multiple nodes that contain the pointers to the other nodes. We don’t really know which node has the reference to the node we want to access.

Let’s say we have determined the first node aka the head node. Now for the second node, we have to traverse from the first node. In the case of the 5th node, any of the last 4 nodes can be containing the pointers and so we’ll need to traverse through all 4 nodes. In the worst-case scenario, to get the last node, we’ll have to traverse all the nodes. That’ll result in a poor time complexity of 0(n).

Here’s the process of searching for an element on a linked list:

Assume we need to locate Node X in a linked list-

• First, we will make the 'Head' node the 'Current' node.
• Then, because the last element points to 'Null,' we'll use a loop until the 'Current' node is 'Null.'
• In each repetition, we'll see if the node's key equals 'Node X.' Return true if the key matches this item; otherwise, return false.

Clearly, accessing an element in an array is much easier and bears much lesser cost than in a linked list. If the requirement involves accessing elements, arrays can be a better and optimized choice.

Round 2: Inserting an element

Let’s say we have to insert a new element at the beginning of an array i.e. arr[0]. In that case, we’ll have to shift all the elements from one place to the right. So, the element which was in the 2nd position i.e. arr[1] will be now in the 3rd position, and so on. The time complexity will be proportional to the size of the array, assuming it’s of ‘n’ size, the time complexity will be 0(n). A true headache, don’t you think?

Even if we insert an element somewhere in the middle of the array, we’ll need to shift all the (n/2) elements to the right resulting again in a 0(n) time complexity.

Only if the array is not full and we have to insert an element at the end, we’ll get a time constant time complexity of 0(1). But only if the array is not full.

Insertion is not so much of a problem in the case of a linked list though. In the instance of a linked list, we will construct a new node and add the address of the first node to the new node to insert an element at the beginning of the linked list.

As a result, the new node becomes the first node. So, the temporal complexity is not proportional to the length of the list. The time complexity would remain constant (1).

Ease of Use

In comparison to the linked list, the implementation of an array is simple. When using a linked list to create a program, the program is more prone to mistakes such as segmentation faults and memory leaks. As a result, great care must be given when creating a program in the linked list.

Round 3: Memory Requirements

Memory allocation is one of the major differences between an array and a linked list. Arrays have a pre-defined size i.e. a fixed size is allocated while creating an array (except in dynamic arrays where size can be expended dynamically).

Let's say you are creating an application that will request input from users and then store that input in an array. You create an array with one million indexes presuming that will be sufficient for a user. But, what happens if the user only enters 100,000 entries into the array? The remaining 90% of the space is wasted.

Whereas, memory is allocated at run-time in the case of a linked list. It allows the list to increase or decrease in size as the program runs as the pointers keep getting updated depending on the insertion and deletion of elements. As a result, there's no such risk of memory wastage.

That being said, a linked list uses more memory than an array for the same number of elements as the reference pointers to the next node are stored with the data.

Let's understand this with an example:

If we have a 7-element array out of which only 4 slots are being used and the remaining space is unused, the memory occupied will be as follows:

7*4 Equals 28 bytes of memory space

Where 7 is the number of array members and 4 is the number of integer bytes each member occupies.

There is no unused memory in a linked list, but the extra memory is used by pointer variables.

If the data is of the integer type, the total memory occupied by one node is 8 bytes, which includes 4 bytes for data and 4 bytes for the pointer variable. If the linked list has four elements, the memory space occupied by the linked list is:

8*4 Equals 32 bytes of memory space

However, if the data component is huge or if there is uncertainty about the size, the linked list is a preferable option. Assume the data is 16 bytes long. The array takes up 16*7=112 bytes of memory space, whereas the linked list takes up 20*4=80, where we have defined 20 bytes as 16 bytes for data size plus 4 bytes for the pointer variable. If we select the bigger data size, then the linked list will consume less memory; otherwise, it relies on the parameters we use to decide the size.

Let's study the differences between the array and linked list in a table format.

Wrapping Up

• A linked list is a linear data structure with nodes chained together, however, those nodes may not be allocated in memory sequentially.
• A data structure that holds data components of the same data type in contiguous memory regions is known as an array.
• The main distinction between an array and a linked list is that an array has a definite size that must be declared beforehand, whereas a linked list is not limited to size, expansion, and contraction during execution.
• As a result, the primary distinction between the array and the linked list is in the storage schema, which allows the user to determine which data structure is best suited to a given problem.

Hope you've understood the differences clearly and can visualize the situations where arrays can be a better option and vice versa.

Here are a few more resources for you-

Array Data Structure- Explained with Examples

Linked List- Explained with Examples

Data Structures & Algorithms