Hello there fellow coders! The last blog I wrote about was on a data structure concept called dynamic programming. Today I want to talk about another data structure called linked lists. They are very similar to arrays: linear data structure, but they hold data in individual objects called nodes. You will definitely see more nodes as you keep going through the wonders of data structures and algorithms. In a linked list, nodes hold both the data and the reference to the next node in the list. The singly linked list also has their own properties of head (where it starts), tail (where it ends), and next (reference to the next node).
Purpose of Linked List
There are a few real world application for linked lists. When you’re on your browser, you are able to go back and forth on the same tab. They are linked through a linked list. It starts from the home page to where ever you are currently. Another real world application is a music player on Apple or Spotify. If you go through a playlist you can consider the head as the first song of that playlist and the last song as the tail.
Starting Off
In order for us to start utilizing a linked list, we must create the appropriate classes. Remember, the Node class has to contain the property of the value and the reference. The Link list also contains the head, tail, and the length. One thing to note, there are different variations of linked list and we could customize the node. Let’s say for example if we wanted to create a doubly linked list instead, the node’s property would have to contain: previous, next, and value. If we take a look at figure 1.0 that is how your classes should look.
The Methods Involved
Almost all data structures contain methods that help organize the structure of the data. I will be talking about a few of them for a singularly linked list. Some of the other linked list contain the same methods, but with a few extra steps because of the variations we would have in the nodes. In a linked list, we are able to push, pop, shift, unshift, get, set, insert, remove, and reverse. Sounds very very similar to an array, but the time complexity is much better!
Push()
Just like an array, the push is inputting the value at the end of the list. The push method in this case has an edge cases that properly assign the head and tail. If it already has a head and a tail, we will take the tail’s next value and assign it to the new node. Then we reassign the tail to the new node. We also have to increment the list’s length by one because we’re adding a new node into the linked list. Pretty simple right? Sounds like a regular push case in an array, but with an edge case.
Want to read this story later? Save it in Journal.
pop()
You can probably guess what this method can do because I mentioned that these methods are very similar to the array’s method. We are removing the last node at the end of the linked list. To do this, we must create place holder values to keep track of the new tail. To give a good analogy, think of a ref and a line of players. The ref needs to remove the last player and he starts from the first player in line. Since the first player in the line is not the last person, the ref will go on to the next person keeping track. Once he gets to the end of the line, he removes the last player and the player before him/her is now the new last player on line.
In figure 1.4, our current will be the ref and our newTail is our new last player on line. The while loop on line 32 to 36 is the ref going towards the end of the line. Once it reaches the end of the line, the ref will stop and assign the last player as the new last player (newTail) and then he will fully remove the last player. Please don’t forget that we also have edge cases in our method. Once there is no more players available then we don’t have a team.
Unshift()
You can probably guess what this method does too. If you don’t that is okay, this is why I am writing this blog! We are trying to add a node at the beginning of the list instead of adding it towards the end of the list. I am still going to use our player analogy. We want to put the new player in front of the line. He/she must go through a tryout and pass. They become a member(s) of the team on line 46. We also have an edge case that is exactly the same as our push method. However, we are going to make our first player on line as the next player on after the newest player. Then we make the newest player as the first player on our line. We also increment our line by one because we added a new player!
Shift()
We need to remove the first player on the line. If we don’t have any players on the line we can’t do anything. However, if there is we will do something similar do what we did earlier with pop without the ref. Create a place holder to keep track of who is going to go out first. The first player has another player next to him/her and then leaves the line. Once that player leaves the line, the next player on line becomes the first player. As each player leaves the line, we will eventually end up with one person. With that one person he/she is the first and last person on line. Once the player leaves there is no more players and we do not have a team anymore.
Get()
In this method, we need to check a player on the line with an input. That input cannot be less than or greater than the amount of players we have on the line. We’re going to bring a coach into this analogy and our coach has an attendance sheet to see the player’s position on the line. The attendance sheet is the counter and the current is the coach checking off the players one by one as he is going through the sheet. While the input has not reached the position on the sheet, the coach will keep checking off the players and down the sheet until he/she finds the input.
Set()
Our coach needs to set a player on the line and change the player’s value. In order for our coach to do this, we can use our get method to find out player. Very convenient for us! If we have found our player on the line, the coach will simply change his/her value, but if the coach cannot find the player we simply say that the player is not here.
Insert()
This one is a little tricker than the set method we created above, but we can persist through the complications. Our coach needs to add a player somewhere within the line. If the new player is being placed at a position where it is less than or greater than the line’s length we simply can’t do anything. If the coach wants to place the player at a position at the end of the line we can use the method push and vice versa with unshift. Now here comes the fun fun part! Our coach has the newest player tryout and they pass! The coach must now place this player somewhere on the line. To do that the coach must use the attendance sheet (get method) and see who will be in front of the newest player and after the newest player. Prev indicates the player before the newest player and temp will be the player after the newest player. Our coach will assign the players’ value’s by switching them.
Remove()
Uh-oh, our coach is mad at one of our players and now he/she wants to remove that player from the line. This method has very similar edge cases to our insert method. So if the coach is angry at the position where the index is less than or greater than the line, the coach must be a little coocoo. However, the coach will use his attendance sheet and cross the player’s name and value. The coach is able to do this by checking to see who is before that player whose he/she is mad at. Let’s call that player Jerry. Coach will take the player before Jerry and assign their next value as Jerry’s next player.
Reverse()
I hope you guys aren’t tired of my line of players analogy, please bear with me! Our coach just wants our players to reverse the position they are in on the line. In order for this method to work, we have to create a few place holder variables. The purpose of these place holder variables will allow us to swap the first and last player on the line. This will get confusing so we will name our original first player Rick and last player Jones. They will swap places with each other and we can start shifting every players position starting from Jones. The next player after Jones is going to be the player who was after Rick. It gets a little tricky here because we are going to use more placeholders called next and prev. The coach is going to make sure that the player after Rick is assigned to next and setting their position to prev. Once the coach sets it up (the placeholders), he/she will then proceed to swap their value and position. The coach will keep doing this until he has done the whole line.
I had a hard time trying to understand linked list until I started looking at it in a different way, hence the player analogy. Enough of the analogy and I hope you were able to get something out of this! Good luck to those who are starting their journey on algorithms and data structures. It will take time, but surely you will be able to code it with your eyes closed. Take care and cheers!
More from Journal
There are many Black creators doing incredible work in Tech. This collection of resources shines a light on some of us:
