DS with JS — Linked Lists

Data Structures with JavaScript — Chapter One — Linked Lists

Gaurav Mehla
Apr 4, 2018 · 5 min read
Image for post
Image for post

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.

⚠️ If you wan’t to learn more about linked-lists click here because in this post I will not cover the theoretical concepts about linked-list. I will just go straight into coding.

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.
Image for post
Image for post
this while loop is the one on which 75% of linkedLists depends…

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!!

Image for post
Image for post
Initial List

❗️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;
}
Image for post
Image for post
Append Operation

🔅 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;
}
Image for post
Image for post
AppendAt Operation

🔅 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;
}
Image for post
Image for post
Remove Operation

🔅 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;
}
Image for post
Image for post
RemoveAt Operation

🔅 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
}
Image for post
Image for post
Reverse Operation

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.

Image for post
Image for post
pffff….finally I made it after spending 3 hours in just dragging and dropping.. but hope so it will help you :)

🔅 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
}
Image for post
Image for post
Swap Operation

🔅 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
}
Image for post
Image for post
IsEmpty & Length Operation

🔅 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;
}
Image for post
Image for post
Traverse Operation

🔅 Display

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

🔅 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;
}
Image for post
Image for post
Search Operation

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.

Practice

One more important thing…

About this post

This post is the first of its series “DS with JS”. There will be more in this series. Next will be on next Monday Morning at 08:00 AM (UTC+05:30). Stay tuned!

That’s It

Happy Coding !!

🎧 Listening to “Just a dream…” . Great music for those who are motivated and dreaming about how their life is going to be change soon — Like me :)

Image for post
Image for post

If you like this article, please give it some claps 👏 and share it! If you do not like this post or have any type of questions regarding anything that i mentioned in this post. Feel free to ask me. Just post an issue in my “Ask Me Anything” by clicking here.

For more like this, follow me on Medium or Twitter. To ask a Question visit this link. More about me on my website.

_devblogs

Stories for Full-Stack Web developers which help them in…

Gaurav Mehla

Written by

Software engineer & Web hacker. Spent 30+% of life on playing with JS

_devblogs

_devblogs

Stories for Full-Stack Web developers which help them in pursuing their goals as a developer, mastering the modern web technologies and *hacking the web.

Gaurav Mehla

Written by

Software engineer & Web hacker. Spent 30+% of life on playing with JS

_devblogs

_devblogs

Stories for Full-Stack Web developers which help them in pursuing their goals as a developer, mastering the modern web technologies and *hacking the web.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store