In this tutorial, we will focus on the differences between two linear data structures: linked lists and arrays. We will discuss different parameters that will show us the usefulness of one data structure than the other. These include accessing an element, memory requirements, inserting an element, and finally the ease of use. So let’s get started.
In order to properly assess the two data structures let us discuss some factors. The most frequent operation that we want to perform with each of the data structures or the size of the data plays a huge part in choosing which data structure to choose. This guide will be useful for users who want to determine when to use a linked list data structure and when to use an array.
Difference Between Linked List and Arrays
Note: In this guide when talking about arrays we mean fixed-sized arrays and not dynamic arrays.
Now let’s discuss some important points to see differences between Linked lists and arrays.
Accessing an Element in Linked Lists vs Arrays
The first parameter that we will analyze for both the data structures will be the time complexity of accessing an element.
In an array, it takes a constant time to access an element regardless of its size. This is due to the reason that array is stored as one contiguous block of memory. If we know the starting address (base address) of this block of memory we will be easily able to access an element of that array.
For example, let us have an integer array num of size 5 with the following values stored in it.
For example, purposes let us assume the starting address of ‘num’ is ‘100.’ As we know byte in the system’s memory has an address and if we assume that an integer is stored in 4 bytes in a typical compiler then the block of four bytes at starting address 100 will be num. Block of 4 bytes at starting address 104 will be num. The next block of 4 bytes at starting address 108 will be num and so on.
If we want to find the address of element at index i i.e. address of num[i] then it will be equal to 100+i*size of an integer in bytes. Therefore it will be 100+4i. If we want to calculate the address of the element at index 3 it will be 100+4*3 = 100+12 = 112. This is the only calculation that is required to find the address of any element in an array.
In terms of Big O notation, constant time is known as O(1). In terms of time complexity, accessing an element in an array is O(1).
In a Linked List, data is stored in a non-contiguous block of memory. A linked list of integers as shown below has multiple blocks of memory at different addresses.
Each block in the linked list is called a node. Each node has two fields: one to store the data and another to store the address of the next node. The address of the first node (HEAD) is the vital information that is needed regarding the linked list. This is passed to all the functions as well.
To access an element in the linked list at a particular position, we first need to start at the HEAD node. While traversing the linked list, at the first node we obtain the address of the second node and then we go to the second node we obtain the address of the third node and so on.
The worst case scenario while accessing an element will be if it is the last element in the list. Therefore we would have to traverse all the nodes in the list.
In the average case, we will be accessing the middle element. If the size of the linked list is ‘n’ where ‘n’ is the number of elements in the list then we will traverse n/2 elements. The time taken in the average case will also be proportional to the number of elements in the linked list which will be O(n).
Therefore if we analyze this parameter of the cost induced while accessing an element, arrays perform far better than linked lists.
Memory Requirement in Linked Lists vs Arrays
The second parameter that we will analyze for both the data structures will be the memory required while using these data structures.
When creating a fixed array the first important thing is the size. The reason for this is an array is created as one contiguous block of memory and has a fixed size unless created dynamically. We often create an array large enough where one part of the array stores our list and the other part is empty. The unused part can later be used to add more elements to the list.
For example we create an array of size 5 but have only 3 integers in the list. The rest of the two positions are un used. There would be some garbage values present there. This is shown in the array below.
Now as we already know that in a typical architecture the integer is stored in 4 bytes. Therefore, the memory requirement for these five integers in the array will be 5*4 = 20 bytes.
When creating a Linked list there is no un used memory. This is because memory is requested for one node at a time so we do not not keep any reserved space. However, apart from the data, a node also contains a pointer to the next node. This causes extra memory usage for pointer variables. This extra memory requirement for pointer variables in a linked list can not be ignored soo easily.
To store the three same integers which we did in the array above, we will require only three nodes and no extra memory reservation for the linked list.
In a typical architecture, integer is stored in 4 bytes and the pointer variable is also stored in 4 bytes which combines to a total of 8 bytes for one node. Therefore, the memory requirement for these three nodes in a linked list will be 3*8 = 24 bytes. It is a bit more as compared to the memory required when defining an array of 5 integers which was 20 bytes only.
However, this all depends on the size of the data. Previously, we were considering integer data types which take only 4 bytes of memory per integer. Let us show you what happens if the data is particularly large. If we have a linked list in which the data part is a complex type that takes for example 16 bytes. Then 4 bytes will be allocated for the pointer field and 16 for the data field which will combine to a total of 20 bytes for a single node. The total memory required for the linked list will be 3*20 = 60 bytes.
In the case of an array, the memory required will be 5*16 = 80 bytes. Therefore using a linked list if the data is large in size in advantageous.
It all depends if the data takes a lot of memory then a linked list will definitely consume a lot less memory than an array. Otherwise, it all depends on the size of the array and how much of it is unused.
As we have seen before when creating an array, one contiguous block of memory is assigned to it. Consider the case if we want to create a very large array and we do not have memory available as a single large block. If we are using a linked list instead, the memory may be available as multiple small blocks. There will be a problem of fragmentation in memory. Arrays have a fixed size, and once the array gets filled and we need more memory then there is no other option than to create a new larger array and copy the contents from the previous array into the new array. This issue is not present when working with Linked Lists.
Inserting an Element in Linked Lists vs Arrays
The third parameter that we will analyze for both the data structures will be the time complexity of inserting an element.
For insertion there can be three scenarios: inserting an element at the beginning of the list, inserting an element at the end of the list, and inserting an element at ith position.
Inserting an element at the beginning
- In the case of an array, we will have to shift each element by one position towards the higher index. The time taken will be proportional to the size of the list. It will be O(n) where n is the size of the list.
- In the case of a linked list, inserting an element in the beginning does not involve any shifting. We will only create a new node and adjust the head pointer and the link of this new node. Therefore the time taken will not depend upon the size of the list. It will be constant. In terms of Big O notation, it will be O(1).
Inserting an element at the end
- While inserting an element at the end of an array we have to first see whether the array has some unused space or not. If there is space in the array we insert the element at the next higher index of the list. So it will be constant time O(1). If however the array is full, we will have to create a new array and copy all the previous contents to the new array. This will take O(n) time where n is the size of the list.
- In the case of linked list, adding an element at the end of the list will mean traversing the whole list and then creating a new node and adjusting the links. So time taken will be proportional to n. In terms of time complexity it will be O(n).
Inserting an element at the i-th position
- In the case of the array we will have to shift the elements. For the average case we may want to insert at the middle position in the array so we will have to shift n/2 elements where n is the number of elements in the list. So the time taken will be proportional to n in average case. In terms of time complexity it will be O(n).
- For linked list we will also have to traverse to that position and then we will adjust the links. Even though we will not have any shifting we will still have to traverse till that point. In the average case time taken will be proportional to n. In terms of time complexity it will be O(n).
The same scenarios will be applicable for the case of deleting an element from the list. They will therefore have the same time complexities for both the data structures as was in the case of insertion.
|Insertion/Deletion at the start||O(n)||O(1)|
|Insertion/Deletion at the end||O(1) if space available|
O(n) if space unavailable
|Insertion/Deletion at the ith position||O(n)||O(n)|
Implementation in Linked Lists vs Arrays
An array is easier to use as compared to linked lists. Linked list implementation in C/C++ programming is more prone to errors like segmentation fault and memory leak. It takes good care to work with a linked list.