Understanding Singly Linked Lists and Their Functions
Linked lists are something we’ve all heard of, and for good reason: They serve as a base understanding for all other data structures. There are two different kinds of linked lists: Singly linked lists and Doubly linked lists. In this article, we’ll be discussing the former (and we’ll provide a brief comparison of both).
Before moving forward: An understanding of ES2015 JavaScript “Class” and “Instance Methods” syntax is required for this article. If you’ve never heard of or used JavaScript Classes, this information will be very hard to understand (as will many other data structures besides linked lists). If this is the case, do a bit of research and then come back! If you’ve got an understanding of this syntax, then let’s jump right in.
What is a singly linked list?
A singly linked list is a data structure that contains a head, tail, and length property (the last is optional, although it makes things much easier).
Linked lists consist of something called nodes. A node is a piece of data that has a value as well as a pointer to another node or null. The head of a linked list is the very first node, and the tail is the very last node, which will always point to null.
A singly linked list is a data structure that consists of nodes. Each node has a value and a pointer that points to the next node, or null once it gets to the end.
The difference between a singly linked list and a doubly linked list is as follows: In a singly linked list, each node only points the node in front of it (or next in line). In a doubly linked list, each node also has a pointer that references the one behind it. As such, singly linked lists provide an easier base understanding of the linked list data structure as a whole.
It’s important to mention that, unlike an array, linked lists do not have built-in indexes. This means that in order to find a specific point in the linked list, you need to start at the beginning and traverse through each node, one by one, until you find what you’re looking for.
Here’s an interesting analogy I once heard: A linked list is like a skyscraper with no elevators. To get to the floor you’re looking for, you need to climb up the stairs one level at a time. In an array, you can press a button that takes you right to the floor you need to get to.
You’re probably thinking: “Linked lists sound very complicated and inefficient, which would I ever use them?” Well, let’s talk about it.
Why/when would I use a singly linked list?
There are a few different times linked lists shine above arrays, and vice-versa. It depends on what exactly you’ll be doing with the data.
Inserting or deleting data at the beginning of a list
Remember that arrays come with built-in indexes. This means that if an array has a thousand items in it and we need to place an item at the very beginning of an array, every single index in the entire array needs to be shifted to the right and incremented (which means we would have an O(n) here, but we will come back to the Big O of arrays vs linked lists at the end of this article).
In a linked list, adding data to the beginning is extremely simple and efficient. You just need to tell the new piece of data to point to the head, and then assign that piece of data to be the new head. No re-indexing required.
Inserting or deleting data somewhere in the middle of a list
Same as the reason above, insertion and deletion of data in a linked list doesn’t require re-indexing the entire list, which makes it faster than inserting or deleting data in an array (unless of course you’re adding or deleting something from the very end of an array, which would not require any re-indexing.)
Linked lists are very useful when working with insertion and deletion of data. Arrays are more useful when random access is required.
Okay, now that we have a brief understanding of what singly linked lists are and the rationale behind using them. Let’s create one and build out its functions.
Important: There are many ways of building out any of these functions. These are all just one way to do each. So if you’ve seen them done differently elsewhere, neither way is wrong. But if you’ve found a better solution to any of them, feel free to share in the comments!
Creating a singly linked list
To create a singly linked list, we will need to start by creating two classes: Node and SinglyLinkedList
Since our nodes consist of some sort of value as well as a pointer to the next one, it needs to contain a val attribute as well as a next attribute. next will start by being equal to null.
Remember that our singly linked list needs to include a head and a tail to specify where it begins and ends. We will also add a length property to make some of our functions easier to implement. The head and tail will start as null.
Adding to the end of the list
To add to the end of the list, all we need to do is create a new node and set the current tail’s next property to be the new node, then make the new node the tail.
Don’t forget the edge case: if there’s no head (i.e. the list doesn’t exist yet), set the head and the tail to be the new node. Increment the length by one and return the list.
Removing from the end of the list
For this, we will need to loop through the list until we find the tail, then set the next value of the node directly before the tail to be null, and set that node to be the new tail. Then decrement the length of the list by one and return the value of the node that was removed (remember you’ll need to save this variable ahead of time in order to return it).
Edge cases: If there’s no head, return undefined; and if the length of the list is zero AFTER removing the node, make sure the head and the tail are set back to null.
Removing from the beginning of the list
Removing a node from the beginning of a singly linked list is very simple. All we need to do is set the head to be the next value of whatever the current head is, then decrement the length by one and return the old head (remember to save the original head as a variable so you can return it.)
Edge cases: The edge cases for shift() are very similar to pop(). If there’s no head, return undefined. If the length of the list is zero AFTER removing the head, make sure the tail is set back to null (the head will already be set to null in this case, but the tail will be set to Node by default. Setting it to null prevents this from happening).
Add to the beginning of the list
Adding to the beginning of a singly linked list is also very easy. We just need to create a new node and set its next value to be the current head, assign it to be the new head, increment the list by one, and then return the list.
Edge case: If the head is currently null, then that means what we’re unshifting is going to be the only value in the list. Therefore it will need to be set to be the head as well as the tail.
Retrieve a node by its position in the list
Remember, linked lists don’t have indexes for their values like arrays! So we will need to do some extra work here. Our function will be passed an index, so we will need to create some sort of counter variable that we can use to loop through the list (starting at the head) while it’s less than the index. Once we reach the index that’s been passed in, we return that node.
Edge case: If the passed in index is less than zero OR if it’s greater than or equal to the length of the list, return null (or -1, undefined, etc. (something bad)).
Change the value of a node given its position in the list (and the new value)
Since we’ve already created our get function, we can use this to find the node at the given index. We can set this node to a variable easily since our get function returns the found node. Once we’ve found the node, all we need to do is set its value to the passed in value, and then return true. If it doesn’t find a node, return false.
Edge case: The get function we’ve defined will already take care of invalid indexes. This allows our set function to be very concise.
Add a new node to the list at a specified position
This function is a bit tricky. First, we will need to create our new node given the passed in value. Now, in order for us to insert our node somewhere, we will need to find whatever node is directly before the passed in index, and set its next value to be the new node. After this, we need to set our new node’s next value to be what the found node’s next used to be (I know, a lot of “nexts”). This means we will need to make sure we’ve saved this as a variable ahead of time. Once we’ve added the new node, increment the length by one and return true.
But wait! IF our function is passing us an index of zero or an index equal to the length of the list, we’ve already written functions for these! Use your unshift or push function in these cases, and pass them the given value.
Edge cases: If the given index is less than zero or greater than the length of the list (it doesn’t matter if it’s EQUAL to the length of the list in this case since we can just add the new node to the end), return false. Also, we’d like this function to ONLY return true or false. Right now, if we ended up using our unshift or push methods here, it would return the whole list. This isn’t the end of the world, but as programmers we like to be consistent. An easy workaround here is to make our method return true if either of these methods are used.
Remove a new node from the list at a specified position
To remove a node, all we need to do is find the node previous to the index passed in, and then set its next to be the next of the next node (the one we’re removing). All we’ve done here is severed the link between the previous node and the one that used to be after it, by making the previous node’s next the one two nexts ahead of it (getting tired of reading the word “next” yet?).
Once this is done, decrement the length by one and return the removed node (this means you’ll need to have saved it to a variable).
But wait! If the passed in index is equal to the length of the list minus one, or if it equals zero, we’ve already written methods for these! In these cases, return your pop() or shift() methods, respectively.
Edge case: If the passed in index is less than zero OR greater than or equal to the length of the list, return null.
Reversing a singly linked list in place
Reversing a singly linked list in place (“in place” meaning by not making a copy of it) is a classic problem and likewise the hardest to explain. There are also many ways to do it. Here’s how we will solve it (this is an example of an iterative solution, there are also recursive solutions that work as well):
First, swap the head and the tail, and save the tail as a new variable (often called curr). Then create a variable next and a variable prev. prev should start as null. Next, loop through the list. Set next to be the next property of whatever curr is at the time (it starts as the tail as defined above). Then, set the next property of the curr node to be the prev variable we defined. Now, set prev equal to curr, and curr equal to next.
Once this is all done, return the updated list.
Feeling extremely confused? Understandable. Take a look at the solution below and try to understand what’s going on. If you’re still having trouble, I’ve provided a helpful gif under the solution that might help.
If you’re having a hard time understanding this, take a look at the gif below from geeksforgeeks.org.
Big O of Singly Linked Lists vs. Arrays
Whew! Still with me? Let’s take a second to go over the Big O Notation of singly linked lists vs arrays.
Insertion: O(1)
Singly linked lists are extremely useful for inserting values at the beginning of a set of data. It doesn’t require any re-indexing like an array does, and therefore takes constant time.
Removal: O(1) or O(n)
If we’re removing from the beginning of a singly linked list, this is extremely efficient and takes constant time. However, if we’re removing from the very end, we need to find the item right before the tail, which involves iterating through the entire list.
Searching: O(n)
If we’re looking for a specific value in a singly linked list, this takes linear time due to the necessity of starting at the beginning and looking through the whole list until we find what we’re looking for. This is similar to arrays, although not totally an equal comparison.
Accessing: O(n)
As discussed at the beginning of this article, accessing a specific index of a singly linked list is not nearly as efficient as an array due to not having built-in “random access” as an array does. Accessing the thousandth element in an array is very simple and takes constant time since every value is indexed, accessing the thousandth item in a singly linked list is much slower and takes linear time due to the reasons discussed above.
In this article, we covered what singly linked lists are/how they differ from doubly linked lists as well as arrays, what they’re useful for and when an array might be better, common functions of singly linked lists, and the Big O of their use cases.
We’ve covered a lot in this article. If it seems like a lot, take a while to digest the information and come back and review as much as you need to.
Got any solutions that are better than the ones provided here? Feel free to share them in the comments!
