Singly linked list with generics in Swift

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.

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).

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.

And finally, using generic linked list.

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

SinglyLinkedList (GitHub)

References

Generics in Swift (Apple)
Linked lists (Wikipedia)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s