Complexity Comparison with Arrays#
If we know where an item is located in an array, then to retrieve the corresponding value, we go straight to it using indexing. The run-time complexity in \(θ(1)\). With linked lists, even if we know where an item is located, we must find that item. There is often a sequential search happening, with run-time complexity in \(θ(n)\).
The big advantage of linked lists is that the program can grab and release memory as it is working. We don’t need to know the size of the list in advance. Many tasks end up moving through the list, whether an array or a linked list, and doing a similar thing to each item. In those situations, we have the same time complexity, whether an array or a linked list is used.
Astute readers will notice, though, that a node contains an extra field over what is required to be stored in an array, namely the next field. Generally, the size of this field is small compared to the size of an entire record or value. However, this is not something to ignore. For example, if the list consists only of integers, then the linked list version will require twice the space (more than 32 bits per Integer + 32 bits per next field) versus the array version (32 bits per int)[1].
Arrays Vs. Linked Lists
Arrays are usually faster; linked lists more easily allow for changing sizes.