Linked Lists vs. Arrays
Let's put the two data structures against each other to find out which is more efficient.
The main difference between arrays and linked lists is memory allocation. An array instantiates a fixed block of memory based on the size we define in its declaration.
On the other hand, linked lists can access or release memory based on the addition and deletion elements. Its size is not fixed.
Other differences can be observed in the way elements are inserted and deleted. As for linked list, insertion, and deletion at head happens in a constant amount of time while in case of arrays it takes O(n) time to insert or delete a value because you have to shift the array elements left or right after that operation. But in case of searching an element, for an array it takes constant time to access an index while in case of a linked list you will have to iterate the list from start till you find the node with the correct value.
Apart from memory allocation, there are some differences in performance between linked lists and arrays. Let’s take a look at them now:
| Operation | Linked List | Array |
|---|---|---|
| Insert (at tail) | O(n) | O(n) |
| Delete (at tail) | O(n) | O(n) |
In a linked list, insertion and deletion 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 simply 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 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 70+ hands-on prep courses.