Linked lists have been an integral part of programmers work. Now its time to annihilate this prehistoric data structure.
Since early C days, you find linked list implementations in nearly every source file, most likely in its simplest form: A data structure with a ‘next’ pointer, refering to the node of the list, beeing such a data structure again.
Then came object-orientation, and every class library provided at least one generic class for linked list, to the programmers don’t need to implement a linked list themselves again. Brave new world. But, surprise, surprise – nobody used them.
What the hell happened? Where had this most important of all data structures gone?
Let’s think about the reasons to use a linked list:
- Linked lists are quite simple to program.
- Insertion in a linked list is cheap: You can insert an element in O(1)
- Concatenation of linked lists is cheap: You can put together two linked lists in O(1) (assumed that you have a double linked list), by setting the next-pointer of the last element of the first list to the head of the second list.
Good reasons, it seems. So why, why, why….?
It’s simple to explain: Compare this advantages with other data structures, let’s say a self growing array:
- Every library provides such an array
- Consecutive insertion in an self growing array is cheap: You can insert an element in O(2) – but you don’t need to get new memory with “new” every time you insert an element
- The concatenation of two lists is expensive, each element must be copied, so this is O(n).
So the advantage seems to be the concatenation of two lists. Isn’t this sufficient to justify the existance of a generic linked list class in class library?
Let’s have a look at such a concatenation operation in O(1):
Assume you have two lists, l1 and l2. A new list is created by the concatenation of l1 and l2, let’s call this list l3. If you create l3 the way described above, you will face a problem: The elements (nodes) in l1 and l2 are now as well in l3. But each node has only one next pointer. If you now change l3, you will as well change l1 or l2. Since you have a generic linked list class, this is not desired behaviour. So you must create l3 by copying the elments from l1 and l3 to new nodes. This means, that you now do this operation in O(n).
So now the last advantage of a linked list compared to an array has gone. Of course, there are a lot of cases, where the two operants of the concatenation are no longer used, and therefore, copying is not necessary. But – it should be a generic implementation, eh? And to be honest: How often do you need a concatenation operation?
In short words: Nobody needs a generic linked list class, that has no advantages. You instead use an array – where you can access the entries simply by the index of the array in O(1).