A Link to the Past: Linked Lists in Swift
In the programming world, we often hear about Linked Lists. In my line of work, I pretty much never see them in our codebase (I’m also partially to blame for that). With Swift, I think part of that comes from them not being a built in data structure, so in order to use one, you have to implement your own custom class. Creating custom class models is a very common thing to do, but usually it’s to represent something that you’re software uses or keeps track of, like a user.
Since you’d have to create a Linked List manually, it’s not done that often and since it’s not done that often, it doesn’t come to mind often as a data structure of choice when you can use an array, set, or dictionary that is built-in to Swift. but, we’re going to learn how to make a Linked List now.
What is it?
A Linked List is a sequence of related items, called nodes, containing the same data types. There are two main types of linked lists:
- Singly-linked list — This is like a one-way city street. Let’s say that each block is a node. Each block is connected to the one in front of it, but as you pass each block, you can’t go back to the previous block. If you tried to drive the wrong way on a one-way, you would crash. It’s not allowed. You can only move forward to the next block (node). The only way to get back to a node that you have already passed is to start over all the way from the beginning.
- Doubly-linked list — This is, as you might guess, like a two-way city street. Now, if you decided you wanted to go back a block, you’d just have to flip a u-turn and go back to where you just came from. It’s easy.
An important thing to note is that you are going linearly, in a line. When driving on the block, I can’t just magically skip a block and get to a block that’s after the immediately next block on the street (unless you can fly). You have to go to each block (node) in order.
Alright, so let’s get into the details of a node.
On both types of linked list nodes, you will have two properties: a value and a next pointer. The value is the data the node contains, like the building number on each block. The next pointer is simply the next node in the list, or the next block on the street. In a doubly-linked list you will also have a previous pointer that refers to the node you were just at, or the last block you passed on the street. Here’s the code:
Explanation time. We establish the node of type T, which is a generic type in Swift. That lets us later use it to store any type we desire. The next node is optional because you might be at the last node in the list in which case it won’t yet have a next node. In the Doubly-linked node class, we made the optional previous value a weak var. Let’s say Node A is followed by Node B and therefore references Node B. Node B is also referencing Node A though as its previous. In order to prevent a retain cycle* from occurring by having two strong references to each other, we make previous have a weak reference. If you’re unsure of what the init() function does, basically it makes it so when you create a new node, var head = node(value: 4), you can pass in that value and the init function will know, “Oh, this thing they passed into the function is the value, I’ll make sure that the value property is set to 4.” Also, since we are using the generic <T> type, Swift will infer the actual data type, in this case Int. Then if I ask for head.value, it will return 4.
*Quick aside: what do I mean by retain cycle and references? This is best answered in its entirety in a completely different post. But basically, let’s say a node is in memory. It will remain in memory as long as something is using it. When nothing is using that node anymore, Swift has something called ARC (automatic reference counting) that will deallocate that node from memory, to free that little bit of memory up. If something is still referencing it that you aren’t expecting, it will remain in memory. If this happens with multiple items, your app will end up hogging a lot of memory. No bueno. It’s okay if you don’t understand this right now. Patience, young one.
The List
Alright now we’re going to implement each section of the list in code and talk about it.
First off, we create the class with the same generic <T> type. We’re going to give it a few properties, those being head, tail, isEmpty, first, and last. Head is referring to the first node in the list, tail is the last node. The other three properties are computed properties, which means they don’t store an actual property. Instead they return a calculated value or another, possibly private, property value. The isEmpty property lets us know if there’s anything in the list. If head is empty, then that means that no other nodes have been created, because the first node created will be made the head initially.
The first and last properties are there to tell you what the head and tail nodes are. But why don’t we just access the head and tail nodes directly? Why are they marked private? Well, we don’t really want a user to be able to modify the values of head and tail independently. We’d rather modify those ourselves from within the functions we create in the LinkedList. But, with first and last, at least they can still see what those properties contain. So we just created the plans for a street, essentially, but it doesn’t have any blocks yet.
Here’s how we actually create the list in our code:
Line-by-line, we first instantiate a list and we pass in the data type, String in this case. The parentheses () are what basically tells our class to create an instance for us. Now once we created it, we check its isEmpty property, which should be true, since we have not added anything. It does return true. If that’s true, then if we check our first and last properties, they should be nil. And we can see they are.
Next we move onto the first function.
Append
This function is used when we want to add a new node onto the end of the list. It’s like building a new block at the end of the street and extending the street a little further. Conceptually, it’s basically the same thing as an array.append function. All the user has to do is send in a value. Again, it’s generic but it will be the same type as the LinkedList we created. Up above, we created a LinkedList of type String. So when we go to append and create newNode, it will require that the value we pass in be of type String . So we create the node that we will be appending and then first check to see if we have a tail node in the LinkedList currently by checking last . If it does have a tail then we proceed to set the newNode.previous to be the last node, then we set tailNode.next to be the newNode. Its next property was previously nil since it had been the tail. We don’t assign a next property on the newNode since it is the last node in the list and there isn’t another one to which it can point. In the else portion, if we do not have a tail node, then that also means we won’t have a head node, since they get created at the same time, which means that our LinkedList had been empty previously. Regardless of whether we go into the if or the else block, we will end up assigning the newNode as the new tail.
Here’s how we use this in real practice:
We first append, with a required string value of "I". After doing that we can check to see if it actually got added with isEmpty. That returns false, since there is one node in there. When we get list.first it gives us Node<String>. What good is that? It doesn’t tell you anything, does it? Well for one, it lets you know that a node does indeed exist there, which is good. But you have to call the value property directly to see their values, which we do on the next two lines. Since there is only one node in the list currently, first and last are going to be the same node. The reason why we have the question mark in list.first?.value and list.last?.value is because when we call for those properties, we don’t actually know if they exist or are nil and so we have to unwrap that optional property. This helps bad crashes occur in Swift, allowing you to “safely unwrap the optional”, as they say. In fact, you won’t even be able to build without unwrapping. If you recall, when we created our head and tail in our properties, we set them to optional. This way we can create a LinkedList without any nodes.
Retrieving NodeAt an Index
Sometimes you might want to know which node is at a certain index. This function takes in an index of Int data type. It then possibly returns a node, if it finds it. We start it out with a conditional if to make sure they gave us a valid input of a positive integer. Then, we prepare for a loop. We set a node to the head, or the beginning of the list, and set a counter variable, i, to the value of the index parameter. The loop then starts and continues to run until the next node is nil. Within the loop it first checks if i is 0. This is our success check, because it means that we’ve arrived at the desired node, which we then return. But how did I get down to zero? We see this on the next line. If i is greater than zero, then we haven’t passed through enough nodes yet so we decrease i by 1 and progress to the next node in the list. If index is less than 0 or if we reach the end of the list before our i gets to 0, then we return nil. The node was not found. Now let’s take a look at this in practice.
We first append four more items, to make a list containing each of the words in “I Like To Drink Juice”. Why those words? Because I like juice, sue me. After appending, we double check the first and last values again to verify that they are no longer pointing to the same node. The first value should remain the same, and we see that it is, and last is the most recently appended word, “Juice”. We then get the node at the third index, which would be the fourth node in the list. Then, we play around with that node a bit, first checking that its value is correct (it is, with “Drink”). From there, we see how we can access different nodes in the list, just by using each node’s previous and next properties.
Insert
Let’s say you wanted to insert an item into the middle of the list and not just append it to the end. We do this by taking in two parameters: the value of the node to create, and the index of the location where we want to insert the node.
Side note, you’ll notice that we have
at index: Intinstead of justindex: Int. This is a nice thing that Swift allows to make things a little more understandable. When calling the function it will look likelist.insert(value: “Cherry", at: 3). Syntactic sugar.
We return the node afterwards mainly for the sake of proof that it was indeed added. We first will create a new node with the passed-in value. Then we check the index. If it’s 0, guess what the means? It means we’ll be putting it at the very front of the list, which means it will be the new head. We do this by first setting the newNode’s next pointer to the head. Then we set the head’s previous pointer, which was previously nil, to the newNode. Finally we set the newNode as the head. If the index is not 0, then we move into the else block and do something very similar to our nodeAt(index: Int) function. This is because it is essentially the same operation, with a little more added in there. We set a currentNode pointer to the head and a counter equal to the index parameter. Then we loop until i == 1. We could have chosen to loop until i == 0, it just would have changed our logic slightly. I just chose 1 since it is one less loop. Once our i counter gets to 1, it means the next node in the list will be at our target index. So we set the currentNode’s next node (the node at i == 0) to have a previous pointer to the newNode. Then we set the newNode to have its next point to currentNode’s next. We set newNode’s previous to be the currentNode and finally we set currentNode’s new next to be the newNode. Again, if we didn’t reach the index, then we return nil. We’ll talk about remove next and then see an example with both of them together.
Remove
We use remove to take a node out of the list and then re-establish the correct links. You pass in the node you want to remove and we’ll return the value of the node that got removed. The nice thing about passing in the node directly, is that we don’t have to loop through the list to find it, which as you have seen with some of the other functions, can be a bit of a pain, and a cause for slow lookups. With the node that’s passed in, we have access to all of that node’s properties. We create references to the next and previous properties. Then we check if the prev is nil, aka, if the node passed in is the head node. If it does have a previous node, then we set that node’s next to be the node-to-be-removed’s (NTBR) next. If the NTBR doesn’t have a previous then the new head will just be next. We set the next’s previous node to be the prev node. Then we do the same sort of check we just did, but this time to see if it is the tail node, by seeing if the NTBR’s next is nil. If it is, the prev becomes the new tail. With the next and previous nodes of the NTBR now pointing to each other, we can safely set the next and previous pointers to nil, return the node’s value and it will then cease to exist in memory, forever.
But what if you just want to empty out the list completely? This is super easy. You just set the head and tail nodes to nil. With the two critical references of the beginning and end of the list disappearing, the rest of the list no longer has anything to hold onto to keep it in existence and therefore ceases to exist in memory. This happens because while the rest of the nodes in the list are referencing each other, there is nothing outside of them that is actually referencing them, so there’s really no way to access them, therefore they get removed from memory.
Let’s see some live examples.
We first remove the fourthNode we had previously created, that had the value of “Drink”. After removing, we then reassign that fourthNode variable to the new node at that same third index. We check the value and it has changed! It’s now “Juice”. But wait, wasn’t that the last word in the list before? Sure enough, if we check the next value, it is nil. This is still the last node in the list, its just one node shorter. We then get the description, which is what we’ll talk about in just a bit. But it shows us that our list now just contains I, Like, To, Juice. Now we are going to add Drink back in. We call our insert function, and reassign it to that index 3 again after the insertion. We check its value and sure enough it is back to being “Drink”. We check our full list and it is I, Like, To, Drink, Juice once again.
Printing Out Your List
In that last bit we called a new property, description, that gave us a printed string representation of our list. This is not something that just comes built-in. However, Swift has a cool protocol that we can follow called CustomStringConvertible. We create an extension of LinkedList, which extends our already established functionality a little further, and we create another computed property called description. We then start a string with an opening bracket and then, starting at the head node, we loop through and append each node’s value onto the string. Then we close the bracket and return the string at the end. We do this since it would be quite handy to be able to easily know what is inside your list without having to manually write this loop code every time.
We saw how description worked previously, now we remove everything from our list with removeAll(). We check description and it’s empty. We check isEmpty and it returns true. We look for the first node in our list and it returns nil since there are no nodes in the list. We’ve successfully brought a LinkedList into this world, played with it a bit, and promptly obliterated it.
The Full Thing
Here’s what the whole thing looks like together.
Up Next
Well, that detailed explanation wraps up our basic Linked List with it’s functions. If it doesn’t make sense immediately, don’t worry. Just go through it a couple more times and practice on your own, and it will start to make sense. Stay tuned for a later post discussing some common problems related to Linked Lists and how to solve them. Let me know what you think of this post in the comments below!
