Implementing a skew binary random access list
Linked lists are traversed sequentially. To access an element, we need to begin at the top of the list and keep looking for references to the next cell and accessing it until we reach the item of our interest. In big O notation speak, access to an element in plain linked lists is a worst-case O(N) operation, which is quite expensive.
If we want to implement efficient random access to the data that a linked list contains, that is, if we want to specify an index and get to it efficiently—just as in an array, we can consider arranging the same data in a binary search tree, providing for efficient lookup and insertion operations.
If you represent the subscripts of your nodes in a binary format, you'd have ...
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.
