Keeping a Tail pointer & Count to LinkedList implementation

[biscottigelato]

Any reason why a tail pointer and/or a count value is not kept in the Linked List implementation? Right now .last will actually traverse through the entire linked list at O(n) just to get at the last node. Appending to the linked list also traverses the entire linked list at O(n). Count will also cause a Linked List traversal at O(n)

Adding a tail pointer and a count value adds O(1) to space and performance at most for affected operations, however reduces .last, .append and .count from O(n) to O(1).

Happy to do a pull request on this if people are interested

[hollance]

This would make a nice addendum to the article. I wouldn’t rewrite the existing stuff but add it on to the end as a way to improve the current implementation.

[biscottigelato]

I am thinking more from the code/implementation perspective. Didn't really consider how this would impact the article. I can also add a blurb about adding tail and count and how that can improve efficiency. But that requires the pre-text of the tail/count code be part of the implementation tho, otherwise it won't make too much sense nor enough of a difference.

[hollance]

But you can show how ro change the implementation to add those things. And then include this as a different Swift file, LinkedListWithTailPointer.swift.

[kelvinlauKL]

Yup, as you suggested having a tail reference can improve time complexity. The article (and most introductory courses) don't talk about the tail until later on.

It's better for the reader to understand what inefficiencies they have to deal with and why the tail reference is introduced in the first place.