SEList: A Space-Efficient Linked List
Explore the SEList data structure to understand how it improves space efficiency over traditional linked lists by storing elements in blocks. Learn about the block size parameter, BDeque structure, and how SEList minimizes wasted space while supporting efficient element access and modifications.
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.
Advantages 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 BDeque (bounded deque), derived from the ArrayDeque structure. The BDeque differs from the ArrayDeque in one small way: When a new BDeque is created, the size of the backing array a is fixed at ...