Basic Data Structure

Data Structure!!!

May be the most dangerous weapon for programmers to defeat disobedient data. Today we will discuss about few topics on this weapon. First see the definition of Data structure.

Data structure :

A data structure is a specialized format for organizing, processing, retrieving and storing data. While there are several basic and advanced structure types, any data structure is designed to arrange data to suit a specific purpose so that it can be accessed and worked with in appropriate ways.

Huh, after an honorable definition, let’s get into the game.

In this article, the data structures we will be discussing/implementing are:

• Stack
• Queue
• Linked list
• Hash table

Stack:

Firstly we will talk about the easiest data structure about stack. Stack follow a basic principle that is called LIPO (Last In First Out).That means we must delete the last element that pushed in stack. Let’s try to understand with the help of a real life example. When we browse a website, we may click link to go to another page. In that time web browser push an element in stack and if we click at back button, it removes last value and back us to previous page.

Let’s try to see as a programmer,

class Stack {
constructor() {
// create our stack, which is an empty object
this.storage = {};
}
// this method will push a value onto the top of our stack
push(value) {
}
// this method is responsible for popping off the last value and returning it
pop() {
}
// this will peek at the last value added to the stack
peek() {
}
}

We see here are three different methods and we can understand to see the name of those methods as well as comments associated with it. Now go about to know the inner view of those methods.

Push():

class Stack {
constructor() {
this._storage = {};
this._length = 0; // this is our length
}
push(value) {
// so add the value to the top of our stack
this._storage[this._length] = value;
// since we added a value, we should also increase the length by 1
this._length++;
}
/// …..
}

Is it easy? Exactly!!! Simply we take an empty object and initialize length in constructor and add element in the object through push method.

Pop():

It is a cruel method that remove the last value that was added to our stack and then return that value. It high time to reveal his inner view.

pop() {
const lastValIndex = this._length — 1;
if (lastValIndex >= 0) {
// we first get the last val so we have it to return
const lastVal = this._storage[lastValIndex];
// now remove the item which is the length — 1
delete this._storage[lastValIndex];
this._length — ;
return lastVal;
}
return false;
}

Peek():

Its similar to the pop method, but this time, we do not remove the last item.

peek() {
const lastValIndex = this._length - 1;
const lastVal = this._storage[lastValIndex];
return lastVal;
}

So finally we have done our first data structure.Lets go about another one.

Queue:

It looks similar with stack but its follow FIFO (First In First Out) principle.

Lets See The core Implementation:

class Queue {
constructor() {
this.queue = [];
this.length = 0;
}
enqueue(value) {
}
dequeue() {
}
peek() {
}
}

Here also have three methods as stack. Let’s have a crack at inner procedure.

Enqueue():

enqueue(value) {
// add the value to the start of the queue
this.queue.unshift(value);
// update our length
this.length++;
}

This is quite a simple method that adds a value to the end of our queue. Unshift method add this element .

dequeue():

dequeue() {
if (this.length > 0) {
// pop off the value that was added first
this.queue.pop();
// decrement the length
this.length--;
}
}

The final method to implement is the peek method, which is an easy one:

peek() {
const lastValIndex = this.length - 1;
if (lastValIndex >= 0) {
return this.queue[lastValIndex];
}
return false;
}

Now let’s move on linked list.

Linked list:

A linked list is an ordered collection of data elements. A data element can be represented as a node in a linked list. Each node consists of two parts: data & pointer to the next node.

Visually, it looks like this:

Lets see how can we implement it.

const list = new LinkedList();
list.add("red");
list.add("orange");
list.add("yellow");
// get the second item in the list
console.log(list.get(1));       // "orange"
// print out all items
for (const color of list) {
console.log(color);
}
// remove the second item in the list
console.log(list.remove(1));    // "orange"
// get the new first item in the list
console.log(list.get(1));       // "yellow"
// convert to an array
const array1 = [...list.values()];
const array2 = [...list];

Lets move on another one.

Hash Table:

A hash table is a data structure that implements an associative array, which means it maps keys to values. A JavaScript object is a hash table, as it stores key-value pairs.

Lets see the core implementation of hash Table:

function HashTable(obj)
{
this.length = 0;
this.items = {};
for (var p in obj) {
if (obj.hasOwnProperty(p)) {
this.items[p] = obj[p];
this.length++;
}
}
this.setItem = function(key, value)
{
var previous = undefined;
if (this.hasItem(key)) {
previous = this.items[key];
}
else {
this.length++;
}
this.items[key] = value;
return previous;
}
this.getItem = function(key) {
return this.hasItem(key) ? this.items[key] : undefined;
}
this.hasItem = function(key)
{
return this.items.hasOwnProperty(key);
}
this.removeItem = function(key)
{
if (this.hasItem(key)) {
previous = this.items[key];
this.length — ;
delete this.items[key];
return previous;
}
else {
return undefined;
}
}
this.keys = function()
{
var keys = [];
for (var k in this.items) {
if (this.hasItem(k)) {
keys.push(k);
}
}
return keys;
}
this.values = function()
{
var values = [];
for (var k in this.items) {
if (this.hasItem(k)) {
values.push(this.items[k]);
}
}
return values;
}
this.each = function(fn) {
for (var k in this.items) {
if (this.hasItem(k)) {
fn(k, this.items[k]);
}
}
}
this.clear = function()
{
this.items = {}
this.length = 0;
}
}
}

That’s all for today. Happy learning.