Linked List vs Array

Linked lists are used to store collections of data but we have already seen that mechanism for doing this in an array. An array is a sequential structure, meaning that it is a group of memory elements located in contiguous locations(located next to one another in a group). So why would you use a linked list instead of an array?

Arrays technically allow you to do all the things linked lists do, but the biggest difference comes to light when we look at the insertions and removals. Since arrays are indexed, when you perform insertions or removals from the middle of the array, you have to reset the position of all the values to their new indices.

But withlinked lists, it's much easier to shift elements around. You can insert a node anywhere in the physical memory that has an open space for it since it does not need to be localized.

Alternatively, arrays are beneficial when it comes to finding items since they are indexed. If you know the position of an item you can access it in constant or O(1) time. But since the nodes are scattered throughout memory, there is no easy way to access a specific node in a linked list. You would need to start traversing from the head and go through each node until you find the node you need. This would take linear or O(n) time.