Data structures are formats implemented in computer programming to store, manage, and organize data items. These storage formats enable efficient access and modification of data elements. There are several data structures for organizing data in memory, but perhaps the most basic ones are array and linked list. Both these data structures store homogeneous elements in sequential order. However, there are a lot of differences between arrays and linked lists. So, in this tutorial, we will unleash a few key differences between these data structures.
What Is an Array?
An array is a data structure that stores elements of the same data type sequentially. This data structure can be considered as a large chunk of memory that is divided into small multiple blocks. These blocks can store a single value belonging to similar data types such as Integer, Float, Double, Character, etc.
For instance, if we create an array to store integer data elements with size 5, and we enforce elements of different data types instead of an integer. Then, we will end up getting a compile-time error because our insertions into the array are invalid. That will be further clear if we look at the syntax for the array declaration:
|
Data_type Array_Name[Size_of_an_Array]; |
To declare an array, we should first determine its data type and then its name. Following that, we need to indicate the size of an array inside the square brackets. Since we are directly allocating data type to this data structure, it will lead to an error once the elements with different data types are inserted.
What Is a Linked List?
A linked list is a set of nodes that are stored in random order (dynamic memory). Each node is made up of two fields: the data field and the reference field. The reference field is the pointer that stores the next node’s address, and the data field stores the value at a particular node. The linked list is a dynamic data structure that stores homogeneous data elements.
Every node in the linked list is created using the structure in the C programming language. The data element is stored in the data field, and the next is a pointer to the address of the next node.
|
struct Node{ int data; struct Node *next; }; |
Now, the next phase is allocating dynamic memory using the malloc() function in C programming.
|
newnode = (struct Node*)malloc(sizeof(struct Node)); |
Moving forward, let’s understand the difference between array and linked list.
Difference Between Array and Linked List
We can't say whether an array or a linked list is the better data structure. One data structure may be better for one form of requirement, whereas the other data structure may be good for another kind of requirement. Additionally, there are various factors to judge which data structure to choose for a particular requirement. So, continuing on, we'll investigate the difference between arrays and linked lists based on a few parameters.
1. Cost of Accessing an Element
- For an array, accessing an element takes constant time, regardless of its size. Since the items in an array are stored in a contiguous manner, we can quickly determine the address of any element in an array if we know the element's base address. To find the address of any element in an array, we will need to do a simple calculation. In terms of time complexity, accessing an array element costs O(1).
For example, in the image shown below, the base address is 200, and we need to find the address of ith element, i.e., i = 3.
Address of ith element = (Base address) + i * (memory space required)
A[3] = 200 + 3*(4) = 212 {integer size: four bytes}
- For a linked list, elements are not stored in an orderly fashion (non-contiguous memory allocation). The linked list is made up of multiple blocks dispersed in a pool of memory, and each of these nodes stores two fields; and the head node is the only locality that we keep with us while implementing the linked list. Hence, while accessing any element in the linked list, we will have to traverse from the head node. As a result, the average case for accessing an element in a linked list becomes O(n).
Therefore, we can conclude that the cost of accessing an element in an array is less than the linked list. So, whenever there is a need for quick access to elements, we can prefer an array over a linked list. The next parameter to find the difference between array and linked list is the cost of inserting an element.
2. Cost of Inserting an Element
There are three possibilities for inserting an element into either of these data structures, which we will go over one by one.
Inserting an Element at the Beginning
- To place the new element at the beginning of an array, we must first shift the existing element to the right to make room at the first position. As a result, the resulting time complexity becomes proportional to the size of the list. If n is the array size, the time complexity is O(n). The representation of insertion at the beginning of an array given below represents why this operation costs us O(n).
- In the context of a linked list, we will create a new node and add the address of the first node to the new node's reference field for inserting an element. As a result, the new node gets pushed to the position of the first node. Hence, the time complexity is not proportional to the list size. It would be constant, i.e., O(1). The linked list representation shown below represents the scenario of inserting elements at the beginning.
Inserting an Element at the End
- If the array is not yet filled, we can add the new element explicitly using the index. The time complexity would be constant in this scenario, i.e. O(1). If the array is already full, we must first replicate it and add a new element into another array. The time complexity in this situation would be O(n).
- For inserting an element at the end of the linked list, we must traverse the entire linked list. Suppose there are n elements in the linked list, then the time complexity for inserting an element becomes O(n).
Inserting an Element in Mid
- If we intend to put an element at the ith location in an array, we must shift the n/2 elements to the right of that location to make our ith location empty. Hence, the time complexity is proportional to the number of elements. For the average case, the time complexity would be O(n).
- In the case of linked lists, we have to traverse to the index where the new element has to be inserted. Although, in this case, we don't require any shifting of elements, we will get O(n) complexity because we will have to traverse n/2 elements to reach the mid location.
Moving forward, we will discover the cost of removing elements from both array and linked list to contemplate the next difference between array and linked list.
3. Cost of Removing an Element
The time complexity for removing elements from both array and the linked list is similar to the insertion scenario. The table given below compiles the time complexities for different deletion operations in the case of both array and linked list.
Operation |
Array |
Linked List |
|
Removal from the beginning |
O(n) |
O(1) |
|
Removal from the end |
O(1) |
O(n) |
|
Removal from mid |
O(n) |
O(n) |
4. Memory Requirement
- An array, as previously stated, stores elements in contiguous memory locations. For a specified size in the array declaration, an array will directly access the memory pool from the memory area. For example, if we have 5 integer elements in our array, the size taken would be equivalent to:
Utilized memory space = 5 * (integer size) = 5 * 4 = 20
- When we know the size of items that we will store in the list, then using a linked list will not be ideal as a linked list requires more memory space to store pointer variables. For example, if we have a linked list with size five, the required equivalent size would be:
Utilized memory space = 10* (Integer size) = 10 * 4 = 40
However, if we don't know the size of our list at compile-time, array isn't the best choice because we'll have to generate a new larger array and copy the contents of the old array to it. This will be highly inefficient. So, instead of that, we can use a linked list as the size of the linked list can be changed at runtime.
Hence, we can conclude that an array can be used when size is finite or small, and a linked list can be used when the size is unknown or infinite.
When to Use Array and Linked List
The table given below represents when to use which data structure based on different parameters:
Array |
Linked List |
|
When you need speed for iterating through the list of items. |
When you need constant time for performing insertion or deletion. |
|
If you know how many elements will be in the array ahead of time. |
If you have no idea how many items will be there in the list. |
|
When you need random/indexed access to the elements. |
When there is no need for random access of elements. |
|
If you want to add elements only from the end of an array. |
If you want to add items to the list in the middle (such as a priority queue implementation). |
Difference Between Array and Linked List in Tabular Format
Here, we will look at the difference between array and linked list in tabular format.
Array |
Linked List |
|
Stores elements in contiguous memory locations |
Stores elements in non-contiguous memory locations |
|
An array contains only one field which stores data element |
The linked list is comprised of nodes consisting of two fields: data and address field |
|
An array is static, i.e. memory size is fixed and cannot be updated at the run time |
The linked list is a dynamic data structure whose size can be changed at run time |
|
The elements of an array are independent of each other |
The elements of a linked list are dependent as the address of the next node is stored in the previous node |
|
Any element in an array can be accessed directly by the index, making it faster to access any element |
As the linked list is traversed from the first member, accessing an element in a linked list is more time-consuming |
|
Memory allocation is done at compile time |
Memory allocation is done at run time |
|
Since memory regions are consecutive and fixed, inserting or removing data is more expensive |
In a linked list, insertion and deletion operations are quick and uncomplicated |
|
Size remains constant |
Size grows or shrinks when elements are inserted/deleted |
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!
Conclusion
In this data structure tutorial, we explored the difference between array and linked list. We discovered when to use which data structure based on several parameters. We also learned about complexity analysis for performing different operations in both these data structures. Finally, we listed the difference between array and linked list in tabular format along with the information on when to use which data structure.
If you are seeking for more comprehensive learning which goes beyond data structures and encompasses the fundamentals of interactive application development, Simplilearn’s Software Development Courses will be precisely suited to you. The courses in the above catalog can build your chances of getting into a software developer role by assisting you in mastering the craft of software development. So, explore now and get started!
Have any questions about this article on the Difference Between Array and Linked List? If yes, please leave them in the comments section at the bottom of this page; we will respond to them soon!
