Linked Lists vs. Arrays
Let's put the two data structures against each other to find out which is more efficient.
We'll cover the following
Difference between Array and Linked List
The main difference between arrays and linked lists is in the way elements are inserted and deleted. As for linked lists, insertion, and deletion if done at the beginning of the linked-list, happen in a constant amount of time, while in the case of arrays, it takes O(n) time to insert or delete a value. This is because of the different memory layout of both the data structures. Arrays are arranged contiguously in the memory, while nodes of a linked list may be dispersed in the memory. This memory layout also affects access operations. The contiguous layout of arrays allows us to index the array; thus, access operation in the array is O(1), whereas, for a linked list, we need to perform a traversal; therefore, it becomes O(n).
The following table sums up the performance tradeoff between arrays and linked lists:
| Operation | Linked List | Array |
|---|---|---|
| Insert (at tail) | O(n) | O(1) |
| Delete (at tail) | O(n) | O(1) |
In a linked list, insertion and deletion at head happen in a constant amount of time. You can simply add or delete a Node between two Nodes.
In an array, the two operations would take O(n) time since addition, or deletion would mean shifting the whole array left or right.
The access operation in arrays is much faster, as you can use the index of an array to access the value you need. In linked lists, there is no concept of indexing. To reach a certain element in the list, we must traverse it from the beginning.
As you can see, there is a trade-off between the facilities provided by both data structures. You will understand more about the working of linked lists in the lessons that follow.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.