When should you choose a linked list over an array?

You should choose a linked list over an array when you need efficient insertions and deletions, but not random access.

A linked list is a dynamic data structure, meaning it can grow and shrink at runtime without any performance penalty. This makes it an excellent choice when you're dealing with an unpredictable number of elements. In contrast, an array is a static data structure, so its size must be determined at the time of creation, which can lead to wasted space if the array is too large or a need for resizing if the array is too small.

One of the main advantages of linked lists is the efficiency of insertions and deletions. In a linked list, these operations can be performed in constant time, O(1), as long as you have a pointer to the node you're dealing with. This is because you only need to update the links of the neighbouring nodes. In contrast, insertions and deletions in an array require shifting all elements over, which takes linear time, O(n), where n is the number of elements in the array.

However, linked lists do not support random access, meaning you cannot directly access the i-th element without traversing from the head node to the i-th node. This takes linear time, O(n). On the other hand, arrays do support random access, allowing you to access any element in constant time, O(1).

Another factor to consider is memory usage. Each node in a linked list uses more memory than an equivalent element in an array, as it needs to store the data and the reference to the next node. This can be a disadvantage if memory is a concern.

In summary, if you need to frequently add or remove elements and don't need to access elements by their index, a linked list is a good choice. If you need random access and memory is a concern, an array would be more suitable.