An algebraic data type is a type that’s the union of other data types. That is, it’s a type that may be one of several other types. Here’s how we would implement a linked list as an algebraic data type in Swift:

``````enum LinkedList<Element> {
case empty
indirect case node(data: Element, next: LinkedList)
}
``````

This defines an enum called `LinkedList` that might either be `.empty` or a `.node` that points to another `LinkedList`. There are three interesting things to note. The first is that we’ve created a generic data type, so the type of `Element` is declared by the consumer of `LinkedList`. The second is that the `.node` case uses `LinkedList` recursively, and must therefore be marked with `indirect`. The third is that since the `.empty` case has no parameters, the parenthesis may be omitted.

Here’s how we define instances of `LinkedList`:

``````let a: LinkedList<Int> = .empty
let b: LinkedList<Int> = .node(data: 1, next: .node(data: 2, next: .empty))
``````

To work with an algebraic data type, we deconstruct it using pattern matching. Here’s how we would print a `LinkedList`:

``````enum LinkedList<Element>: CustomStringConvertible {
'' // cases omitted for brevity
var description: String {
switch self {
case .empty:
return "(end)"
case let .node(data, next):
return "(data), (next.description)"
}
}
}

let b: LinkedList<Int> = .node(data: 1, next: .node(data: 2, next: .empty))

print("b: (b)") // => b: 1, 2, (end)
``````

We’ve implemented the `CustomStringConvertible` protocol so that we can use string interpolation to print `LinkedList` instances. While it is possible in Swift to pattern match using an `if case` statement, the `switch` is preferable because the compiler will warn us if we’ve forgotten to handle a case. This safety is one big advantage that algebraic data types have over their classical counterparts. In a traditionally implemented linked list, you would have to remember to check if the `next` pointer was `null` to know if you were at the end. This problem gets worse as the number of cases increase in more complex data structures, such as full binary range trees with sentinels.

Note that since the `description` instance variable only has a getter, we do not need to use the more verbose syntax:

``````var description = {
get {
// etc
}
set {
// etc
}
}
``````

Our print function was useful, but in order to do interesting things we need to be able to modify algebraic data types. Rather than mutate the existing data structure, we’ll return a new data structure that represents the result after the requested operation. Since we’re not going to mutate the original data structure, we’ll follow the Swift 3 naming convention of using a gerund for our methods. Here’s how we would add an `.inserting` method to `LinkedList`:

``````enum LinkedList<Element>: CustomStringConvertible {
// cases and "description" omitted for brevity
func inserting(e: Element) -> LinkedList<Element> {
switch self {
case .empty:
return .node(data: e, next: .empty)
case .node:
return .node(data: e, next: self)
}
}
}

let c = b.inserting(e: 0)
print("c: (c)") // => c: 0, 1, 2, (end)
``````

The key is that we’re returning a new `LinkedList` that represents the result after the insertion. Notice how in the `.node` case, we do not need to pattern match on `.node(data, next)` because `data` and `next` are not needed in order to construct the new `.node`; we can simply use `self` as the `next:` node.

Finally, let’s implement the classic “reverse a linked list” interview question using our algebraic data type:

``````enum LinkedList<Element>: CustomStringConvertible {
// cases, "description", and "insert" omitted for brevity
func appending(_ e: Element) -> LinkedList<Element> {
switch self {
case .empty:
return .node(data: e, next: .empty)
case let .node(oldData, next):
return .node(data: oldData, next: next.appending(e))
}
}

switch self {
case .empty:
return self
case let .node(data, next):
return next.reversed().appending(data)
}
}
}

print("reversed c: (c.reversed())") // => reversed c: 2, 1, 0, (end)
``````

I’ll leave it as an exercise to the reader to figure out what the running time for this algorithm is.

Here’s the Playground on GitHub