Data Structures

Question 1

How do you implement a stack in JavaScript?

Answer 1

Just use an array with push and pop methods:

var myStack = [];

//push
myStack.push(1);
myStack.push(2);
myStack.push(3);

//pop
myStack.pop(); //3
myStack.pop(); //2
myStack.pop(); //1

Question 2

How do you implement a queue in JavaScript?

Answer 2

Just use an array with push and shift methods:

var myQueue = [];

//push
myQueue.push(1);
myQueue.push(2);
myQueue.push(3);

//pop
myQueue.shift(); //1
myQueue.shift(); //2
myQueue.shift(); //3

Question 3

How do you implement a Singly Linked List in JavaScript?

Answer 3

In a singly linked list, you get the head, and each object points to the next. So…

function LinkedList(){  
  this.head = null;
}

LinkedList.prototype.push = function(val){
  var node = {
    value: val,
    next: null
  }
  if(!this.head){
    this.head = node;      
  }
  else {
    current = this.head;
    while(current.next){
      current = current.next;
    }
    current.next = node;
  }
}

var sll = new LinkedList();

//push node

sll. push(2);
sll. push(3);
sll. push(4);

//check values by traversing LinkedList

sll. head; //Object {data: 2, next: Object}
sll. head.next; //Object {data: 3, next: Object}
sll. head.next.next; //Object {data: 4, next: null}

Question 4

How do you create a Doubly Linked List in JavaScript?

Answer 4

For doubly linked list there will be a link backward to the previous element.

function DoublyLinkedList(){
   this.head = null;
}

DoublyLinkedList.prototype.push = function(val){
  var head = this.head,
        current = head,
        previous = head,
        node = {
          value: val,
          next: null,
          previous: null  
        };

  if(!head){
    this.head = node;
  }
  else{
    while(current && current.next){
      previous = current;
      current = current.next;
    }
    current.next = node;
    node.previous = current.next;
  }  
}

Question 5

How do you remove a node from a Singly Linked List?

Answer 5

case -1: your targeted node is in the head. you have to replace the head with the next node

case -2: your targeted node is in the tail. you just have to remove it from the tail. Hence next of the node before the tail will be null.

case-3: your targeted node is in the middle of the LinkedList, you have to make the node after your targeted node to be the next node of the node before your targeted node.

LinkedList.prototype.remove = function(val){
    var current = this.head;
    //case-1
    if(current.value == val){
       this.head = current.next;     
    }
    else{
      var previous = current;

      while(current.next){
        //case-3
        if(current.value == val){
          previous.next = current.next;          
          break;
        }
        previous = current;
        current = current.next;
      }
      //case -2
      if(current.value == val){
        previous.next == null;
      }
    }
  }

Question 6

How do you reverse a Singly Linked List?

Answer 6

Just walk through the LL and put the nodes in an array. This would be easier other than using remove function (if LL have one), because to remove a single item from the end of the SLL you have to walk all way to the end of the SLL every single time. Here you are just walking once.

function reversesll(sll){

if(!sll.head || !sll.head.next) return sll;

  var nodes=[], 
        current = sll.head;

  //storing all the nodes in an array
  while(current){
    nodes.push(current);
    current = current.next;
  }

var reversedLL = new LinkedList();

reversedLL.head = nodes.pop();
current = reversedLL.head;

  var node = nodes.pop();  
  //make sure to make next of the newly inserted node to be null
  //other wise the last node of your SLL will retain its old next.
  while(node){
    node.next = null;
    current.next = node;

    current = current.next;
    node = nodes.pop();
  }
  return reversedLL;
}

//create the LL
var sll = new LinkedList();
sll.push(1);
sll.push(2);
sll.push(3);
sll.push(4);
sll.push(5);

//test it
reversesll(sll);
//{head: {value:5, next:{value: 4, next: {value: 3, next: {value:2, next:{value:1, next: null}}}}}}

Question 7

How do you reverse a Doubly Linked List?

Answer 7

function reverseDoublyLL(dll){
   var head = dll.head,
       current = dll.head,
       tmp;
   while(current){
      tmp = current.next;
      current.next = current.previous;
      current.previous = tmp;
      if(!tmp){
         //set the last node as header
         dll.head = current;
      }
      current = tmp;
   }
  return dll;
}

Question 8

How do you get the kth node from the end of a linked list?

Answer 8

Set two counters in motion, the second once the first is k steps in. Once the first runs out of nodes you can stop.

function kthFromEnd(sll, k){
  var node = sll.head,
        i = 1,
        kthNode;

  //handle, 0 or negative value of k
  if (k<=0) return;

  while(node){
    if (i == k) {
      kthNode = sll.head;
    } else if (i-k>0) {
      kthNode = kthNode.next;
    }

i++;

node = node.next;   }   return kthNode; }

//create the LL
var sll = new LinkedList();
sll.push(1);
sll.push(2);
sll.push(3);
sll.push(4);
sll.push(5);

//test at least once
kthFromEnd(sll, 1); //Object {value: 5, next: null}
kthFromEnd(sll, 3); //Object {value: 3, next: Object}