Linked List : newbies with JavaScript

What is a linked list?

In the data structure, linked lists are a popular and important DSA. It is a linear data structure. A linked list is utilized to store various objects of similar types of data. Also, it is a collection of independent nodes that’s why it contains any type of data. Unlike an array, it is stored from one node to another node with pointing to the next. Data can be stored in scattered ways.

There are mainly three types of Linked lists.

1. Singly-linked list

2. Doubly linked list

3. Circular linked list - it can be singly and doubly

Note: I assume that the article is for beginners. If you are an expert of linked lists programming please escape this blog or suggest if anything is omitted needs to be a better approach to learning.

In this article, I took JavaScript as a programming Language and described every detail from pseudocode/details with visualization to implementation of real code.

NoDe: in the linked list each data is called a node. Each node has two parts: data and the address of the next node. That is why it points the link of each node to the next.

Example of a singly - linked list:

The picture shows a linked list example. Here A is the head of a linked list whose address is implied as 1000 and B is the next node of A where 2000 is implied as its address and the address of each node points to the next node, here D is the last node who’s next node address is null.

Singly Linked List:

So the linked list shows a linear path that can be traversed one way: a singly linked list**.**

A singly linked list made up of nodes each node consists of two fields: one is data and the address of the next node’s reference.

Operation of linked list:

Traversal - access each element of the linked list.

• Insertion - adds a new element to the linked list.

• Deletion - removes the existing elements.

• Search - Find a node in the linked list.

• Replace- find the specific index value and replace

Before going to the implementation you must have little knowledge of OOP(object-oriented programming) because we use classes for sharing common properties and behavior. So I assume that you are familiar with it. If not please take a glance/visit the OOP side.

First node: Let’s form the first node here construction allows us to initialize an object.

Here is a node class that will be used for the whole operation.

First singly linked list Class:

Here is the first singly linked list class that will be used for the next operation. Here the constructor initializes the Head and Tail and its length.

Length:

How to find the length ? at first, the length of list is assumed empty.

When we need to calculate the length of the list. we can define an isLength()/ isEmpty() method so that we can use it inside the operations.

1. Insertion - adds a new element to the singly-linked list.

There are two methods for insertion

a) push() — insert element to the end. b) unshift() → insert an element at the start of the list

Step One: PUSH() method

todo: the list is “ ” = empty list

• Before the insertion, the list is implied empty so that we can push an item/node to the list. Here we use the PUSH() method to insert nodes.

• Now let’s move to insert a node to the list. Here the push method inserts a node to the end of a list. You can also use prepend, and append words instead of push unshift.

• Then we need an instance of a node to be inserted.

• Now think first is the list empty? if yes then set the node to head and tail. If there is at least a node in the list then set the node tail to next. Like: “tail.next”

• Then increase the length of the list. If you forget to increase the length then the next node can not insert.

Pseudocode example: push()

• ‘ ‘ if no node the length is 0

• ‘ ‘ list is empty then the head and tail will be A = | A |

• | A | node A is inserted, length is 1

• | A, B | if the length is 1 then the next node of A will be B, and B will be the tail

The push method will push the node to the end.

Visualization:

Here the head and tail are null

Now insert A in the list so head and tail are A

If there was A before the B insertion so the B will be the tail of the list

code snippet

Now make an instance of a linked list and you can call the method like bellow

let list = new SinglyLinkedList() // take the instance of singly link list which defined at the top

Call list.push(A) then list.push(B) // you will get the answer | A B |

If you can not find the list to display, we can make a showLIst() method to show the list.

code snippet

The showList method will take all nodes of the list while a node exists in it. Here you can see in the while loop the (current = this.head) assumes that there is a node in the list. Simple …

So run the code with your IDE like below 🙂

class Node{

// codes

}

Keep it out of the class below. it is separate class

class SignlyLinkedList{

isLength(){

// write code

}

push(value){

// all push method code

}

showLIst(){

// code

}}

Make list instance like : let list = new SignlyLinkedList()

Then call list.push(‘A’)

list.push(‘B’)

console.log(list.showList()) // result A, B

Remember: make sure all your code and calling is written according to the scope.

Unshift() method.

According to the push(), the rule of the unshift() method has one change, that is the inserted node will stay as the head of the list and location will be the first element. And the first element which was at the head of the list will be the tail. Simple

Pseudocode example: unshift()

• ‘ ‘ if no node the length is 0

• ‘ ‘ list is empty then the head and tail will be A

• | A | node A is inserted, length is 1

• | B A | if the length is 1 then the next node of B will be A, and A will be the tail

the unshift method will allow you to locate the node at the start of a list

Visualization:

Here the head and tail are null

Now insert A in the list so head and tail is A

If there was A before the B insertion so the B will be the Head of the list

Code snippet

Then call list.unshift(‘A’)

list.unshift(‘B’)

console.log(list.showList()) // result B, A

Just include the unshift() inside the SinglyLinkedList class scope.

class SignlyLinkedList{

//include all methods

}

Remember: make sure all your code and call are written according to the scope.

2. Deletion - removes the existing elements.

In terms of deletion in singly linked lists, there are two types of methods that can be applied.

• pop() method: that can delete a node from the end of the list.

• shift() method: that can delete a node from the start of the list.

pop() method:

PseudoCode example: pop()

• ‘ ‘ if no node the length is 0 . return empty

• | A | if the list is not empty and at least one(1) node is in the list then head and head.next point to tail will be null and length will be set to = 0 . the head refer to the next node pointer will be null like:( this.head=null and this.tail=null length =0)

• | A B C D | suppose there is more than 1 node in the list

• Now define two nodes 1.currentNode\= this.head 2.lastNode\=this.tail and assume a temp variable like nodeToPop which will set for a new tail.

• Now the condition is set if there are nodes in the list. like- while(condition)

• It will traverse the whole list to the end and find the lastnode compared with the (currentnode and currentnode.next is == tail )each time iteration.

• When it finds a tail the traverse will stop and before the tail lastNode will be the currentNode then set it to nodeToPop.

• Then nodeToPop.next will be set to null like delete

• At last, the length of the list will be decreased by one the return the popped node

Visualization:

Here only one node exists. So if we need to delete the node we will find its pointer to the address and set it to null along with the head pointer

Temp variable is taken as “nodeToPop”

Here a temp variable traverses by comparing each element of the list to find the temp.next/tail.next =null or not .

currentNode = this.head and this.tail =currentNode.next for compare

Hence the temp variable finds the last element D is the tail because the condition match

nodeTopop will set to currentNode and currentNode = currentnode.next will be the tail

After the last item, travers the temp variable will set lastNode then break the traverse or it will delete all the elements. Now C will be the new tail

nodeTopop.next= null here D is deleted this.tail= nodeToPop here C is the new tail.

Code snippet

Suppose there are four items pushed A B C D

Then call list.pop()

console.log(list.showList()) // result A B C

Just include the pop() inside the SinglyLinkedList class scope.

shift() method :

shift() method will use deleting a node from the start of the list.

Pseudocode example : shift()

• ‘ ‘ if no node the length is 0 . return empty

• | A *pointer | if the list is not empty and at least one(1) node is in the list then the head will be replaced with the head.next node. so the tail will be null and the length will be set to = 0 the head refer to the next node pointer will be null like:

  ( this.head=null and this.tail=null length =0)

• | A B C D | suppose there is more than 1 node in the list

• Now define a variable like newHead=this.head that indicates current head

• Then the current head will delete and the second node will be the current head like this.head = newHead.next node

• At last, the length of the list will be decreased by one.

Visualization:

Here no node in the list so head and tail will set null and length also.

Above the picture there is a node that indicates head and points to head.next as the second node, as there is no second node so the head will remove and set null the tail will be as null length will be set null also.

Now the picture above shows there are three nodes where A point Head node and B point Head.next node. Now A node will replace by the B node where B will be set to the head node

At last A the old head node will be removed and second node B will be the new head node and the length will decrease by one.

Code Snippet

Suppose there are four items pushed A B C D

Then call list.shift()

console.log(list.showList()) // result B C D

Just include the pop() inside the SinglyLinkedList class scope.

So the insertion and deletion are completed and I hope you will practice it more.

Now I want to go to the next part like finding the list value of specific nodes and deleting and replacing nodes with another node then our journey of a singly linked list will end for a time now.

3. finding the specific node’s value or data.

How to find the specific value of nodes! well we will take the help of index.

Pseudocode example : get(index)

For getting the desired index we shall pass the specific index as an argument

• if the length of list is smaller than 0 or greater than the length it will return empty

• Let a variable will be head node set currentNode = this.head

• And let count variables which will count the iteration for the next node

• Now set a condition if the node is not null the iteration will continue to increase like while(head is exist)

• The count will increase every iteration and currenNode will traverse every node like currentNode = currentNode.next

If the desired index is found then the count will return the location of the index.

Visualization:

Here suppose our desired node index is F so the count is set to 0 and the head is O then it will traverse until the desired item is found, so the head will continue to increase line head.next and the count will increase too.

Code snippet

Suppose there are four items pushed A B C D

Then call list.get(2)

console.log(list.showList()) // result c

Just include the get(index) inside the SinglyLinkedList class scope.

4. update specific values in list

PseudoCode example : set(index,value)

For getting the desired index we shall pass the specific index as an argument and a value to replace

• First grub the specific index where the value will replace

• The value of the index will replace by the new value

Then if there is no node return null

Visualization:

The picture shows the c index value will be replaced by the k so currentNode that grub the index value will be replaced by the K.

Code snippet

Suppose there are four items pushed A B C D

Then call list.set(2,”k”)

console.log(list.showList()) // result A B K D

Just include the set(index,value) inside the SinglyLinkedList class scope.

5. insert a specific value in a position

insertAt(index,value) method is used for inserting an element into a specific index. So we need index help to find the position and insert the value in it.

Pseudocode example : insertAt(index,value)

For getting the desired index we shall pass the specific index as an argument

• if the length of the list is smaller than 0 or greater than the length it will return empty

• If the desired index is at the start of the list then call the unshift() method because the unshift() method will insert a node from the start of the list.

• If the desired index is the last or tail of a list then call the push() method that will insert the tail of a list node.

• If the index value is at another place then set a temp variable name nodeToInsert which will return before the desired index and you can use get(index) method like get(index -1)

• Now set another variable like getPrevNode its next node will set the nodeToInsert.next node

• Then getPrevNode.next will set nodeToInsert

• Then the length of the list will be increased by one.

Visualization:

Here the above picture shows C is in index 2 where F will be inserted at index 2 and C will be at index 3 and the length will be increased by one.

Code snippet:

Suppose there are four items pushed A B C D

Then call list.insertAt(1,”L”)

console.log(list.showList()) // result A L B K D

Just include the insertAt(index,value) inside the SinglyLinkedList class scope.

6. now remove the specific index value of the list

remove(index)

PseudoCode example : remove(index)

For getting the desired index we shall pass the specific index as an argument

• if the length of the list is smaller than 0 or greater than the length it will return empty

• Now identify two positions of list length head and tail.

• If the desired index is at the start of the list then call the shift() method because shift() method will use deleting a node from the start of the list.

• If the desired index is the last or tail of a list then call the pop() method that will delete the tail of a list node.

• If the index value is at another place then set a temp variable name preNodeToOfRemove which will return before the desired index and you can use get(index) method like get(index -1)

• Now set another variable like nodeToRemove and set the preNodeToOfRemove.next index

• Then preNodeToOfRemove.next will set nodeToRemove.next

• Then the length of the list will be decreased by one.

Visualization:

Here suppose the E index will be removed. So get the previous index of desired index calling get(index -1) that would be D. Now E will be set in a temp variable which is pointing D next index then temp index will be replaced by the F index. And length will decrease by one. Remember not null never be set just replacement of index is needed.

Code snippet

Note: we can optimized our code remove() inside the else{} scope: like below

Line no 10 can be set like:

{ preNodeOfremove.next \= preNodeOfremove.next.next }

Suppose there are four item pushed A B C D

Then call list.remove(2)

console.log(list.showList()) result A B D

Just include the remove(index) inside the SinglyLinkedList class scope.

Time complexity of singly linked list Space complexity of singly linked list

Create nodes delete nodes update notes TC and SC are bellow

Create a list is O(1)

Push to a list O(1)

Pop to a list O(n)

showlist() loop to all O(n)

Shift a node from list O(1)

Unshift a node from list O(1)

Remove at index from a list O(n)

Update a value from a list O(n)

insertAt a position into a list O(n)

note: since tehre are not space creation in these operations so SC will be always O(1)

Create a list is O(1)

Push to a list O(1)

Pop to a list O(n)

showlist() loop to all O(1)

Shift a node from list O(1)

Unshift a node from list O(1)

Remove at index from a list O(1)

Update a value from a list O(1)

insertAt a position into a list O(1)

for more specific visualization you can visit:

That is the end of the discussion. If you have any queries please comment. There may be some disagreement with the logic. Please tell me. Happy reading