What is the idiom of linked data structure?

(I cannot guarantee that there is no mistake in the discussion below, if there is, please correct me, thx.)

Sometimes we need linked data structure (e.g. linked lists, binary tree, heap, etc.). The special thing about these structures is that they are defined recursively. We cannot define it directly with struct or enum, because we cannot know their size at compile time. I know some different ways to implement them, but none of them satisfied me.

Take a singly linked list as an example:

  • Implements node with classes: Data structures in Swift are used to struct with value semantics (e.g. Array, Dictionary), not reference semantics, so I don't think it works.
  • Wrap the node class with struct and add copy-on-write semantics to it.: This seems to create a lot of small objects (the example above has the same problem), ARC counters are used extremely frequently, and atomicity needs to be guaranteed. This kind of implementation is very common in languages that use tracing GC (e.g. languages on JVM), but I don't think this is an efficient implementation in Swift.
  • Use indirect enumeration type (use sum type like Haskell, ML, etc.): Enumeration type does not seem to be of copy-on-write, so this won't work.

The data structures in the Swift standard library are all continuous in memory (Array, Dictionary), so I don't have any good references. Everyone has their own implementation, but I want to know which one is officially recognized.

Are there similar examples in Apple-supported libraries?

See Recursive Enumerations

Sorry, but could you please tell me where this article explains the copy-on-write semantics of enumeration type? (maybe I missed it). enum seems to always produce a new copy, no matter how large the data structure is.

Terms of Service

Privacy Policy

Cookie Policy