Dynamix array is also known as Vector, Dynamic array is an array that resizes itself up or down depending on the number of content.
Linked lists have both advantages and disadvantages. The advantage of linked lists is that they can be expanded in constant time. While creating dynamic arrays, we must allocate memory for a certain number of elements. To add more elements to the array when full, we must create a new array and copy the old array into the new array. This can take a lot of time.
Since dynamic array implementation usually allocates more memory than necessary, so there is a bit of unused space.
We can prevent this by allocating lots of space initially but then we might allocate more than we need and waste memory. With a linked list, we can start with space for just one allocated element and add on new elements easily without the need to do any copying and reallocating.
Disadvantage of dynamic array is inserting or removing objects in a random position in a dynamic array is very slow O(n/2), as it must shift (on average) half of the array every time. While, insertion into linked list is fast O(1) insertion and removal at any position in the list, as insertion in linked list is only breaking the list.
So Linked list provides the following two advantages over arrays :
- Dynamic size
- Easy insertion / deletion
But, Linked lists have following drawbacks over dynamic array:
- Random search is not possible.
- Low cache locality over dynamic array.
- Extra space is required for pointers in each node.
Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.