Speeding up access to linked list elements
Searching for an element in a linked list is a very iteration-consuming task. For every such query, you'd have to start at the head of the list and jump from element to element using the next cell's references till you find the item you're looking for. This is a worst case O(N) operation, which is quite expensive as it grows at the same time as the size of your data.
One thing that we can do about this is inspired by caching. Caching is about storing the most-accessed elements in a "close" place, drastically reducing the complexity of retrieving elements from sequential data structures.
As far as linked lists are concerned, we would store the most-accessed elements near the head of the list, as this would be the "closest" place for every linked list retrieval algorithm. Here, you'd always start from the beginning of the list to begin any traversal operation. This will be done by always storing the result of...
