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 ...
Get Clojure Data Structures and Algorithms Cookbook now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
