Home > Software engineering >  Time complexity of LinkedList in dart
Time complexity of LinkedList in dart

Time:07-19

In the dart enter image description here

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 and LinkedListEntry.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.

  • Related