Doubly Linked List
What’s mean of the Linked list’s tail pointer?
- Inserting at the end is O(1) instead of O(N)
- In a Doubly Linked List then removing from the end is also O(1) instead of O(N)
And the pointer will takes up a trivial amount of extra memory.
If we design a doubly linked list, add the self.tail pointer would be good. Because the pointer can support us on add or delete by the index operations when the index equals to length of linked list.
Persistent data structure
In computing a persistent data structure or not ephemeral data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not visibly update the structure in-place, but instead always yield a new updated structure.
Reference
SoftwareEngineer Persistent data structure The Algorithms Python