DS with JS — Linked Lists

Data Structures with JavaScript — Chapter One — Linked Lists

Introduction

A Linked List is a linear collection of data elements, called nodes, pointing to the neighbouring node by means of pointer.

Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node or previous node in the sequence.

Core

The most important part of a linked list is a node. It consist of two things —

1. Data
2. Pointers
In Single Linked Lists there is only one pointer (next ) but in Double Linked lists there are two pointers (prev & next ). There can be more than two pointers also. It totally depends on your purpose of creating them.

Whenever we create an instance of our `LinkedList` class, the `constructor` executes and it create a `head` node with both data and next as `null`. Then we use its `append` method to insert items into this list. In this post, we will go through the following methods/operations on Linked Lists —

⚜️ The list

1. Append
2. AppendAt
3. Remove
4. RemoveAt
5. Reverse
6. Swap
7. IsEmpty & Length
8. Traverse
9. Display
10. Search

and a lot more… So, without further ado…

Lets’ begin!!

❗️All the code snippets you will see below are just Pseudo code. If you want to see working code — click here

🔅 Append

`append( item ) {  let current = this.head;  let newNode = new Node(item)  while( current.next !== null ) {    current = current.next  }  current.next = newNode;  return true; }`

🔅 AppendAt

`appendAt( pos, item ) {  let counter = 0;  let current = this.head;  let newNode = new Node(item);  while( current.next !== null ) {    if( counter === pos ){      newNode.next = current.next      current.next = newNode      return true;    }    current = current.next    counter++;  }  return false; }`

🔅 Remove

`remove( item ) {   let current = this.head;   while( current !== null ) {     let previous = current;     current = current.next;     if( current.data === item ) {       previous.next = current.next;       return true;     }   }   return false; }`

🔅 RemoveAt

`removeAt( pos ) {  let counter = 0;  let current = this.head;  while( current !== null ) {    let previous = current;    current = current.next    if( counter === pos ){      previous.next = current.next;      return true;    }    counter++;  }  return false; }`

🔅 Reverse

`reverse() {   let current = this.head.next;   let prev = null;   let next;   while(current !== null) {     next = current.next     current.next = prev     prev = current     current = next   }   this.head.next = prev   return true }`

It is easy to understand what we see instead of what we read. So, If the mechanism of this `reverse` function is still unclear to you, I have made a `gif` in order to show you how the execution goes.

🔅 Swap

`swap( nodeOne, nodeTwo ) {  let current = this.head;  let counter = 0;  let firstNode;  while( current !== null ) {    current = current.next;    if( counter == nodeOne ){      firstNode = current;    } else if( counter == nodeTwo ) {      let temp = current.data;      current.data = firstNode.data;      firstNode.data = temp;    }    counter++;  }  return true }`

🔅 isEmpty & Length

`length() {  let current = this.head;  let counter = 0;  while( current.next !== null ) {    current = current.next    counter++;  }  return counter;}`
`isEmpty() {  return this.length() < 1}`

🔅 Traverse

If you want to execute a function over each node, then you can use `traverse`. Just pass the function as shown in the example —

`traverse( fn ) {  let current = this.head;  while( current.next !== null ) {    fn(current)    current = current.next;  }  return true; }`

🔅 Display

`display() {  let current = this.head;  let elements = [];  while( current !== null ) {   elements.push( current.data );   current = current.next  }  return elements.join(" ");}`

🔅 Search

`search( item ) {   let current = this.head.next;   let counter = 0;`
`   while( current ) {     if( current.data == item ) {      return counter     }     current = current.next     counter++   }   return false;}`

There are still a lot of things that we can do with linked-lists. Never stop doing practice. Explore yourself and think of problems by yourself. The more you think of problems — the more you brain will create links with Data Structures. Just keep checking DSwithJS Github repository for more.