0
$\begingroup$

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.

$\endgroup$

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Unfortunately, I need my data to be stay in a particular order (and it isn't sorted), but thank you for the link to unrolled linked lists, I found a link to hashed array trees on the same page, and both look promising. $\endgroup$
    – user
    Oct 25, 2020 at 23:12
  • 1
    $\begingroup$ I recently came across the Redis Quicklist, which seems relevant. matt.sh/redis-quicklist-visions $\endgroup$
    – selig
    Nov 1, 2020 at 17:55
  • $\begingroup$ Thanks, that one looks great! If you add it to your answer, I can accept it. $\endgroup$
    – user
    Nov 1, 2020 at 19:14
2
$\begingroup$

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).
$\endgroup$
0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ @user, I don't know what you mean by linear in this context. $\endgroup$
    – D.W.
    Oct 25, 2020 at 18:08
  • $\begingroup$ I wanted to say that it was all in one line with only 2 endpoints rather than with nodes with multiple children branching off. I've added a small example to my question, if that helps. $\endgroup$
    – user
    Oct 25, 2020 at 18:12
  • $\begingroup$ @user, it's still a tree. $\endgroup$
    – D.W.
    Oct 25, 2020 at 18:13
  • $\begingroup$ Oh, okay, that makes sense. I'd still like to see if there's a specialized data structure somewhere, though, so I can see if there's already performance benchmarks and ways to implement it efficiently, rather than spend months experimenting with it and writing benchmarks myself. $\endgroup$
    – user
    Oct 25, 2020 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.