Hands-On Data Structures and Algorithms with Python - Second Edition

A faster append operation

There is a big problem with the append method in the previous section: it has to traverse the entire list to find the insertion point. This may not be a problem when there are just a few items in the list, but it will be a big problem when the list is long, as we would need to traverse the whole list to add an item every time. Each append will be slightly slower than the previous one. The current implementation for the append operation is slowed down by O(n), which is not desirable in the case of a long list.

To fix this, we store not only a reference to the first node in the list but also a reference to the last node. That way, we can quickly append a new node at the end of the list. The worst-case running time ...