Using JavaScript prototype

Introduction

In the JavaScript world, objects inherent functionality through prototypal inheritance. An object's prototype acts as a blueprint for its instance. Methods or properties defined at the object's prototype are linked to the object instance, and at the time of execution, those are discovered by waking up the prototype chain.

Foundation

Implementing a basic node that can hold some data.

function Node (data) {
  this.data = data
 }

Defining methods in the function's prototype.

Node.prototype.setData = function(data) {
   this.data = data
 }
 
 Node.prototype.getData = function() {
   return this.data
 }

Giving it a try.

let node = new Node(10)
console.log("Data: ", node.getData()) // Data: 10

Forming a Linked List

Extending node to hold a reference to the next subsequent node, forming a linked list data structure.

function LinkedNode(data, next) {
  if(!new.target) return new LinkedNode()
  Node.call(this, data)
  this.next = next
}

Linking up the prototype, which will allow methods to be discovered up the prototype chain.

LinkedNode.prototype = Object.create(Node.prototype)
 
Node.prototype.setNext = function(next) {
  this.next = next
}
 
Node.prototype.getNext = function() {
  return this.next
}

LinkedNode.prototype.constructor = LinkedNode // Restoring the constructor

Giving it a try.

const node1 = new LinkedNode(10)
const node2 = new LinkedNode(11)
node1.setNext(node2)

Stack using Linked List

Implementing a Stack using the Linked Node.

function Stack() {
  if(!new.target) return new Stack()
  this.head = undefined
  this.size = 0
}

Stack.prototype.push = function(data) {
  let node = new LinkedNode(data)
  node.setNext(head)
  this.head = node
  this.size++
}

Stack.prototype.pop = function() {
  if(!this.size) return undefined
  let node = this.head
  this.head = head.getNext()
  this.size--
  return node.getData()
}

Stack.prototype.isEmpty = function() {
  return this.size === 0
}

Stack.prototype.top = function() {
  return this.size ? this.head.getData() : undefined
}

Trying it out

let stack = new Stack()
stack.push(10)
stack.push(11)
stack.push(12)
console.log("pop: ", stack.pop()) // pop: 12
console.log("peek: ", stack.top()) // peek: 11

In the Wild

About that image on top, that's a problem that we will solve with the help of the above stack implementation. Thus shedding light when stacks are useful.

The problem statement is to find rising trends in stock price based on its historic data. The rising trend means finding the longest consecutive rise in stock price.

We will try to understand the solution in a very efficient manner, which is through a picture.

explanation

The example dataset contains the price for six consecutive days.

price = [8, 4, 5, 2, 7, 5]

To calculate the span or trend, the algorithm needs to scan the whole list, keeping track of the highest price seen so far. Tracking of the highest element is done with the stack data structure. Elements are pushed into the stack when they are first encountered. When a greater element is encountered, the stack is popped until a larger element is on the top of the stack.

Stack Operation per day

Implementation

function findTrend(dataset){
  const trends = []
  const trackingHighest = new Stack()
  let previousHighestDate
  let trend
  
  const isCurrentDateGreater = (current) => dataset[current] > dataset[trackingHighest.top()]
  const ensureNoPreviousSmallerDate = (current) => { while(!trackingHighest.isEmpty() && isCurrentDateGreater(index)) trackingHighest.pop() }
  const getPreviousHighestDate = () => !trackingHighest.isEmpty() ? -1 : trackingHighest.top()
  const saveTrend = (current, trend) => trends[current] = trend

  for(let current = 0; current < dataset.length; current++) {
    ensureNoPreviousSmallerDate(current)
    previousHighestDate = getPreviousHighestDate()
    trend = current - previousHighestDate
    saveTrend(current, trend)
    trackingHighest.push(current)
  }
  return trends
}

Giving it a try.

let price = [8, 4, 5, 2, 7, 5]
let trend = findTrend(price)
console.log("Trend: ",trend) // Trend: [1, 1, 2, 1, 4, 1]

Conclusion

JavaScript is an amazing language, and understanding how a language works is crucial.

References

The Stock Span Problem - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
Loading...
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
Alibh Deori

Alibh Deori