Should the list part of a linked list type (not its nodes) be a struct or a class?

Using Swift
#1

One of the exercises in Paul Hudson's book Swift Coding Exercises is "create a linked list of lowercase English alphabet letters, along with a method that traverses all nodes and prints their letters on a single line separated by spaces.”

He further adds

Hint #1: If your first instinct was to create your new data types as a struct, it shows you’re a sound Swift developer. Sadly, I’m afraid that approach won’t work here because structs can’t have stored properties that reference themselves.

However in John Sundell's article Picking the right data structure in Swift he implements it as a value type

Let’s start by declaring a List struct, which will keep track of the first and last nodes within our list. We’ll make both of those properties read-only outside of our type, to be able to ensure data consistency:

struct List<Value> {
    private(set) var firstNode: Node?
    private(set) var lastNode: Node?
}

extension List {
    class Node {
        var value: Value
        fileprivate(set) weak var previous: Node?
        fileprivate(set) var next: Node?

        init(value: Value) {
            self.value = value
        }
    }
}

Is this a mistake on Sundell's part?

#2

i believe he is referring to the List.Node type, which is a class.

#3

It should be noted that while the List type is a struct, it isn't a value type. Whether a type is a value or a reference type is more complex than simply whether the outer layer is a class or a struct, but instead it's about its semantics. In this case, mutations to two copies of a List are reflected in both values, so the semantics of the type are referential, even though the outer type is a struct.

As an example, you can take John Sundell's List type and do this:

var x = List<Int>()
x.append(1)
let node2 = x.append(2)
x.append(3)

var y = x
x.remove(node2)
print(Array(y))

In this example, I mutated var x, but the mutation is visible through the copy made before the mutation. This is an example of reference semantics in action.

5 Likes