Linked Lists in Swift (1)

This is the first post of my upcoming series devoted to linked lists. I like this data structure very much because of its elegance and efficiency in situations where you have to insert and remove objects quite often and randomly. Unfortunately there is no standard data type „Linked List“ in Swift, so we have to build one by ourself. That’s not too difficult and there are quite a few example implementations in the web (e.g. from Chris Pilcher or Hugo Tunius). I’ll take these as a starting point and add some of my own thinkings and optimisations.

Let’s start with the nodes. We want to store objects of arbitrary type. It is convenient to wrap these objects in our own data type which also holds the references to the previous and next objects in the list. There is one important word in the sentence above: „reference“. We need to hold a reference to the neighbouring objects, not the objects themselves. So we have to use a class for the wrapper and not a struct. In Swift structs are value types and putting the neighbours of the same type in a struct would cause a disastrous recursion, so the compiler forbids that. But enough of the preamble, let’s look at the code:

That doesn’t look too complicated, does it? Since we want to store objects of arbitrary type we have to use generics. The pointers to the previous and next objects in the list may be nil so we make them optionals. And removing one node should not lead to a dead lock of referencing so we have to make one of these pointers weak. The init is also very simple, we just store the supplied object (or a reference to it if its type is a class).

OK, let’s turn to the linked list itself. Here is the mere trivial part:

We keep references to the first and the last node of the list; since the list may be empty they have to be optionals. And we allow ourself a counter to the number of nodes in the list. That is not strictly necessary but it speeds up some operations. Finally we have some computed properties.

And now the more interesting methods:

These methods are quite straightforward and should be easy to understand. Some words about the remove method: Since we do not want to keep references of possibly later deleted nodes we have to clear the pointers to the previous and next nodes of the unlinked node. And, for convenience we give the original object back to the caller if we remove/unlink a node. For the insertion of nodes we use a private helper method to get the adjacent nodes of a given index; maybe we can use that for other purposes later as well.

And that’s it. We have implemented the main functionality of a linked list. Just let us add a description property to print out the linked list prettily:

Now its time to make some tests:

with the result:

You see it works as expected. Here is the playground of our achievements so far.

The next posts of this series will cover the following objectives:

  1. More Swifty features (i.e. iterators and index)
  2. Some more convenience methods
  3. Serialising

So stay tuned.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.