# 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.