Linked Lists vs. Arrays

Memory allocation comparison

The main difference between arrays and linked lists is memory allocation. An array instantiates a fixed block of memory based on the size defined 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.

Performance comparison

Other differences can be observed in the way that elements are inserted and deleted. As for linked lists, insertion, and deletion at head happens in a constant amount of time ,while in the 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, an array takes constant time to access an index, while with a linked list, you will have to iterate the list from the start until you find the node with the correct value.

Apart from memory allocation, there are some differences in performance between linked lists and arrays. Take a look at them now:

Operation	Linked List	Array
Access	O(n)	O(1)
Insert (at head)	O(1)	O(n)
Delete (at head)	O(1)	O(n)
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, you 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.

---