SEList: A Space-Efficient Linked List
Discover the implementation of a space-efficient linked list.
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 storing individual elements in a DLList, we store a block (array) containing several items. More precisely, an SEList is parameterized by a block size b. Each individual node in an SEList stores a block that can hold up to b + 1 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 b + 1 and never grows or shrinks. The important property of a BDeque is that it allows for the addition or removal of elements at either the front or the back in constant time. This will be useful as elements are shifted from one block to another.
class BDeque extends ArrayDeque < T > {BDeque() {super(SEList.this.type());a = newArray(b + 1);}void resize() {}}
An SEList is then a doubly-linked list of blocks:
class Node {BDeque d;Node prev, next;}int n;Node dummy;
Space requirements
An SEList places very tight restrictions on the number of elements in a block: Unless a ...