As a C programmer when we need to deal with multiple data elements of same type, we think of using array or linked list. Many times we scratch our head which data structure we should go for.. Though Array and linked list have many similarities, they are two fundamentally different data structures. Let’s see when to prefer linked list over array.
Prefer Linked List When Number of Elements are not Know
When we need to store elements but the number of elements are not known in advance, I mean in programming time. Number of elements can be taken as input from the user run time. Another situation could be, we need to store elements as and when comes from another module. In this situations, prefer linked list because in case of array we have to allocate memory to hold the elements in advance (in time of writing the program). As number of elements are not known, we won’t be able to allocate appropriate amount of memory. We can allocate very large chunk of memory but most of the allocated memory will be wasted if the actual number of element is not large. There could be another problem. If the number of elements is higher than we anticipated in time of allocating memory, then we won’t be able to store all elements. One solution could be, we can reallocate the whole array every time we need to store extra element but that will be expensive in terms of performance.
In this situation we can use linked list to avoid these problems. In case of linked list we don’t have to allocate memory beforehand. When new element is inserted into a linked, memory is allocated in that time for the new element.
When Number of Elements Increase or Decreases Run Time
If the number of elements increases or decreasing during the execution of the program, then we should use linked list. Lets see what are the problems with array. If the number of elements increases over time and the number exceeds the the allocated memory, we can’t store the new elements. We have different problem with the array if the number of elements decreases over time. Hole or gap between two valid entries will be created in the array and also there will be memory wastage. As memory is allocated in time of insert element in the list and de-allocated in time of deleting the element, there will not be any shortage or wastage of memory.
When to Insert Element at the Beginning or Middle of the List
It is not convenient to insert element at the beginning or in the middle of an array. One example we want to insert element in the middle of a list is when we want to maintain a sort list after insertion. In this case, we have to shift all the right elements by one place. That is not at all efficient. Linked list does not have this problem. We can insert element in a linked list in any position without rearranging the whole existing list.
Random Access of Element is not Required
Random access means no matter what the position of an element is in the list, access time will be same. Access time does not depend on the position of the element in the list. If random access or constant time access of elements is required, then you should not go for linked list. Accessing an element in a linked list is always linear. But we can access the array elements in constant time using the index of the elements.
Prefer Linked List for Stack, Queue Implementation
Always prefer linked list to implement data structures like stack, queue, priority queue etc. As the number of elements of these data structures changes run time, linked list is more suitable than array for the reasons mentioned above. Though it is not impossible to implement stack or queue using array.
