Data Structures Part 5: Linked Lists
Hello there! We are almost through all of the data structures that we will learn together! Today’s topic is…linked list! These data structures can be pretty tricky to wrap your head around, so we are going to dissect as much as we can to ensure you have a good foundation to build on. I also encourage you to check out this resource to get amazing visual representations of what’s really going on behind the scenes of a linked list. By the end of this article, I hope you will have a better understanding of linked lists, how to create them from scratch, and most importantly how to solve problems implementing this new data structure. Let’s hop into it shall we?
What is a Linked List?
A linked list is another type of linear data structure that consists of nodes and pointers. Each node consists of a reference that points to the proceeding node. A popular visual representation of a linked list would be a conga line! Each person has their arms extended to touch the shoulders of the person in front of them. Unlike some of our previous data structures that come pre-built into JavaScript, linked lists are not, which means we will have the opportunity to build one from scratch! Let’s first start by covering all the anatomy of a linked list.
Components of a Linked List
A linked list is made up of four main components:
1. Node — an element within a linked list that can hold several types of data such as numbers, strings, characters, etc.
2. Pointer — a reference to the next node in memory (nodes can be placed anywhere in memory, linked lists do not store data in an indexed order like arrays)
3. Head — the first node within a linked list
4. Tail — the last node within a linked list that then points to a null value
Types of Linked Lists
There are two main types of linked list, each built slightly different to accommodate different use cases:
- Singly Linked List
A singly linked list has pointers that only reference the next node in the list ( notice the arrows flow in one direction).
2. Doubly Linked List
A doubly linked list has pointers that reference the next node as well as the previous node (notice the arrows flow in both directions).
Building from Scratch
First we are going to initiate a class called “LinkedList” that contains a length property and head property. We are also going to initialize a node class that contains an element property (representing the current element) and a next property (representing the next node). We then have two simple methods “head”, and “size”. The “head” method is going to return the value of the head, which is the value at the front of the linked list at any given time. The “size” method is simply going to return the length of the linked list. So far so good!
This LinkedList class is going to have three more methods: add, prepend and delete. The “add” method will be taking in an element parameter and we will be creating a new node passing in that parameter as an argument. Then we will check if there is a head node in the list, if there is not a head node already, then we will assign our new node as the head. If there is an existing head node, then we will assign a “current” value to the head. While the next node in the list does not have a value of null (meaning we haven’t reached the tail node yet), keep moving down the linked list. Once we have gotten to the end of the linked list, our current.next node will be assigned to the new node that we created. Lastly, we increment the length of the linked list to account for the element just added.
Now that we have added a new node to the end of our linked list, we also want to add to the beginning. With our “prepend” method, we will also initiate a new node that takes the element parameter as an argument. In this method we only want to reassign the current head to the new node we just created; so we are going to assign the newHead.next property to the current node in the head position and then assign the head property of the linked list to our newHead node.
Lastly, we want to delete a node from our linked list. Our “delete” method takes an element as a parameter. If our head node is equivalent to null, we will just return (this just means there is nothing in our linked list to delete). If our head node does exists, then we are going to check if the element we want to delete is in the head position of our list. If it is, we are just going to reassign the head position to the next node and return. Like our “add” method, while the next node does not have a value of null, keep moving through the list. We will keep moving until we have found the node before the element we want to delete. By stopping at the node before our selected node, we are just going to redirect our pointer to “skip over” it and connect to the node after it(current.next.next). Then we assign the current value to current.next.
And we have made it through! Linked lists can be difficult to visualize, again, Visualgo is an amazing additional resource to get a feel for the flow of each method we just covered.
Linked Lists and Big O Notation
You may have noticed by now that linked lists are very similar to arrays, and you would be correct in thinking so. However, they do have their differences. In an array, you are able to grab a specific value by using its index without having to iterate through to find it. Linked lists must be traversed in order to find a specific value since data is not stored in indexes. Due to this, a lookup method would have a time complexity of O(n). The same goes for the deletion, and insertion methods. We must traverse through the entire linked list in order to perform all of these at their worst case scenario. Prepending a node to the beginning of the list is a time complexity of O(1), which is pretty fast! We do not have to traverse or iterate through the rest of the linked list in order to update the indexes (since there are none). Appending a node to the end of the list has a time complexity of O(1) as well.
Exercises
Now that we’ve created a linked list from scratch, lets solve a problem taken from LeetCode. We are going to find the middle node of a linked list, if the linked list is an even number, then we will return the second middle number:
Our function “middleNode” is going to take the head of our linked list as a parameter. We are going to implement the “tortoise and hare” algorithm, otherwise known as the Floyd Algorithm to solve this problem. We are going to assign two pointers to the head value. Then, as long as the hare’s current value and the hare.next value does not equal null (meaning it has hit the end of our linked list); the hare node will move through the list twice as fast as the turtle node. Once the “hare” node hits a null, we will return the turtle. If the linked list consists of an odd number of nodes, the hare node will get to the end of the linked list without hitting the null value, and the turtle node will be exactly in the middle of the linked list. If the linked list consists of an even number of nodes, the hare node will stop before moving to the null value, while the turtle returns the second middle number.
And there you have it! We have solved a linked list problem in O(n) time, all while learning a little more about a popular algorithm!
Well done! And congratulations on finishing up on our fifth data structure! Linked lists can be very daunting to learn; however, I hope after this article, we were able to link some of the pieces together (yes…the pun was very intended). Thanks again for reading, and until next time…
💕👩🏾💻Happy Coding!👩🏾💻💕
