Linked Lists. JavaScript.
A linked list is a data structure that stores multiple values in a linear fashion. Each value in a linked list is contained in its own node, an object that contains the data along with a link to the next node in the list. The link is a pointer to another node object or null if there is no next node. If each node has just one pointer to another node (called next) then the list is considered a linked list whereas if each node has two links ( previous and next) then it is considered a doubly linked list.
Originally it was intended for better memory management, linked lists also became popular when developers didn’t know how many items an array would ultimately contain. It’s easier to use a linked list and add values as necessary than it was to accurately guess the maximum number of values an array might contain.
The design of a linked list.
In order to use the Linked List, it’s important to know how to create a Node first. The node should have two properties, ‘data’ and ‘next’. Accept both of these as arguments to the ‘Node’ constructor, then assign them to the instance as properties ‘data’ and ‘next’. If ‘next’ is not provided to the constructor, then default its value to be ‘null’.
Create a new class Node:
class Node {
constructor(data, next = null){ //when creating a new node, always assign some data to it, and the //next node is null; this.data = data;
this.next = next;
}
}
Create a new class Linked List:
Create a class to represent a linked list. When created, a linked list should have *no* head node associated with it. The LinkedList instance will have one property, ‘head’, which is a reference to the first node of the linked list. By default ‘head’ should be ‘null’.
class LinkedList {constructor() {
this.head = null;
}
//add following methods within Linked List
}
Add following methods within Linked List.
insertFirst(data): Creates a new Node from argument ‘data’ and assigns the resulting node to the ‘head’ property. Make sure to handle the case in which the linked list already has a node assigned to the ‘head’ property.
insertFirst(data) { const node = new Node(data, this.head)
this.head = node
}
size(): Returns the number of nodes in the linked list.
size() {
let counter = 0;
let node = this.head; while (node){ // as long as we don't reach the last node, keep //counting - incrementing the count of nodes
counter ++;
node = node.next;
} return counter; // once there is no more node with the property //next, next === null, return counter}
getFirst(): Returns the first node of the linked list.
getFirst() {return this.head
//the first element of the linked list is always ahead
}
getLast(): Returns the last node of the linked list.
getLast() { if (!this.head) { //if we don't a have head node = our linked list //is empty
return null;
} let node = this.head;
while (node){ //we start with the head
if (!node.next){//if our node doesn't have the next property - we are at the end of //the linked list return node;
} //otherwisenode = node.next;
// reassign out node --> next node and continue the while loop
}
clear(): Empties the linked list of any nodes.
clear(){this.head =null;
//just reassign the head node to null to clean the linked list
}
removeFirst(): Removes only the first node of the linked list. The list’s head should now be the second element.
removeFirst() {
if (!this.head){ //if we don't have head node = our linked list is //empty
return;
}
this.head = this.head.next //remove the first node by adding the //head to the next node
}removeLast(): Removes the last node of the chain.
removeLast(){
if (!this.head){
//if we don't have the head node = our linked list is empty
return;
} if (!this.head.next){
// if we don't have a next node, it equals null this.head = null; //we have only one node - head, assign head to //null;
return;
} let previous = this.head;
let node = this.head.next;
while(node.next) {
//as long as the next element from the element next to the head //exists previous = node; // reassign it to prevoius
node = node.next; // reassign next to node
}// else
previous.next = null;
//remove the last element by assigning it to null.
}
insertLast(data): Inserts a new node with provided data at the end of the chain.
insertLast(data) { const last = this.getLast()
if (last){
// There are some existing nodes in our chain
last.next = new Node(data)
}else{
//The chain is empty
this.head = new Node(data)
}
}
getAt(integer): Returns the node at the provided index.
getAt(index) {
let node = this.head;
let counter = 0;
while(node){
//as long as node is exist
if (counter === index){ //if our index same as a counter, it //means we found a notereturn node;
}
node = node.next;
//if not, assign a node to the next node and increment the counter
counter ++;
}
return null;// otherwise return null
}
removeAt(integer): Removes node at the provided index
removeAt(index) {
if(!this.head) {
return;
}
if(index === 0) { //if no head
this.head = this.head.next; //assign next node to the head
return;
}
let previous = this.getAt(index-1) //get the prevous node
let next = this.getAt(index+1)// get the next node
if (!previous || !previous.next){ //if no previous node or no next
return;
}
previous.next = next // reestablish the connection skipping the //current node
}insertAt(data, integer): Create and insert a new node at provided index. If the index is out of bounds, add the node to the end of the list.
insertAt(data, index) {//insert a node to an empty list
//index is out of bounce 12, add to the very end;
//use getAt method to get a reference to the previous node
//create the new node
//new node point to the
if(!this.head) {
this.head = new Node(data); //if our list is empty, create a //first node with the head
return;
} if(index === 0) {
this.head = new Node (data, this.head);
// if we need to insert the new node to the beginning of the linked // list - assign the new node and make the next agr. to an old head
return;
} let previous = this.getAt(index-1) || this.getLast();
//previous is the one before the new one that had to be insert or //the last element in the linked list//if the index is out of bouncelet node = new Node(data, previous.next);
//create a node and reassign the next node of the newly created //node
previous.next = node //change the reference of next to the new node
}
forEach(function): Calls the provided function with every node of the chain and the index of the node.
forEach(fn) {
let node = this.head;
let counter = 0; while(node){
fn(node, counter);
node = node.next;
counter++;
}
}
for…of Loop: The linked list should be compatible as the subject of a ‘for…of’ loop
//use javaScript Generators*[Symbol.iterator](){ let node = this.head;
while(node){
yield node;
node = node.next;
}
}
Linked lists are a foundational data structure in computer science. The concept of using nodes that point to one another is used in many other data structures are built into many higher-level programming languages.
For JavaScript programming, it’s easier using the built-in collection classes such as Array. The built-in collection classes have already been optimized for production use and are well-supported across execution environments.