[Suggestion] [Beginner] Data structure that implements quick insertion and removal of items

Hi folks, I was wondering if it may be possible to add a data structure that would add the following points:

  • fast insertion, at most O(logn)
  • fast removal, at most O(logn)
  • fast access with subscript, at most O(logn)

While the Deque module already covers it, it gives me a bit of problems during resizes of the array, I'm using it as an underlying data structure for my app that contains approximately 200k records.

I don't want to make you lose time, as I'm a newbie in using both Git and Swift, and I'm open to suggestions, so, if you know other workarounds, I'm here to learn.

Nonetheless, here's how I would achieve my goals:

  • The data structure should be based off a SkipList, but with fixed length promotion of nodes, so that we can control where each promoted node is.
  • Each "promoted" node knows how many items are in the middle between both the previous and next node
  • Each node knows whether it is pointed by a promoted node and every promoted node points to an underlying node (This allows us a traversal between layers of "promoted" nodes)
  • Each time we add a node at a random position, we see if we have too many items, and if so, we promote a new node
  • Each time we remove a node at a random position, we see if we have too few items, and if so, we remove a promoted node
  • The search would occur by iterating from the uppest layer of promoted nodes and going down each time we would surpass our objective. Once reached, we only go down

I already worked on something my work

This started off more like a private repo for datastructures I needed.

I hope to not have angered anyone, and I'm open to suggestions and even a rejection.

Why not Dictionary?
Otherwise I'd look at some B-Tree flavour.

1 Like

Thank you for the reply.

I need to use the data inside a ForEach(), unless it’s a wrong approach, and so I need it to be conformed to the RandomAccessCollection.

Do you know if It is possible to conform a Dictionary or a B-tree to that?

If you use them inside a ForEach, I think you'd also want data to be ordered. Swift's builtin dictionary isn't, but the collections package does provide OrderedDictionary whose keys property has the random-access-collection OrderedSet type. However, I haven't looked into the complexity of the operations you outlined in the OP.


ForEach works with Dictionary out of the box however it indeed returns items in "arbitrary" (yet well defined) order:

ForEach(Array(dictonary.values), ...

Do you need items in a particular order (I guess you do)? If so could you tolerate spending O(N logN) to do the sort?

I don't use Algorithms package to know if B-Tree is in there (and in what form). It is not too complicated to implement but could be tricky if you never did this. It requires "<" or other form of "less" operation defined on elements and ForEach will return elements according to that. However it doesn't sound you need B-Tree, dictionary should suit you just fine. Note that SwiftUI itself may struggle with lists containing 200K elements - I guess that would be the limiting factor, not the O(N) vs O(logN) complexity.

1 Like

I've tried it, but it makes my scroll stutter. I forgot to mention that I add items while my program is running. I emulated the behavior by adding 100 items when I finish to show the ones I already had.

Would a B-tree be better?


I don't know your app to suggest anything better. E.g. could you postpone adding items till after the scroll is finished?

After you tried all possible tricks like withAnimation / animation blocks, etc, you may want to consider UIKit: UICollectionView might give you better results. It's API is quite different compared to SwiftUI's List – very "manual" (more work needed and more customization possible). On the plus side it would handle much more items compared to SwiftUI, on the minus side - diffing is more problematic (you may try luck with its builtin support for diffable data sources). As a side note - you may embed UIKit views into SwiftUI app and vice versa.

OTOH have a look at this video : Building Custom Views with SwiftUI - WWDC19 - Videos - Apple Developer towards the end. This shows that very fast drawing is possible with SwiftUI.

1 Like