33
How can you differentiate between Array and LinkedList?
Hey Everyone, As I am posting some DSA related stuff on Twitter & LinkedIn using Python for few days it made me realize that let's write an article for everyone. Here you go.....
Array is a data structure that stores the same type of data in memory i.e you can't have multiple data types in an array.
Array elements store contiguously in memory location.
array(data_type, value_list)
Here "i" is the data type code. Check below the common data types used for the array module.
LinkedList is the collection of nodes that stores dynamically/randomly in memory. Node has two parts data and link, data is the value store in a node and link holds the address of the next node.
There are so many differences between Array and LinkedList. pointed few of them using examples in below
👉 As we already discussed below point in Array and LinkedList definition:-
🔸Array stores elements contiguously in the memory location.
🔸LinkedList nodes stores dynamically/randomly in memory.
See the below pic for a better understanding 👇
👉 Cost of accessing an element:-
🔸Array: In the below picture, you can see elements are stored and base addresses are assigned for each element.
These base addresses are contiguous for the array i.e 400, 401, 402..... 406,407.
So, if you know the base address of an element in an array, then you can get the base address of any element in an array.
To get the address of an element you just need to perform a simple operation that's it.
So accessing the elements of an array's cost is** O(1)**.
🔸LinkedList: As we discussed above LinkedList is a collection of Nodes and that is a collection of two sub-parts i.e., one part contains elements and another one contains the address of the next node.
So if you want to access an element in a linked list, you have to know the first element address which is called Head here.
If you want to access the 4th node, have to traverse from the first node.
Accessing the last node, you have to traverse all the nodes.
So Average time complexity to access an element in LinkedList is O(n).
We can conclude that for accessing an element, Array is the best choice than LinkedList.
👉 Cost of Inserting the element at the beginning:-
🔸Array: If we are adding an element at the beginning, we need to shift other elements to the right to create the space in the first position.
if n numbers of elements are present in the array, the time complexity will be equal to the size of the array i.e., O(n).
🔸LinkedList: If we need to add a node at the beginning, we don't move any elements anywhere, just create a new node and add the address of the first node to the new node.
This is an easy way to add an element at the beginning. We can say this is just a constant time i.e., O(1).
We can conclude here, for inserting an element at the beginning LinkedList is the best choice than Array.
👉 Cost of Inserting the element at the end:-
🔸Array: If the array has space, we can insert an element at the end using the array index. In this case, it has constant time complexity i.e O(1).
But If the array is full then we have to copy the array to the new array. So, the time complexity is O(n).
🔸LinkedList: If we talk about LinkedList, we have to find the head then we can find the last node.
So, we are searching the whole LinkedList to find out the last node to insert an element.
So time complexity is O(n).
👉 Cost of Inserting the element at the middle:-
🔸Array: If the array has space, insert an element at the middle of the array and moving other elements to the right side of the array.
So the time complexity is O(n).
🔸LinkedList: If you want to insert an element at LinkedList, you have to traverse from head to that position.
So, the time complexity is equal to the size of LinkedList elements i.e O(n).
Based on the above discussion you can choose one or another one of your requirements.
Thank you so much for reading my article. Hope you understood the differences between Array and LinkedList. 😊
33