Introduction
In the previous post in this series, I gave an introduction to linked lists as a data structure. Next we will take a look at how we can create some of the common methods associated with linked lists. All of the following examples are in JavaScript.
Getting started
Before we start creating the methods, we need to create a node class as follows. Now would be a good time to remember that a node in a linked list has data and a pointer to the next node. We can create a node using a constructer.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
Next we can create a linked list class, putting all of our methods within this class. To do this we should start by creating a constructor for the Head, which is the first node in our linked list.
class LinkedList {
constructor() {
this.head = null;
}
}
We can now start adding methods to our linked list class.
Linked List Methods
getLength()
This is a method that can be used to get the length of a linked list:
getLength() {
let count = 0;
let current = this.head;
while (current) {
count++;
current = current.next;
}
return count;
}
We can find the length of a linked list by traversing the entirety of the linked list, increasing a counter by one every time a new node is found.
addHead()
This method can be used to insert a new node at the Head of a linked list.
First we create a new node:
const newNode = new Node(data);
Then we point the new node to the current Head:
newNode.next = this.head;
And finally declare the new node to be the Head:
this.head = newNode;
The method will look like this:
addHead(data) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
addTail()
This method will add a node to the tail of a linked list.
First we need to check if the linked list has any nodes in it. We can do this by checking if a Head node exists, if not the newly created node will become the head.
if (!this.head) {
this.head = newNode;
return;
}
We will need to create a reference to the current node whilst traversing the linked list, starting at the Head.
let currentNode = this.head;
while (currentNode.next) {
currentNode = currentNode.next;
}
The loop will run for as long as the current node has a next value, that is to say, as long as the current node points to another node. When this is no longer the case, the current node will point to the new node which will in turn become the tail of the linked list.
currentNode.next = newNode;
The complete method is as follows:
addTail(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
return;
}
let currentNode = this.head;
while (currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = newNode;
}
insertAt()
We can use this method to insert a new node at a given index. Given a linked list and a new node, it may help to envision the insertion as follows.
Say we want to insert the new node at index 3, we must first traverse the linked list until the given index.
The new node will point to the node at index 3 and then the node at index 2 will point to the new node.
This is what the final linked list will look like, with the new node at index 3.
In code, we will first we check if the index is valid, throwing an error if an invalid index is provided.
if (index < 0 || index > this.size()) {
console.error("Invalid index");
return;
}
After creating a new node, we will check if a Head already exists, if not the new node will become the Head, similar to the addHead() method.
if(index === 0){
newNode.next = this.head;
this.head = newNode;
return;
}
Otherwise we will need to create a reference to the current node, traversing the linked list until we find the desired index.
for (let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
We finish by inserting the node at the index, by setting the new node's pointer to the current(our reference) node's next value.
newNode.next = currentNode.next;
Then we set the current next value to the new node.
currentNode.next = newNode;
The complete method will look like this:
addAt(index, data) {
if (index < 0 || index > this.size()) {
console.error("Invalid index");
return;
}
const newNode = new Node(data);
if (index === 0) {
newNode.next = this.head;
this.head = newNode;
return;
}
let currentNode = this.head;
for (let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
newNode.next = currentNode.next;
currentNode.next = newNode;
}
removeHead()
This is a method that we can use to remove the Head of a linked list. First we check if the Head exists.
if (!this.head) {
return;
}
If it exists, we simply remove the Head's pointer to the next node.
this.head = this.head.next;
This is what the the full method looks like:
removeHead() {
if (!this.head) {
return;
}
this.head = this.head.next;
}
removeTail()
This method can be used to remove the last node in a linked list.
After checking if the linked list has any nodes, we traverse the list in a manner similar to the addTail() method, the only difference being that now we point the penultimate node to null.
The code for this method is as follows:
removeTail() {
if (!this.head) {
return;
}
let current = this.head;
while (current.next.next) {
current = current.next;
}
current.next = null;
}
removeAt()
This method allows us to remove a node at a given index.
For example given the following linked list, say we want to remove the node at index 2.
This can be done by traversing the linked list to the node before the given index(index 1 in this case), pointing it to the node at the index after the given index(index 3).
It is important to remember that each node in a linked list consists of data and a pointer to the next node in the list, therefore by pointing the previous node to the node after the index, the node at the index is no longer a part of the array list.
This is what the final linked list will look like:
To do this in code, start by checking if a valid index has been given. Then we check if the index given is zero, if so we remove the head of the linked list.
if (index === 0) {
this.head = this.head.next;
return;
}
Next we traverse the linked list, similar to what we did with the addAt() method, the difference being that once we find the node node at the desired index, we now point our reference node to the node after the node at the index.
let currentNode = this.head;
for (let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
if (currentNode.next) {
currentNode.next = currentNode.next.next;
}
The full code for this method is as follows:
removeAt(index) {
if (index < 0 || index > this.size()) {
console.error("Invalid index");
return;
}
if (index === 0) {
this.head = this.head.next;
return;
}
let currentNode = this.head;
for (let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
if (currentNode.next) {
currentNode.next = currentNode.next.next;
}
}
get()
We can use this method to get a node's data given an index. We start by setting a reference to the linked list's Head. We then traverse the linked list until the node before the index, setting the reference to this node.
for (let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
We then return the data value of the node of the given index.
return currentNode.next.data;
This is what the full code for the method looks like:
get(index) {
let currentNode = this.head;
for (let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
return currentNode.next.data;
}
print()
The final method for our linked list class will allow us to print out the data values of the nodes in the linked list. This is done by creating a reference to the current node, and printing the data value of each node as we traverse the linked list. The code is as follows:
let currentNode = this.head;
while (currentNode) {
console.log(currentNode.data);
currentNode = currentNode.next;
}
Conclusion
To test out the methods of the linked list class, simply create a new linked list, for example:
const linkedList = new LinkedList();
You can then proceed to call the methods as required. I hope this guide has helped to deepen your understanding of linked lists.
Top comments (0)