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

**URL:** <https://forums.swift.org/t/suggestion-beginner-data-structure-that-implements-quick-insertion-and-removal-of-items/60638>\
**Category:** Collections\
**Tags:** swift-collections\
**Created:** [October 3, 2022, 9:38pm UTC](https://forums.swift.org/t/suggestion-beginner-data-structure-that-implements-quick-insertion-and-removal-of-items/60638 "2022-10-03T21:38:52Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![CnF-Gris](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/cnf-gris/32/27071_2.png) [@CnF-Gris](https://forums.swift.org/u/CnF-Gris)\
**Post date:** [October 3, 2022, 9:38pm UTC](https://forums.swift.org/t/suggestion-beginner-data-structure-that-implements-quick-insertion-and-removal-of-items/60638/1 "2022-10-03T21:38:52Z")

</div>

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](https://github.com/CnF-Gris/ChrisDataStructures)

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.

---

<div class="post-metadata">

**Author:** ![tera](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tera/32/38201_2.png) [@tera](https://forums.swift.org/u/tera)\
**Post date:** [October 4, 2022, 8:13am UTC](https://forums.swift.org/t/suggestion-beginner-data-structure-that-implements-quick-insertion-and-removal-of-items/60638/2 "2022-10-04T08:13:37Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![CnF-Gris](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/cnf-gris/32/27071_2.png) [@CnF-Gris](https://forums.swift.org/u/CnF-Gris)\
**Post date:** [October 4, 2022, 3:38pm UTC](https://forums.swift.org/t/suggestion-beginner-data-structure-that-implements-quick-insertion-and-removal-of-items/60638/3 "2022-10-04T15:38:09Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![filip-sakel](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/filip-sakel/32/8697_2.png) [@filip-sakel](https://forums.swift.org/u/filip-sakel)\
**Post date:** [October 4, 2022, 4:25pm UTC](https://forums.swift.org/t/suggestion-beginner-data-structure-that-implements-quick-insertion-and-removal-of-items/60638/4 "2022-10-04T16:25:42Z")

</div>

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](https://swiftinit.org/reference/swift-collections/orderedcollections/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.

---

<div class="post-metadata">

**Author:** ![tera](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tera/32/38201_2.png) [@tera](https://forums.swift.org/u/tera)\
**Post date:** [October 4, 2022, 5:21pm UTC](https://forums.swift.org/t/suggestion-beginner-data-structure-that-implements-quick-insertion-and-removal-of-items/60638/5 "2022-10-04T17:21:50Z")

</div>

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

```swift
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.

---

<div class="post-metadata">

**Author:** ![CnF-Gris](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/cnf-gris/32/27071_2.png) [@CnF-Gris](https://forums.swift.org/u/CnF-Gris)\
**Post date:** [October 5, 2022, 8:57am UTC](https://forums.swift.org/t/suggestion-beginner-data-structure-that-implements-quick-insertion-and-removal-of-items/60638/6 "2022-10-05T08:57:23Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![tera](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tera/32/38201_2.png) [@tera](https://forums.swift.org/u/tera)\
**Post date:** [October 5, 2022, 10:30am UTC](https://forums.swift.org/t/suggestion-beginner-data-structure-that-implements-quick-insertion-and-removal-of-items/60638/7 "2022-10-05T10:30:02Z")

</div>

> [@CnF-Gris](#):
>
> Would a B-tree be better?

No.

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](https://developer.apple.com/wwdc19/237) towards the end. This shows that very fast drawing is possible with SwiftUI.
