SEList: A Space-Efficient Linked List
Explore the SEList data structure to understand how it improves space efficiency in linked lists by grouping elements into blocks and using bounded deques. Learn about its design, space requirements, and how it offers efficient element access with minimal wasted memory.
We'll cover the following...
One of the drawbacks of linked lists (besides the time it takes to access elements that are deep within the list) is their space usage. Each node in a DLList requires an additional two references to the next and previous nodes in the list. Two of the fields in a Node are dedicated to maintaining the list, and only one of the fields is for storing data.
Advantage of SEList
An SEList (space-efficient list) reduces this wasted space using a simple idea: Rather than store individual elements in a DLList, we store a block (array) containing several items. More precisely, an SEList is parameterized by a block size . Each individual node in an SEList stores a block that can hold up to elements.
For reasons that will become clear later, it will be helpful if we can do Deque operations on each block. The data structure that we choose for this is a ...