Data Structures and Algorithms ep 2. Linking things with Linked Lists part 1.
As always as an introduction, I’m a current coding bootcamp student, with about 4 weeks left in the program. We don’t cover Data structures and algorithms that much, but as software engineers, we all know that its pretty important when it comes to interviews. As always, I’ll be talking about whatever data structure, why it’s important, how to implement it and of course, covering a leetcode problem that involves it! I hope this helps, also this is how I understand how linked lists are and how to implement it and stuff.
Also, I don’t own the memes and the giphy that I used here! The only picture that I used that I made is the horribly drawn version of Linked List below, credits to whoever created the memes and stuff!
What are Linked Lists and why should I care about them?
Linked lists are considered to be the most basic data structure, and more often than not they are usually the first ones to be taught after arrays, when you finally take the deep dive into data structures and algorithms. A linked list has a series of nodes which contain a pointer to the next node of the series. So now what you’re probably asking is…what is a node?
A node is just an element of the list comprising of the data in the linked list and a reference to the next node.
So now you’re probably asking, when and where can I use these? You can implement two other data structures in these called Stacks and Queues along with other more advanced-ish data structures as well.
There are also many types of Linked Lists we have Singly, Doubly, and Circular. For this blog post I’ll be talking about Singly Linked Lists.
So before breaking things down further, let’s talk about another important thing we should know, what is the big O for a Linked List?
So Linked Lists are a linear data structure since its a series of nodes that point to the next element. With that being said, linked lists are very good at adding and removing various elements, while it is very slow to search and accessing elements. Since linked lists are a linear structure, trying to access a specific element is dependent on the size of the list which makes the Big O of searching + Accessing an element O(n). Whereas if we are adding a new node or an element to the linked list, the Big O would be O(1), if you are inserting it in the beginning of the list.
So how do I implement this?
For reference, you should be a little bit comfortable with classes in Javascript from here on out! :) But anyway, there are a couple things we can include when we create our Linked List a pop method, a push method, remove method and the last method I’m going to cover is reverse which is the leetcode question I wanna try out :).
As I mentioned earlier a linked list is made up of nodes! So the first thing to do is create a Node class.
class Node {
constructor(data) {
this.data = data
this.next = null
}
}So what’s happening here? We’re creating our Node class, the constructor method if you are unfamiliar with it initializes our node object within our node class, which will store the data. Next we set our next value to null. Why null? Because right now we have nothing.
Next we’re going to define our Linked List.
class LinkedList {
constructor(){
this.length = 0;
this.head = null
this.tail = null
}
}So what’s happening here? Well right now we just created a linked list with a length of 0, and we currently don’t have anything right now so that’s why both the head and the tail are null.
So now that we have our Linked List and Node class, how are we going to do our methods? Let’s start off with the push method.
First this function should accept a value. So inside our push method we’re going to put value inside.
push(val) Next, we should create a new node using our good old Node class that we created.
push(val){
let newNode = new Node(val)
}
}So now that we have our node, we have to check and see if there is a head, if there is no head, we set the head and the tail to be the new node. Otherwise, set the next property on the tail to be the new node and set the tail property on the list to be the new created node.
if!(this.head){
this.head = newNode;
this.tail = this.head
} else {
this.tail.next = newNode;
this.tail = newNode;
}
}The final thing you need to do is to increment the list by 1, and then return the length of the list. All in all the final push method looks like this. (I wrote out everything in VS code and this is how it came out in the end).
push(val) {
let newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
this.tail.next = newNode;
this.tail = newNode;
} this.length++;
return this
}Let’s talk pop()
Another method that can be used is the pop method.
Similar to what we did, we would create a pop method, unlike the push method we’re not taking any values. First we’re going to check if there are any nodes in the list, if not, then we’re going to return undefined.
pop{
if(!this.head) return undefined So now we wanna loop through our linked list until we reach the tail. In order to do this we would create two variables, and then we’re going to loop through it. So we’re going to create a current variable and a newTail value and set it to current.
let current = this.head;
let newTail = current;
while(current.next) {
newTail = current
current = current.next
}So let’s break down what’s happening here, so imagine we have a linked list here:
1 → 2 → X
So imagine we’re trying to loop through this linked list above. If we were to run this code on this list, it would start at 1, which would be our head, as well as our newTail., which start at the beginning. Now we’re going to loop through it. The while loop is checking to see if there is a value after current, if there isn’t then it stops. Since we’re looping through it the newTail is always going to become the previous value and current will be the next value, and it keeps going until there’s no more values.
Next, we’re going to move the tail and set the next value to null.
this.tail = newTail
this.tail.next = null;
this.length --;
return current So going back to our linked list above:
1 → 2 → X
The current value is the ! and the newTail would be the 2, and setting the next value is null since we have nothing after the 2 value. Since we popped a value out, we should decrement the length and also return the current value.
But wait?? What if there’s only one value??
if(this.length === 0) {
this.head = null;
this.tail = null;
}
return current So all in all, our final code will look like this:
pop() {
if (!this.head) return undefined;
let current = this.head;
let newTail = current
while (current.next) {
newTail = current;
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length--;
if (this.length === 0) {
this.head = null
this.tail = null
}
return current;
}The pop method definitely had a lot of things going on here, so now what about deleting things out of the list and getting things from the list?
Getting a value from a Linked List
So how do we get a value from a linked list? Would it be similar to an array and just getting the index out of it? If we were to try it what would happen?
If you guessed we would get an undefined value then you were right! Right now we don’t have a method to get the value of something in LinkedList. As with getting a value from a list we need to use the index, however unlike arrays where the index value is assigned, we are counting how many there are so that’s where the index value comes from. (This is where the O(n) big o for searching and accessing a Linked List comes from remember, searching and accessing a value in linked list is dependent on the total amount of items in the list.) So first, we need to declare our get method taking in the index value.
get(index)So now we have to think about a couple things, what if for some reason we enter in an index value that’s less than 0 and a value that’s greater than the length, we’re going to return null because it doesn’t exist. We are also going to declare a count value because as I’ve mentioned in a Linked List when we’re trying to find the index value, we are manually counting through each value we currently have. We also would have a current value which would start at the head which would keep track of the current position as we loop through.
get(index){
if(index <= 0 || index >= this.length) return null
let count = 0;
let current = this.head Next we have to add a while loop to go through the list to find the index we are currently looking for.
while(counter !== index){
current = current.next ;
counter++;
}
return current
}So what’s happening here? Here’s our Linked List.
1 → 2 → 3 → 4 → 5 →X
Say we want the value of index 3, which by looking at this we know the value would be 4. So our code would do this, we would start at value 1, which would be the current head.
Is index 0 the one we are looking for? Nope! Our counter increases by 1, and we move on and the next value becomes our head.
Is index 1 the one we are looking for? Nope! Our counter increases by 1, and now is 2, and we move on, the next value becomes our head!
Is index 2 the one we are looking for? Nope! Our counter increases by 1 and now is at 3 and we move on!
Is index 3 the one we are looking for? Yes! Since the counter is now equal to the index we entered in, our code stops and now returns the current value.
All in all, our current and final code for this method looks like this.
get(index){
if(index < 0 || index >= this.length) return null;
let counter = 0;
let current = this.head;
while(counter !== index){
current = current.next
counter++
}
return current
}Removing from Linked Lists at a specific value
So we can also remove stuff from linked lists. Remove also has quite a bit of things going on as well. Like the previous two methods we start off by declaring a method and the index of the value we want to remove.
remove(index) {
if(index > 0 || !this.head) return undefined
if (index = this.length - 1) return this.pop()
if(index === 0) {
return this.shift(value)
}So now we have to check our edge cases.
What if we entered in an index that is less than 0? In that case we would have it check that and return undefined.
What if the index we enter in is equal to the same as the length-1? We pop it out!
Lastly while I didn’t cover the method because this entry is getting way too long and I wanna cover reverse next, if the index is equal to 0, we would shift and move the next value to the left and it would be the new head.
So getting past all those edge cases, now we have to tackle, what if we want a specific value? We start by getting the previous Node, by using the get method.
let previousNode = this.get(index - 1)
let removed = previousNode.next
previousNode.next = removed.next
this.length--;
return removed; Next we’re going to declare a removed value and set it to the next value of the previous node, which is the value we are trying to remove. Next, we would set our previousNode to be the removed value. After all is said and done, we’re going to decrement the length and return the removed value.
So let’s go back to the Linked List we made to take a look at this visually.
1 → 2 → 3 → 4 → X;
Say we want to remove index 1. Looking at this we know, okay its not index 0, index 3, or its less than 0, so we’re not going to get it that easily and that eliminates our edge cases.
Now we move on to the next part of the code.
Since we’re removing index 1, we want to get the previous node, so we would use our get method to get it, so our previous Node would equal 0 which is value 1.
Next, we’re going to assign our removed value to the next value, because after all we’re trying to get rid of the value at index 1.
The final step is to reassign our previousNode.next to removed.next which would remove the value.
At the end of it all, we would decrement the length, because we removed our node and we would return the value. The final code looks like this:
remove(index){
if(index < 0 || index >= this.length) return undefined;
if(index === 0) return this.shift();
if(index === this.length - 1) return this.pop();
let previousNode = this.get(index - 1);
let removed = previousNode.next;
previousNode.next = removed.next;
this.length--;
return removed
}LeetCode Time: Reversing a Linked List
This is leetcode problem number 206. Reversing a linked list which can be found here: https://leetcode.com/problems/reverse-linked-list/
Reversing a linked list is a pretty common interview question based on my google foo skills. So let’s take a look at a linked list.
1 → 2 → 3 → 4 → 5
What we want from this we want it to look like this.
5 → 4 → 3 → 2 → 1
So since we’re working backwards, our we’re going to set our end of our linked list to null.
reverse(head) {
let prev = null;Next we’re going to go through our linked list using a while loop.
while(head){
let cur = head.next
head.next = prev;
prev = head;
head = cur
} So what’s happening here? We are declaring a temp value which would refer to the next Node of our linked list. I’m gonna try to make a diagram of this which kinda explains it. So in our little linked list above it would look like this.
1 → 2 → 3 → 4 → 5
h. . . c
I’m gonna be representing the current value with the letter c like above, and the head would be represented with the letter h. The dots are there because for some reason medium won’t let me do spaces lol. Right now, the head is still at 1 and the current value is at 2.
Now we’re going to shake things up a bit instead of pointing to the next value, we’re going to point to the previous value for the next value.
1 → 2 → 3 → 4 → 5
p .. h/c
So what’s happening here, remember the head of the linked list is always the start of a linked list, but now for some reason the head is in the middle of the list. The while loop we declared keeps repeating until we get to the end.
1 ← 2 → 3 → 4 → 5
p . . p . . h/c ..
After another loop
1 ← 2 ← 3 → 4 → 5
p .. p .. . p.. h/c ..
And another loop.
1 ← 2 ← 3 ← 4 → 5
p .. p .. p .. p .. h/c
and the last loop.
1 ← 2 ← 3 ← 4 ← 5
p .. p .. p .. p .. p(the head) .. null
At this point the while loop stops completely because there is nothing else to check.
All in all, when you do this, this is the final code.
let reverseList = function(head) {
let prev = null;
while(head){
let cur = head.next;
head.next = prev;
prev = head;
head = cur;
}
return prev
};This is one way to solve the reverse linked list problem. If asked about time space complexity it would be O(n) and the space complexity is O(1).
Whoa, this was a super long entry a lot longer than I was hoping it to be, and stuff. Anyway, for those who manage to read through this whole thing I hope you get something out of it. This is kinda how I see linked lists which might be weird, but I also tried to oversimplify it! Also, I know the diagram of explaining the reversing linked lists look weird but its also kinda difficult to explain lol (No wonder why they ask this as an interview question haha)
Anyway, this ends part 1 of the linked lists. While I want to do part 2 right away, I kinda wanna cover stacks and queues. My next data structures related entry will be on stacks and queues and in the future I’m going to write another linked list entry…probably on the other methods that can be used and doubly/circular linked lists.
