Hey guys am back again with part 2 of my 2-part post on Linked list. In the first part we focused on explanation, visualization, and use cases, while in this part we shall look at implementation in Javascript. So let's get into it.
Methods Of A Linked List
There are a lot of methods that we can implement into a Linked list, but we're going to be focusing on some of the most common methods:
- Prepend: Add a new node to the head of the list.
- Append: Add a new node to the tail of the list.
- PopFirst: Removes and returns the head/first node of the list or null if the list is empty.
- PopLast: Removes and returns the tail/last node of the list or null if the list is empty.
- Size: Returns the number of nodes in the list.
- Contains: Search through list and returns true or false if the value is present in the list.
In this tutorial we will be building the Doubly-linked list because it is a bit more complex than the Singly-linked list but also not too far from the Circular-linked list.
Node Class
class Node {
constructor(data, next, prev) {
(this.data = data), (this.next = next || null);
this.prev = prev || null;
}
}
Since we're building a Doubly-linked list, our nodes need to have 3 values, the data, the next pointer, and the prev pointer.
Linked List Class
class Linkedlist {
constructor() {
(this.head = this.tail = null), (this.size = 0);
}
}
Our Linked list will also have 3 parameters, the head
, tail
, and size
. The head
and tail
parameters will be set to null
initially, and size
will be set to 0. The head
parameter will keep track of the first node in the list, and the tail
will keep track of the last, while size
will keep track of the number of nodes in the list.
Prepend Method
The prepend method is used to add a new node to the head of the list.
prepend(data) {
if (!this.head) {
this.head = new Node(data);
this.tail = this.head;
} else {
let oldhead = this.head;
this.head = new Node(data);
this.head.next = oldhead;
oldhead.prev = this.head;
}
this.size++;
}
It will take in a value which will be set as the value of the new node. Let's break this function down step by step.
- First, we check if the list is empty.
- If it is, we create a node, pass it the data, and make sure the
head
andtail
of the list are pointing to this new node. - If the list isn't empty, then we take the current head of the list and put it in a variable
oldhead
; then we change the head pointer of the list to our new node. We set the next pointer of our new node tooldhead
and the prev pointer ofoldhead
to our newhead
. - Then lastly, we increase the
size
count by 1.
Append Method
The append method adds a new node to the end of the list.
append(data) {
if (!this.tail) {
this.tail = new Node(data);
this.head = this.tail;
} else {
let oldTail = this.tail;
this.tail = new Node(data);
oldTail.next = this.tail;
this.tail.prev = oldTail;
}
this.size++;
}
The append method follows a similar process to the prepend method.
- First, we check if the list is empty.
- If it is, we create a node, pass it the data, and make sure the
head
andtail
of the list are pointing to this node. - If the list isn't empty, then we take the current
tail
of the list and put it in a variableoldtail
; then we change thetail
pointer of the list to our new node. We set the prev pointer of our newtail
to theoldtail
and the next pointer ofoldtail
to our newtail
. - Then lastly, we increase the size count by 1.
PopFirst Method
The popFirst method removes and returns the data of the head/first node in the list.
popFirst() {
if (this.head) {
let oldHead = this.head;
if(this.size === 1){
this.head = this.tail = null;
}else {
this.head = oldHead.next;
this.head.prev = null;
}
this.size--;
return oldHead.data;
} else {
return null;
}
}
- First we check if there is a node in the list; if there isn't, then we just return
null
. - If there is a node, then we check if its the only node in the list by checking if size is equal to 1.
- If it is the only node, then we set both the
head
andtail
of the list tonull
and return the data of the node. - If it is not the only node in the list, then we store the current
head
of the list in a variableoldhead
, set the newhead
of the list to theoldhead.next
and set the newhead.prev
tonull
and return the data of theoldhead
. - Lastly, we decrease the
size
count by 1.
PopLast Method
The popLast method removes and returns the data of the tail/last node in the list.
popLast() {
if (this.tail) {
let oldtail = this.tail;
if(this.size === 1){
this.head = this.tail = null;
}else {
this.tail = oldtail.prev;
this.tail.next = null;
}
this.size--;
return oldtail.data;
} else {
return null;
}
}
The process of the popLast method is similar to the popFirst method.
- First we check if there is a node in the list; if there isn't, then we just return
null
. - If there is a node, then we check if its the only node in the list by checking if size is equal to 1.
- If it is the only node, then we set both the
tail
andhead
of the list tonull
and return the data of the node. - If it is not the only node in the list, then we store the current
tail
of the list in a variableoldtail
, set the newtail
of the list to theoldtail.prev
and set the newtail.next
to null and return the data of theoldtail
. - Lastly, we decrease the size count by 1.
Size Method
size() {
return this.size;
}
The size method is very simple. It just returns the size
property of the list which shows how many nodes are in the list.
Contains Method
The contains method is a form of search method that checks if a value is present in a list and returns true
or false
.
contains(data) {
if (this.size > 0) {
let currentNode = this.head;
while (currentNode) {
if (currentNode.data === data) {
return true;
}
currentNode = currentNode.next;
}
return false;
}else {
return `list is empty`
}
}
- First thing we want to do in this function is check if the list is empty, if it is we return a string to let the user know.
- If the list is not empty, then we want to loop through the list starting from the
head
and check each node's data property to see if it matches our function argument. - If we find a match, we return true.
- If we don't find a match, we return false.
Our complete Linked list class should look like this after adding all the above methods.
class Linkedlist {
constructor() {
(this.head = this.tail = null), (this.size = 0);
}
prepend(data) {
if (!this.head) {
this.head = new Node(data);
this.tail = this.head;
} else {
let oldhead = this.head;
this.head = new Node(data);
this.head.next = oldhead;
oldhead.prev = this.head;
}
this.size++;
}
append(data) {
if (!this.tail) {
this.tail = new Node(data);
this.head = this.tail;
} else {
let oldTail = this.tail;
this.tail = new Node(data);
oldTail.next = this.tail;
this.tail.prev = oldTail;
}
this.size++;
}
popFirst() {
if (this.head) {
let oldHead = this.head;
if(this.size === 1){
this.head = this.tail = null;
}else {
this.head = oldHead.next;
this.head.prev = null;
}
this.size--;
return oldHead.data;
} else {
return null;
}
}
popLast() {
if (this.tail) {
let oldtail = this.tail;
if(this.size === 1){
this.head = this.tail = null;
}else {
this.tail = oldtail.prev;
this.tail.next = null;
}
this.size--;
return oldtail.data;
} else {
return null;
}
}
size() {
return this.size;
}
contains(data) {
if (this.size > 0) {
let currentNode = this.head;
while (currentNode) {
if (currentNode.data === data) {
return true;
}
currentNode = currentNode.next;
}
return false;
}else {
return `list is empty`
}
}
}
You can find and tinker with the code here. Try adding some methods of your own and thanks for reading.
Top comments (1)
Great post! Easy to understand