LINKED LIST METHODS
In my on-going journey to have a better understanding of algorithms, I am continuing to learn about Linked Listed.
This is what I have learned this week about Linked Lists.
What is a node?
A node has two properties
1. data
2. next
— — — — — — — — — — — — — — — — — — -
This is a typical setup for a Linked List.
Class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
— — — — — — — — — — — — — — — — — — -
TYPICAL USAGE
let n = new Node(1)
— — — — — — — — — — — — — — — — — — -
LINKEDLIST
· Header: Which keeps track of the node at the front of the list.
· Tail: Which keeps track of the node at the back of the list.
· Size: Which keeps track of the number of nodes within the list.
size: 4
— — — — — — — — — — — — — — — — — — -
class LinkedList{
constructor(){
this.head = null;
this.tail = null;
this.size = 0;
}
}
TYPICAL USAGE
let LinkedList = new LinkedList()
tail = Null
head = Null
size = 0
— — — — — — — — — — — — — — — — — — -
LINKEDLIST: PREPENDING
// adding a node to the beginning of a LIST
prepend(data){
const n = new Node(data);
if(this.size ===0) {
// if the list is empty, do the following
this.head = n;
// set this.head to reference the newly created node.
this.tail = n
// set this.tail to reference the newly created node.
// because the list is empty, the newly created node will be both the head and the tail.
} else {
// if the LIST has data in it, do the following.
n.next = this.header;
// set n.next to the node that the header is referencing.
// this will move the data that is in header to the sequential node, making the Header empty for the next line of code
this.header = n;
// set this.header to reference n, the new first node within the LIST.
}
this.size++;
// after a node is inserted to the beginning of the LIST, increment the size by 1.
}
— — — — — — — — — — — — — — — — — — -
LINKEDLIST: APPENDING
// adding a node to the end of a LINKED LIST
append(data){
const n = new Node(data);
if(this.size ===0) {
// if the list is empty, do the following
this.head = n;
// set this.head to reference the newly created node.
this.tail = n
// set this.tail to reference the newly created node.
// because the list is empty, the newly created node will be both the head and the tail.
} else {
// if the LIST has data in it, do the following.
const temp = this.tail;
// the current this.tail will be set to const temp, a temporary variable, which is a reference of the tail.
//
this.tail = n;
// this.tail will reference the newly created node, n.
temp.next = this.tail;
// this.tail will set temp.next, as the new tail.
// the data that was saved in temp is now replaced with the newly created node and is set to temp.next
}
this.size++;
// after a node is inserted to the end of the LIST, increment the size by 1.
}
— — — — — — — — — — — — — — — — — — -
PRINTING OUT OUR LINKEDLIST
// Printing out a Linked List
printList(){
let data = “”;
// this will save the data within the node as a string.
// we will “return data” at the end of the method.
let current = this.header;
// we will start at the beginning of the list.
while(current != null){
// this will iterate through the LIST until current equals null.
// if current equals null, that means there are no more nodes within the LIST.
// if the LIST is empty, then skip down to return data.
data = data + current.data + “”;
// this will save the data at the current node by appending it to a string we’re going to return.
current = current.next
}
return data
// after the while loop is done executing, the data is returned.
}
— — — — — — — — — — — — — — — — — — -
REMOVE FIRST NODE
// Removing the first node from a LINKED LIST
removeFirst() {
if(this.size === 0)
// if the LIST is empty, return null, as in return nothing;
return = null;
let data = this.header.data
// this will set whatever that is in the header as data
// this is what we want to remove from the LIST
if(this.size === 1) {
// if the size of the LIST is equal to 1, then do the following
// if there is only 1 item in the LIST, then set the header and tail to null.
this.header = null;
// this will set this.header to null
// this will remove the data from the LIST
this.tail = null;
// set this.tail to null
// this will remove the data from the LIST
} else {
// if the size of the list is not equal to 1, then do the following
this.header = this.header.next;
// set will this.header to equal to the sequential node in the LIST
// this will remove the data from the LIST
// this will replace whatever data that was stored in header with the data that is stored in the sequential node.
this.size — ;
// this will decrement the size of the LIST by 1.
return data;
// this will return the data
}
— — — — — — — — — — — — — — — — — — -
REMOVE LAST NODE
// Removing the last node from a LINKED LIST
removeLast() {
if(this.size === 0)
// if the LIST is empty, return null, as in return nothing;
return = null;
let data = this.tail.data
// this will set whatever that is in the tail as data
// this is what we want to remove from the LIST
if(this.size === 1) {
// if the size of the LIST is equal to 1, then do the following
// if there is only 1 item in the LIST, then set the header and tail to null.
this.header = null;
// this will set this.header to null
// this will remove the data from the LIST
this.tail = null;
// set this.tail to null
// this will remove the data from the LIST
} else {
// if the size of the list is not equal to 1, then do the following
let current = this.header
// this will set current as the header
// in order to remove the last node, we need to find the node before the last node, as in, find the second to last node and then remove the last node.
while(current.next.next != null)
// this while loop will stop when current.next.next is equal to null.
// this while loop will stop at the second to last node.
current = current.next;
// this will move current node, which is set as the header, from the header node position to the sequential node in the LIST.
// the while loop will keep running until current.next.next is equal to Null.
current.next = null;
// when current.next.next is equal to Null, then current.next will equal to Null.
// this will remove the node before the Null in the LIST.
this.tail = current;
// this will set this.tail to the new last node.
// this will set this.tail as the node before Null in the List.
}
this.size — ;
// this will decrement the size of the LIST by 1.
return data;
// this will return the data
}
— — — — — — — — — — — — — — — — — — -
INSERTING A NODE AT A CERTAIN POSITION
// Inserting a node at a certain position in a LINKED LIST
insertAt(pos, data) {
if(pos < 0 || pos > this.size)
// if you want to insert a node at a position that is less 0 or greater than the size of the LIST, then just return.
return;
if(pos === 0)
// if you want to insert a node at position 0, which is at the beginning of the LIST, then prepend the data
this.prepend(data);
else if(pos === this.size)
// if you want to insert a node at the end of the LIST, which would be this.size, then append the data
this.append(data);
else {
// if you want to insert a node between the beginning and the end of the LIST, do the following.
const n = new Node(data);
// this is the node we want to insert into the LIST.
let prev = null;
// prev is set to null.
let current = this.header;
// setting current to this.header will start at the beginning of the LIST.
let counter = 0;
// this will keep track of the position we’re in.
while(counter < pos){
// this while loop will keep going as long as the counter is less than position you want to enter the node into the LIST, which is pos.
// when the counter is greater than the position you want to enter the node into the LIST, which is pos, exit the loop and go down to n.next = current.
prev = current;
// current is set as prev.
// if the counter is less than the position you want enter the node into the LIST, which is pos, then set current as prev.
current = current.next;
// this will set the node that is to the right of the current node as the new current node.
// this will move current node, which is set as the header, from the header node position to the sequential node in the LIST.
counter++;
// this will keep track of the position we’re at.
// the while loop will keep running as long as the counter is less than the position you want to enter the node into the LIST, which is pos.
// when the counter is greater than the position you want to enter the node into the LIST, which is pos, go to the next line of code
}
// it’s time to insert the node into the LIST
// we’re at the index in the LIST where you want to enter the node.
n.next = current;
// current is set as n.next.
// the ‘current’ index is set as n.next, which is the node you want to insert into the LIST
prev.next = n;
// n is set as prev.next.
// before the while loop, next.header was set as current, then within the while loop prev was set as current, after the while loop n is set as prev.next
// n is the data you want to enter the node into the LIST.
this.size++;
// increase the size of the LIST.
// now that a node has been inserted into the LIST, the size of the LIST has increased by 1.
}
}
— — — — — — — — — — — — — — — — — — -
REMOVING A NODE AT A CERTAIN POSITION
// Removing a node from a certain position in a LINKED LIST
removeAt(pos){
if(pos < 0 || pos > this.size)
// if you want to remove a node at a position that is less 0 or greater or equal to the size of the LIST, then just return null.
return null;
if(pos === 0)
// if you want to insert a node at position 0, which is at the beginning of the LIST, then prepend the data
// if you want to remove a node at position 0, which is at the beginning of the LIST, then return this.removeFirst()
return this.removeFirst()l;
else if(pos === this.size -1)
// if you want to remove a node at the end of the LIST, which would be this.size -1, then return this.removeLast()
return this.removeLast()
else {
let prev = null;
// prev is set to null.
let current = this.header;
// setting current to this.header will start at the beginning of the LIST.
let counter = 0;
// this will keep track of the position we’re in.
while(counter < pos){
// this while loop will keep going as long as the counter is less than position you want to enter the node into the LIST, which is pos.
// when the counter is greater than the position you want to enter the node into the LIST, which is pos, exit the loop and go down to n.next = current.
prev = current;
// current is set as prev.
// if the counter is less than the position you want enter the node into the LIST, which is pos, then set current as prev.
current = current.next;
// this will set the node that is to the right of the current node as the new current node.
// this will move current node, which is set as the header, from the header node position to the sequential node in the LIST.
counter++;
// this will keep track of the position we’re at.
// the while loop will keep running as long as the counter is less than the position you want to enter the node into the LIST, which is pos.
// when the counter is greater than the position you want to enter the node into the LIST, which is pos, go to the next line of code
}
// it’s time to remove the node into the LIST
// we’re at the index in the LIST where you want to remove the node.
// current should be the reference we want to remove
prev.next = current.next
// prev is set as one node to the left of current.
// current is set as one node to the right of prev.
// prev.next is set as current.next, which is the node to the right of the ‘current’ node.
// so prev.next will equal to current.next.
// this will remove the node at that position.
this.size — ;
// decrease the size of the LIST.
// now that a node has been removed from the LIST, the size of the LIST has decremented by 1.
return current.data
// returning the data from the removed node.
