DS with JS — Linked Lists — II

Data Structures with JavaScript — Chapter Two — Doubly Linked Lists

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

A doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.

Before Proceeding further…

This post is continued from DS with JS — Linked Lists, If you haven’t gone through that yet, make sure you do before proceeding further…

Core

Image for post
Image for post

⚜️ The list

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

Lets’ begin!!

Image for post
Image for post
Initial List

🔅 Append

append( item ) {
let node = new Node( item );
if(!this.head) {
this.head = node;
this.tail = node;
} else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node
}
}
Image for post
Image for post
Append Operation

🔅 AppendAt

appendAt( pos, item ) {
let current = this.head;
let counter = 1;
let node = new Node( item );
if( pos == 0 ) {
this.head.prev = node
node.next = this.head
this.head = node
} else {
while(current) {
current = current.next;
if( counter == pos ) {
node.prev = current.prev
current.prev.next = node
node.next = current
current.prev = node
}
counter++
}
}
}
Image for post
Image for post
AppendAt Operation

🔅 Remove

remove( item ) {
let current = this.head;
while( current ) {
if( current.data === item ) {
if( current == this.head && current == this.tail ) {
this.head = null;
this.tail = null;
} else if ( current == this.head ) {
this.head = this.head.next
this.head.prev = null
} else if ( current == this.tail ) {
this.tail = this.tail.prev;
this.tail.next = null;
} else {
current.prev.next = current.next;
current.next.prev = current.prev;
}
}
current = current.next
}
}
Image for post
Image for post
Remove Operation

🔅 RemoveAt

removeAt( pos ) {
let current = this.head;
let counter = 1;
if( pos == 0 ) {
this.head = this.head.next;
this.head.prev = null;
} else {
while( current ) {
current = current.next
if ( current == this.tail ) {
this.tail = this.tail.prev;
this.tail.next = null;
} else if( counter == pos ) {
current.prev.next = current.next;
current.next.prev = current.prev;
break;
}
counter++;
}
}
}
Image for post
Image for post
RemoveAt Operation

🔅 Reverse

reverse(){
let current = this.head;
let prev = null;
while( current ){
let next = current.next
current.next = prev
current.prev = next
prev = current
current = next
}
this.tail = this.head
this.head = prev
}
Image for post
Image for post
Reverse Operation

🔅 Swap

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

🔅 IsEmpty & Length

length() {
let current = this.head;
let counter = 0;
while( current !== null ) {
counter++
current = current.next
}
return counter;
}
isEmpty() {
return this.length() < 1
}
Image for post
Image for post
IsEmpty & Length Operation

🔅 Traverse

traverse( fn ) {
let current = this.head;
while( current !== null ) {
fn(current)
current = current.next;
}
return true;
}
Image for post
Image for post
Traverse Operation

🔅 TraverseReverse

traverseReverse( fn ) {
let current = this.tail;
while( current !== null ) {
fn(current)
current = current.prev;
}
return true;
}
Image for post
Image for post
TraverseReverse Operation

🔅 Search

search( item ) {
let current = this.head;
let counter = 0;
while( current ) {
if( current.data == item ) {
return counter
}
current = current.next
counter++
}
return false;
}
Image for post
Image for post
Search Opeartion

Practice

  1. GeekForGeeks Double Linked List
  2. HackerRank Linked Lists

One more important thing..

About this post

This post is the second instalment to its series “DS with JS”. There will be more in this series. Next will be on next Thursday Morning. Stay tuned!

That’s It

Happy Coding !!


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.