🖤 Hi Programmers! 🐱
Today we will be walking through the third installment of the series on How To: Build A Linked List. Here are the links to the first two installments: 1 and 2. Please feel free to read those if you haven't or reread to refresh your mind.
We will be focusing on how to add insertion functionality via an insert() and traverse() method to our class LinkedList.
These two methods are definitely more challenging than the previous but together we are going to make them fully comprehensible and readable.
Let's get started!
Goals
1. Mapping Out insert()
2. Checking Parameters
3. Creating a New Node
4. Build traverse()
5. Traverse the Linked List
6. Recap + Summary
Mapping Out insert()
Our insert() method is going to have 'index' and 'value' parameters. We need both parameters, because unlike append() or prepend() that produce a value at a fixed spot in the linked list, insert() will insert the value at any specified index.
Therefore, inserting a node at a specific index is a lot more complicated than just appending or prepending. Let's consider what we would need to do in order to successfully insert a new node:
1. Check the parameters for edge cases.
2. Create a new node.
3. Traverse through the existing nodes in the linked list until we get to the specific index we pass a parameter.
4. Update the 'next' property of the node that comes before the new node; set it to the new node object.
5. Update the new node's 'next' property.
8. Increase the length of the linked list.
Whoa -- this is a lot. But we can do it don't worry.
Checking Parameters
What happens if we call insert(1000, 4) -- inserting the value of 4 at the index of 1000 -- on our instance of LinkedList, but our instance only has five (5) nodes? Or what happens if we call insert(0, 999)?
Realistically, we could still follow through with insert(), but that complicates things for no reason. If our index is greater than or equal to our instance of LinkedList's length, we should just append it using the append() method we created. The same thing goes if we want to insert a value at the index of 0. Since the index of 0 always represents our first node in the linked list we can prepend the node using prepend().
Checking parameters is a great thing to think about and implement when coding. It shows that we consider edge cases and we think a little outside of the box.
Here is what the code would look like checking the index parameter:
insert(index, value) {
if (index >= this.length){
return this.append(value)
}
if (index === 0){
return this.prepend(value)
}
}
Creating a New Node
Now, let's create a new node using the ES6 object syntax. This is nothing new if you have been following along with the series:
insert(index, value) {
if (index >= this.length){
return this.append(value)
}
if (index === 0){
return this.prepend(value)
}
const newNode = {
value: value,
next: null
}
}
We declare an object 'newNode' and set its 'value' property to the value we pass into insert() and we set its 'next' property to null.
Build traverse()
What is traversal? You may not have heard of it before. Do you recognize the terms "looping" or "iterating"? They are all somewhat interchangeable. Just think of traversing through a linked list as stepping on stones on a path: you start at the first stone and continue to step onto each stone (one at a time) until you reach the last stone.
We need to traverse through the linked list because our instance of class LinkedList is unidirectional. Like reading a sentence, going left to right.
In our traverse() method, we will pass it a parameter of 'index':
traverse(index){
}
Now, we want to traverse the list until we get to the index we passed in. We can achieve this using a while loop:
traverse(index){
let counter = 0
let currentNode = this.head
while (counter !== index){
// do something here
}
}
- We declare and assign a 'counter' variable to 0.
- We declare and assign a 'currentNode' variable to our linked list's head node - because we want to start at the beginning.
- While the counter does NOT equal our index -- keep executing the code block in the while loop until the counter does equal our index.
So what should we do to our currentNode as long as the counter does not equal its index?
traverse(index){
let counter = 0
let currentNode = this.head
while (counter !== index){
currentNode = currentNode.next
counter++
}
return currentNode
}
- While the counter does NOT equal our index, reassign the value of the currentNode to the currentNode's 'next' property AND increment the counter.
- By doing this, we are able to skip through from one node to the next.
We continue through the linked list, stopping at each node to check its index. When the counter finally equals the value of the index, the while loop will stop executing and we will be at the index we passed in (via returning the currentNode).
Traverse the Linked List
With our parameters checked, our new node created, and a working traverse() method, we can now do a few things like:
1. Update the 'next' property of the node that comes before the new node; set it to the new node object.
2. Update the new node's 'next' property.
How can we do this? We use traverse() to arrive at the node that comes before it.
Lexically, the node that comes before our index has an index of 'index - 1':
insert(index, value) {
if (index >= this.length){
return this.append(value)
}
if (index === 0){
return this.prepend(value)
}
const newNode = {
value: value,
next: null
}
const beforeNode = this.traverse(index - 1)
}
Here, we have decided to store the index of the node that comes before our inserted node in a constant 'beforeNode' for reference and later use.
Now, we can grab the beforeNode's next property and store it also in a constant for reference and memory:
const beforeNode = this.traverse(index - 1)
const beforePointer = beforeNode.next
Then, let's update the 'next' value of beforeNode and set it to the newNode object:
const beforeNode = this.traverse(index - 1)
const beforePointer = beforeNode.next
beforeNode.next = newNode
Right now our newNode's 'next' value is 'null'. Yet, we want it to point to the node that the beforeNode used to point to... Good thing we stored its value in memory as a constant!
const beforeNode = this.traverse(index - 1)
const beforePointer = beforeNode.next
beforeNode.next = newNode
newNode.next = beforePointer
So, very quickly and very suddenly we have achieved a few things:
- We inserted the newNode into the linked list at the index we passed in as a parameter.
- We were able to do so because we updated the beforeNode's 'next' property and updated newNode's 'next' property.
- We shifted the indices of all pre-existing nodes that came after the newNode.
Finally, we just have to increment the length because our instance of LinkedList is now longer:
class LinkedList {
constructor(data){
this.head = {
data: data,
pointer: null
}
this.tail = this.head
this.length = 1
}
append(value){
const newNode = {
value: value,
next: null
}
this.tail.next = newNode
this.tail = newNode
this.length++
}
prepend(value){
const newNode = {
value: value,
next: this.head
}
this.head = newNode
this.length++
}
traverse(index){
let counter = 0
let currentNode = this.head
while (counter !== index){
currentNode = currentNode.next
counter++
}
return currentNode
}
insert(index, value) {
if (index >= this.length){
return this.append(value)
}
if (index === 0){
return this.prepend(value)
}
const newNode = {
value: value,
next: null
}
const beforeNode = this.traverse(index - 1)
const beforePointer = beforeNode.next
beforeNode.next = newNode
newNode.next = beforePointer
this.length++
}
}
Recap + Summary
That was a lot! But, we now have an even more functional Class LinkedList built in JavaScript. We are getting to a point where our code provides functionality to instances instantiated from the class. A functional linked list is great for efficient coding, an introduction to Trees, and predictable data rendering.
For the next part in the series, I want to focus on traversing linked lists in order to remove a node in a specific location on the linked list.
Stay tuned! And thank you for reading + coding along with me :)
🖤🖤🖤
Top comments (3)
This one is nice..
Thank you Kumar! I hope you find it helpful :)
yeah it was , easy to understand and to the point