Linked lists improved

📚 Official Books Data Structures & Algorithms in Dart
1

I think the implementation of linked lists can be improved by…

  • adding the length property,
  • adding the previous property, which points at previous node, and
  • replacing insertAfter and removeAfter methods with insertAt and removeAt methods respectively, which use the index parameter.
2

Those are some good ideas. Here are a few additional comments to take into consideration:

  • length: The length property would have O(n) time complexity since you would need to start at head and count the nodes until you got to tail. You could improve this to O(1) if you added some additional logic to cache the length and update the value every time you added or removed a node.
  • previous: Adding a previous property would make this a doubly linked list, which is a slightly different data structure than the singly linked list described in the Linked Lists chapter. The advantage of having previous is that it would be O(1) to get the previous node. The disadvantage is that the logic is a bit more complex and the memory overhead a little higher since you are pointing to an extra node. Everything is a tradeoff, so you need to make the decision based on the requirements of your application.
  • insert: I completely agree that insertAt and removeAt with an index are much better from the UX perspective than insertAfter and removeAfter. The difference is that insertAt and removeAt are slower O(i) operations (where i is the index), whereas insertAfter and removeAfter are fast O(1) operations.
1 Like
3

In the second edition of the book, I’m including a DoublyLinkedList implementation in the challenge folder for Chapter 5, “LinkedLists”. This has a Node with a previous property.