CodePudding user response:
it is said that inserting a value in the middle of the list has constant time complexity
That is not true if you are reading the documentation more closely. What the documentation states are:
... Despite its name, this class does not implement the List interface. It does not allow constant time lookup by index.
...
In return, each element knows its own place in the linked list, as well as which list it is in. This allows constant time
LinkedListEntry.insertAfter
,LinkedListEntry.insertBefore
andLinkedListEntry.unlink
operations when all you have is the element.A LinkedList also allows constant time adding and removing at either end, and a constant time length getter.
https://api.dart.dev/stable/2.9.2/dart-collection/LinkedList-class.html
So what it means is that if we do have an reference to a given element, we can put a new element to our LinkedList
if this new element are inserted right before or after our current element.
Since a reference to a LinkedList
itself has a reference to the first and last element (since it is doubled-linked), it also means we can insert an element at the beginning or end of the list if we just have a reference to the LinkedList
itself.
But if we want to insert at an arbitrary index, we need to iterate over each element until we get the position we want to insert at. This operation require linear time since we cannot just jump to a specific position (like with normal List
).
So no, Dart does not handle LinkedList
(Double-linked) differently from other double-linked list implementations. Which is also what the documentation describes.