What do you call a data structure containing multiple lists?

Question

I was thinking about a data structure to make concatenation of lists easier, something that contains multiple lists (in a sequence) internally, but can be treated as a single contiguous list. I know such a data structure must exist out there already, and I would like to find articles about its performance, but I don't know what it's called. The closest thing I've found so far is a skip list, but that seems to be more like a binary search tree and isn't just for dumping elements in.

I thought of implementing it something like this - the data structure L starts out containing an empty doubly-linked list of arrays.

[]

Then, when an array or other list-like data structure is added to it, it becomes the first element.

Add [100, -4, 2] to L
Head -> [100, -4, 2] <- Tail

The next array added becomes its second element, and so on.

Add [2, 6, 1] to L
Head -> [100, -4, 2] <-> [2, 6, 1] <- Tail

Add [4, 5] to L
Head -> [100, -4, 2] <-> [2, 6, 1] <-> [4, 5] <- Tail

L will only expose methods to iterate over it one at a time (in order), so it can be treated as a normal list.

Answer 1

If you don't care about the order of elements (e.g. you can deal with sets instead of lists) then the union-find structure gives an (amortized) constant time union operation.

There's also the unrolled linked list but the idea is to unroll a list for better cache performance rather than better performance when concatenating lists. For this reason, the number of elements at each node is generally bounded.

I don't think the data structure you describe has a name. It will act like a linked list in the worst case e.g. O(1) to add at the front/back and O(n) to search but you get the added bonus of O(1) concatenation that would be O(k) (for k new elements) with linked lists.

If that's all you're doing with your list then there doesn't seem to be any need to rearrange your list at any point e.g. by coalescing or splitting up nodes.

Update: An example of a specific data structure that seems to behave in the way you want is the Quicklist in Redis. It is described as a 'linked list of ziplists' where a ziplist is a contiguous bit of memory.

Answer 2

The short answer is I haven't seen this as a data structure before. I think generally it's just called a "list of lists", and it's the operation for iterating through it that gets a special name. Python's "itertools.chain", something like "flatten().iter()", or in lazy functional languages just "flatten".

The longer answer is, your data structure L is solving a (to me) weird use case I don't see often.

• You want to support only iteration and concatenation
• You don't know all the things to concatenate in advance
• You don't want to modify the original lists (concatenating linked lists destructively is already O(1), if you just store a tail pointer)
• You only want to concatenate primitive lists AFAIK, not more instances of L.
  • If you want more instances of L, I could see this being worth naming, but also probably worth optimizing. Chris Okasaki's "Purely Functional Data Structures" talks about how to support linked list concatenation efficiently, without destroying the original lists.
  • If you only want primitive lists, I would expect to see indexed lists used, not linked lists, and thereby supporting indexing efficiently on the master list. This could potentially require an additional master data structure (look up the "rope" data structure, which is used for efficient static list or string concatenation with indexing).

Answer 3

You appear to be describing a tree.

You have a list of lists. That corresponds to a two-level tree. Each list is a node in the tree, and each element of that list is one of its children.