Build Linked List from Scratch
I watched a video about building a Linked List from scratch, but there was something bothering me. After talking to a friend of mine, I finally found what kept me up whole night. As one of those having little background computer science and trying to study data structures and algorithm, I found it not easy to understand. There might be some blind spots to us, so I think it’s worth writing it down to help those who may have the some questions. Without further ado, let’s get started.
One concept you need to remember is “pass by reference”. I’m not going to talk too much about this concept. I will just briefly explain it.
When you create a new object of a class, the object takes up some space and is located at somewhere in the memory. When you assign this new object to another variable, this variable doesn’t make a copy of the new object and store the data. Instead, this variable points to the same new object located in memory.
Let’s try to build a Linked List class from scratch using Swift (In fact, we can build a Linked List using any language). This Linked List class includes some methods, such as addLast(), addFirst(), indexOf(), contains(), removeFirst(), removeLast(), and size().
First, let’s create a new playground in Xcode. Generally, objects that are linked are named “node”, so let’s create a node class first.
The node class contains two properties. One is “value”, which stores our integer data, and the other is “next”, which points to the next node.
Next, we create a LinkedList class.
The LinkedList class contains two basic properties. One is first, which is used to track which node is the first node, and the other is last, which is used to track which node is the last node. In addition, we declare one more property, called “count”. This property changes according to the size of a LinkedList object. This property may come in handy afterwards.
1. addLast() method adds a node to the last position of the LinkedList object.
Let’s start with creating a addLast() method in the LinkedList class. Every time we call this method, we create a new node object. We need to check if this LinkedList is empty. I use the “value” property of “first”to check it. If the “value” property is equal to nil, then we assign the new node object to “first” and “last”. If the “value” property is equal to nil, which means the LinkedList is not empty, then we need to replace the currently last node “last” with our new node object. We assigne the new node object to the “next” property of “last”, and then assign the new node object to “last”. The corresponding code is as follows.
Well, everything seems to make sense. However, when I looked into lines 25 and 26, something didn’t add up. What??? You just assigned the new node object to the “next” property of “last”, and then you also assigned the new node object to “last”. Since the “next” property of the new node object was nil, didn’t it just set the “next” property of “last” to nil again??, and the data of the original “last” just went missing. This is where “pass by value” concept comes in.
Let’s walk it through start with an empty LinkedList. We call addLast() method for the first time. We got a new node object of “New1” . Please see the following drawings, where dash arrows represent “reference”.
Since the LinkedList is empty, we assign “New1” to “first” and “last”. This is where “pass by reference” comes in. Both “first” and “last” reference the same object, “New1".
We call addLast() method the second time. We got a new node object of “New2” at the lower right corner.
We assign “New2” to the “next” property of “last”. As we said in the beginning, when you assign an object to multiple variables, the variables don’t make copies of it. Instead, the variables just reference the object. Therefore, if a value of one of the variables changes, then it changes the value of object, thereby changing the values of the other variables as well. As a result, this actually assigns “New2” to the “next” property of “New1”, making the “next” property of “New1” point to “New2”. Therefore, the “next” property of “first” is set to “New2”, as well.
And then we assign “New2” to “last”, making “last” turn to reference “New2”, which is currently our last node. According to the graph, it is the actual “New1” and “New2” that get connected. Now, we successfully connect a new node to the last node.
2. addFirst() method adds a node to the first position of the LinkedList object.
This one is pretty much the same as addLast(), so I will not talk too much about it. Let’s just see the code directly. In addition, if you are having a hard time understanding why this code can work, you can draw some pictures as I did to help you figure it out.
3. indexOf() method finds where the input data is located.
4. contains() method tells you if the input data is contained in the LinkedList object. At first, I wrote down the code below, and it worked properly.
However, the video provided a different way, which I found very brilliant. It used indexOf() method directly. When indexOf() method returns -1, it means the input data doesn’t exist in the LinkedList. When indexOf() method returns anything except -1, it means the input data exists in the LinkedList.
Therefore, when indexOf() method is not equal to -1, it is true, so contains() method returns true. On the contrary, when indexOf() method is equal to -1, it is false, so contains() method returns false. Instead of writing a bunch of code, you can write one line of code and save time simply by implementing indexOf() method.
5. removeFirst() method removes the first item.
6. removeLast() method removes the last item.
7. size() method tells you how many items are contained. At first, I also wrote a bunch of code to iterate over each item, and then get the result. It is okay if the LinkedList doesn’t contain a lot of items. However, if the LinkedList contains millions of items, it may be very inefficient. The time complexity is O(n).
As a result, the video provided a cleverer way. Remember that we used “count” to keep track of the size of the LinkedList, and that we said it may come in handy. This is where it comes in. We can simply use the count property to achieve the same goal, but more efficiently. In this case, the time complexity is O(1).
