In this post we will go over basic usage of generics in Swift by building a simple singly linked list.
Introduction to generics
Generic code is code where the functionality is described without using specific types. Meaning, the code can use any types what match with constraints (if there are any). It’s best to take a look on an example. See how separate functions can be replaced with a single implementation.
| // non-generic functions | |
| func someFunctionInt(_ values: [Int]) {} | |
| func someFunctionString(_ values: [String]) {} | |
| // generic | |
| func someFunction<T>(_ values: [T]) {} | |
| // non-generic functions | |
| someFunctionInt([1, 2, 3]) | |
| someFunctionString(["a", "b", "c"]) | |
| // generic | |
| someFunction([1, 2, 3]) | |
| someFunction(["a", "b", "c"]) | |
| // Type constraint | |
| func someSortFunction<T: Comparable>(_ values: [T]) -> [T] { | |
| return values.sorted() | |
| } | |
| let sorted = someSortFunction([3, 7, 5, 1]) | |
| print(sorted) // [1, 3, 5, 7] |
Generic implementation defines a placeholder for a type (in angle brackets), in those examples T was used (can be something else but it is the most common placeholder). If multiple type placeholders are needed, placeholders are separated with commas. In addition, it is possible to constrain the type, for example, requiring the type to conform to comparable protocol allowing to use comparisons in the generic function’s implementation. It’s the bare minimal knowledge required for getting started with generics. There is a lot more about it.
Singly linked list
Singly linked list is a data structure where every node knows about the next node, but not about the preceding node. The benefit of such data structure is efficiency when inserting and removing nodes. On the other hand it does not allow random access of nodes.
Defining a generic linked list is quite easy. First we need a LinkedList struct storing the first node. Node stores a value and the next node. When inserting or removing nodes from the list, next property is updated. Therefore node needs to have reference semantics for making sure all the objects are pointing at the correct next object (in value semantics new instances would be created when mutating the next property and it would break the continuity of the list).
| struct LinkedList<T> { | |
| final class Node<T> { | |
| let value: T | |
| init(_ value: T, next: Node<T>? = nil) { | |
| self.value = value | |
| self.next = next | |
| } | |
| var next: Node<T>? = nil | |
| } | |
| var first: Node<T>? = nil | |
| } |
As said before, inserting and removing nodes is just a matter of updating the next properties. Therefore when inserting a node, its next node is the current node’s next node and the current node’s next node is the inserted node.
| extension LinkedList { | |
| @discardableResult func insert<T>(_ node: Node<T>, after: Node<T>) -> Node<T> { | |
| node.next = after.next | |
| after.next = node | |
| return node | |
| } | |
| @discardableResult mutating func prepend(_ node: Node<T>) -> Node<T> { | |
| node.next = first | |
| self.first = node | |
| return node | |
| } | |
| @discardableResult func remove(after node: LinkedList<T>.Node<T>) -> LinkedList<T>.Node<T>? { | |
| let removed = node.next | |
| node.next = node.next?.next | |
| return removed | |
| } | |
| } |
And finally, using generic linked list.
| print("Populating parking lot.") | |
| var parkingLot = LinkedList<String>() | |
| parkingLot.prepend(LinkedList.Node("Car")) | |
| let truck = parkingLot.prepend(LinkedList.Node("Truck")) | |
| parkingLot.insert(LinkedList.Node("Chopper"), after: truck) | |
| parkingLot.forEach(body: { print($0.value) }) | |
| print("Empty: \(parkingLot.isEmpty)") | |
| /* | |
| Populating parking lot. | |
| Truck | |
| Chopper | |
| Car | |
| Empty: false | |
| */ | |
| print("Rearranging parking lot.") | |
| parkingLot.remove(after: truck) | |
| parkingLot.forEach(body: { print($0.value) }) | |
| /* | |
| Rearranging parking lot. | |
| Truck | |
| Car | |
| */ | |
| print("Populating numbers.") | |
| var numbers = LinkedList<Int>() | |
| let first = numbers.prepend(LinkedList.Node(1)) | |
| numbers.insert(LinkedList.Node(2), after: first) | |
| numbers.forEach(body: { print($0.value) }) | |
| /* | |
| Populating numbers. | |
| 1 | |
| 2 | |
| */ |
Summary
In this post we took a quick look at how to write generic code and applied that knowledge on generic version of singly linked list. It should be noted that here we used only the basics of generics and for example the linked list implementation could also benefit from associated types allowing to replace Node with for example, Element.
Playground
References
Generics in Swift (Apple)
Linked lists (Wikipedia)
Augmented Code 