Linked Lists in Swift (3)

This is my third post about linked lists in Swift. In the previous post we’ve made our linked list a little bit more „Swifty“. Today I want to introduce some more convenient methods to make life easier.

One thing I was missing from the original developers is an easy way to insert a new node before or after a given one. This is one of the main reasons for me to use linked lists at all. Of course, you can remember the index in the list of the given node and insert a new node at or before this index but that is ugly and inefficient for long lists. The node itself knows its neighbours, so its easy to implement these methods.

We just have to check if we want to insert before the first node in the list or after the last one. We have implemented the necessary methods already. Now we can see the advantage of choosing the node as the iterator element since we can insert new nodes within a for-loop:

In this example I have searched the list for the second item and inserted new nodes before and after that. The loop is not disturbed by these operations:

Nice, isn’t it?


The second thing I want to add is a method to return the index of a given node in the list:

We just loop over the whole list until we find the supplied node. Notice that we have to use the identity operator (===) here since we do not want to test against equality but against identity. If we  do not find the node we return nil. Does it work?

Yes, looks like:


My third idea for today is the possibility of removing a node from its list without referencing the list itself. At some point it may be necessary to remove a node without knowing explicitly in which list it is stored (i.e. if you have several lists of the same type). This makes it necessary to store the list in the node:

Also, we have to modify the insert methods of the linked list where we create the nodes:

And now we can implement our new method in the Node class:

By preparing this post I stumbled over a problem here. Although everything looks easy and correct it crashes in the example playground:

error: Execution was interrupted, reason: EXC_BAD_ACCESS (code=2, address=0x7ffee70a6fa0).

 

This problem is present only in the playground (Xcode 9.2) and not in a real project. By debugging a little bit I pinned it down to the extension with the CustomStringConvertible protocol. Removing this protocol from our linked list lets the problem vanish:

„Stranger and stranger“ as Alice would say. So, we have to use the description directly for the time being.

Update: With the release of Xcode 10.1 this problem disappeared. So, from now on it seems to be safe to make the LinkedList to be CustomStringConvertible and to print the list directly (without referencing the description).

Now we can test that as well:

with the result:

Again, we can modify the list without disturbing the loop.


The last thing for today is the implementation of an endless loop or a ring. Sometimes it’s necessary to start in the middle of the list and loop through it by continuing at the top when the bottom is reached (maybe even several times or endlessly). Our Node has a property which points to the next node in the list; we would need a (computed) property which points to the next node in the list or the first one if we reached the end. Here it is:

As you can see, for this we need the pointer to the list in the node again. Let’s test that as well:

with the result:

You see, we looped over the end of list and continued at the top.

That’s it for today. Here is the playground of our enhanced linked list.

The next and last post of this series will cover the following objective:

  1. Serialising

So stay tuned.

Schreibe einen Kommentar

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