CODEWITHSUNDEEP
arraysswiftlinked-list
DemetrioProgramerOsorio
DemetrioProgramerOsorio

Reputation: 114

Linked lists in Swift

I decided to polish my knowledge of data structures and came across linked list.

I was wondering if anyone has any practical example of where do we use them in relation to mobile development or any other kind of projects that use swift as their language since to me it seems the Array class already has enough flexibility as it is.

Upvotes: 2

Views: 2856

Answers (1)

Rob Napier
Rob Napier

Reputation: 299555

You should use linked lists anytime you need their primary benefit: O(1) insertion and deletion at arbitrary points in the list.

The mistake most people make with linked lists is trying to implement them as a value type in Swift. That's very hard, and the resulting data structure is generally useless. The most common form is with an enum:

enum List<T> {
    indirect case Cons(T, List<T>)
    case Nil
}

let list = List.Cons(1, .Cons(2, .Cons(3, .Nil)))

I've never seen anyone come up with an efficient implementation of that. Efficient collections in Swift require copy-on-write, and that's very hard to build for an enum.

The natural way to build linked lists in Swift is as a mutable reference type. That's very easy to make efficient and is very useful.

class List<T> {
    var value: T
    var next: List<T>?
    init(_ value: T, _ next: List<T>?) {
        self.value = value
        self.next = next
    }
}

let list = List(1, List(2, List(3, nil)))

And in that form, you'd use it any time you want O(1) insertion and deletion at arbitrary points in the list.

You could also build this as an immutable reference type (using let) if you had several large lists that shared a significant tail. I've never seen that come up in practice.

Most folks I know who go down this route want an immutable linked list so they can implement the many very beautiful recursive algorithms that are built on them and which are very common in FP languages (this may say more about the people I know than the question itself). But Swift is at best mildly hostile to recursion, so this is rarely worth the trouble IMO except as an exercise. But recursive algorithms are just one use of linked lists. As an O(1) arbitrary-insertion data structure they're as useful in Swift as they are in Pascal and C, and you build them roughly the same way.

Upvotes: 7

Related Questions