16
NovDifferences Between Array and Linked List
Arrays Vs. Linked Lists
Arrays and Linked Lists are the types of non-primitive linear data structures. An array is a collection of elements of the same data type stored at contagious memory locations that can be randomly accessed with their index number. A Linked List consists of a series of connected nodes that are randomly stored in the memory. Here, each node consists of data and the address of the next node.
We have covered all the topics related to these two in the previous tutorials. In this DSA tutorial, we'll analyze the differences between arrays and linked lists in data structures. To further enhance your understanding of data structures, enroll in our best Data Structures and Algorithms Course.
What is an Array?
An array is a powerful data structure that allows users to store and manipulate a collection of elements, all of the same data type in a single variable. Simply, it is a collection of elements of the same data type stored at contagious memory locations that can be randomly accessed with their index number.
Declaration of an Array
Syntax
dataType arrayName[arraySize];
Example
int a[5];
Here, an integer type array a is declared with the size 5. It can store 5 integer values.
Read More: Arrays in Data Structures
What is a Linked List?
A Linked List is a data structure consisting of a series of connected nodes randomly stored in the memory. In a linked list, each node has two parts, the first part is the data and the second part contains the pointer to the address of the next node.
The first node of a linked list is called the Head, and it acts as an access point. The head pointer points to the first element of the linked list. The last node is called the Tail, and it is the end of a linked list that points to a NULL value.
Declaration of a Linked List
Syntax
struct node
{
int data;
struct node *next;
};
Here, we have created a structure
named node
that contains two variables, data
of integer type, and a pointer, next
that contains the address of the next node.
Read More: Linked Lists in Data Structures
Differences Between Arrays and Linked Lists in Data Structures
1. Time Complexity Analysis
Operations | Arrays | Linked Lists |
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) |
2. Memory Consumption
Language | Array | Singly-linked list | Doubly linked list |
C/C++ | 4 bytes | 8 bytes | 12 bytes |
JVM language | 4 bytes | 24 bytes | 24 bytes |
3. Access and Execution Time
Since the memory for an array is allocated in one piece, its elements are located at consecutive memory addresses. When accessing t main memory, all array elements on the same memory page are simultaneously loaded into the CPU cache. Thus, once we have accessed one array element, the neighboring elements can be accessed very quickly.
The nodes of a linked list 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.
Arrays Vs. Linked Lists: A Thorough Comparison
Arrays | Linked Lists |
An array stores a collection of elements with the same data type and only stores values, unlike a linked list that has data and address as its values. | It is a data structure of the set of elements that contain two parts, data and address which is a pointer to the next element and each element is of the same data type |
There is no such node concept as it contains only a set of values and is hence used as a default data structure in many modern programming languages. | Each element is considered as one single node where these nodes are connected using pointers which are the address value of the next node and other than the address it also stores data for each node. |
In the case of an array, memory size is fixed, and it's impossible to change it during the run time. | In the linked list, the placement of elements is done during the run time. |
The elements are not dependent on each other. | The data elements are dependent on each other. |
The array takes more time while performing any operation like insertion, deletion, etc. | The linked list takes less time when performing these operations. |
Array gets memory allocated in the Stack section. | the linked list gets memory allocated in the Heap section. |
In an array, random access is possible as it uses array indices as addresses to access instead of pointers. | In a linked list random access to the elements is impossible as it uses the pointers which are connected to the elements sequentially. |
Arrays can be defined in a one-dimensional array, two-dimensional array, or multidimensional array. | Linked lists can be defined as simple linked lists, circular linked lists, or doubly linked lists. |
In the case of an array, memory utilization is ineffective. | In the case of the linked list, memory utilization is effective. |
When to use Array over Linked List?
- The total number of elements to be inserted is known beforehand
Here, an array is considered a good option as memory allocation is done only once in the beginning. Memory-related issues during runtime are minimized.
- Accessing the N-th element is a common operation
Here, an array must be used as random access requires instant O(1) time while in Linked List, it takes linear time O(N) time. Hence, arrays are more used in database applications where random access is important.
- Implement algorithms that need random access
This is important as in certain algorithms using an array is an optimization while using a Linked List results in an overhead.
When to use Linked Lists over Arrays?
- Inserting and Deleting new elements is a common operation
Here, Linked Lists must be used as depending on the implementation/ approach, insertion, and deletion can be performed in constant time O(1) while in the array, random deletions take linear time O(N) as all elements are readjusted.
- Implementing Undo operation
The most common use case of Linked List is the implementation of undo operation in Browsers and Word editing software. This is the best option as the number of operations to be stored in memory varies and the only important operation is the go back. There can be branches and hence, Linked List is the perfect choice.
- An array of Linked Lists
In many applications, we use an array of Linked Lists where at every index of the array, there is a Linked List. This structure is used in collision resolution in Hash Map.
Summary
In the above tutorial, we covered all aspects of differentiating an array from linked lists. Before understanding this, you need to be thorough with the concepts of arrays and linked lists. If you aren't, refer to them diligently and come to this tutorial.