Introduction to Data Structures and Algorithms with JavaScript.
Muriithi Gakuru
Posted on February 21, 2022
In this post we're going to be looking into data structures and algorithms.
Hopefully this will help to improve your skills and understanding.
Let's start with a good old fashioned definition
Data Structures - this is an organization of data so that it can be used efficiently. It provides a way so that data can be stored, organized, retrieved and used efficiently.
This is an introduction to Data Structures(DS) so we'll get straight into it.
Arrays
Similar to other programming languages, array objects in JavaScript enable storing a collection of multiple items under a single variable name. One important factor about arrays in js are not primitives meaning that the data are not objects and have no underlying methods.
Examples of primitive types in js are; string, number, bigint, boolean, undefined, symbol, and null.
Let's give some characteristics of arrays.
JavaScript arrays are resizable and can contain a mix of different data types.
Arrays must be accessed using integer indices. Elements cannot be accessed using strings because they are not associative.
The first element of the array is always 0. One might think that this is common knowledge but in some languages the first element is 1.
- - FORTRAN
- - COBOL
Constructor
Array()
This creates a new Array
object
// Initializing while declaring
// Creates an array having elements 10, 20, 30, 40, 50
var house = new Array(10, 20, 30, 40, 50);
//Creates an array of 5 undefined elements
var house1 = new Array(5);
//Creates an array with element 1BHK
var home = new Array("!BHK");
How to create and array
// 'fruits' array created using array literal notation.
const fruits = ['Apple', 'Banana'];
console.log(fruits);
// ['Apple', 'Banana']
console.log(fruits.length);
// 2
// 'fruits' array created using the Array() constructor.
const fruits = new Array('Apple', 'Banana');
console.log(fruits);
// ['Apple', 'Banana']
console.log(fruits.length);
// 2
// 'fruits' array created using String.prototype.split().
const fruits = 'Apple, Banana'.split(', ');
console.log(fruits);
['Apple', 'Banana']
console.log(fruits.length);
// 2
The above example shows how to create an array from a string separated using a comma. We can also create a string from an array using the join()
method and add a comma separator.
const fruits = ['Apple', 'Banana'];
const fruitsString = fruits.join(', ');
console.log(fruitsString);
// "Apple, Banana"
Functions to use with Array
Array.isArray()
Returns true if the argument is an array, or false otherwise.
Array.prototype.reverse()
Reverses the order of the elements of an array in place. (First becomes the last, last becomes first.)
Array.prototype.unshift()
Adds one or more elements to the front of an array, and returns the new length of the array.
Array.prototype.splice()
Adds and/or removes elements from an array.
This is just the tip of the iceberg. There is more to arrays and to their uses here.
Queue
Think of a queue in a bank. It's probably a 20th century example but applicable. The first person to join the queue gets served first and leaves. Only then do people who joined after are served, first one in first one out.
This data structure uses the First In First Out(FIFO) principle. Where the dequeue is the removal of the first element and the enqueue is the addition of an element onto the queue as shown below.
Queue has the following methods:
-
enqueue
- adds an element at the end.
// enqueue function
enqueue(element)
{
// adding element to the queue
this.items.push(element);
}
This function adds an element at the back of a queue. We have used push() method of array to add an element at the end of the queue.
-
dequeue
- removes an element at the front of the queue.
// dequeue function
dequeue()
{
// removing element from the queue
// returns underflow when called
// on empty queue
if(this.isEmpty())
return "Underflow";
return this.items.shift();
}
This function removes an element from the front of a queue . We have used shift method of an array to remove an element from the queue.
-
front
- this gets the first element.
// front function
front()
{
// returns the Front element of
// the queue without removing it.
if(this.isEmpty())
return "No elements in Queue";
return this.items[0];
}
This function returns the front element of the queue. We simply return the 0th element of an array to get the front of a queue.
-
size
- gets the number of elements in the queue -
isEmpty
- shows whether the queue is empty.
// isEmpty function
isEmpty()
{
// return true if the queue is empty.
return this.items.length == 0;
}
In this function we have used the length property and if the array length is 0 then the queue is empty.
Stack
The name stack comes from the analogy to a set of physical items. Let's use books for instance. I'll drop an image just for context.
We start by placing one book and then each consequent book is placed on top of the other. When we need to access the first book placed, we'll have to take each book out starting with the one that was placed last.
Some pancakes would suffice too! Let's stack them up ;)
This is the Last In First Out (LIFO) principle.
JavaScript Array type provides the push() and pop() methods that allow you to use an array as a stack.
push()
The push()
method allows you to add one or more elements to the end of the array. The push() method returns the value of the length property that specifies the number of elements in the array.
If you consider an array as a stack, the push() method adds one or more element at the top of the stack. The following example creates an empty array named stack and adds five numbers, one by one, at the end of the stack array. It is like to push each number into the top of the stack.
Try it out.
pop()
The pop() method removes the element at the end of the array and returns the element to the caller. If the array is empty, the pop() method returns undefined.
The following example shows how to pop elements from the top of the stack using the pop() method.
Linked List
A linked list or a singly linked list is a representation of a list of values like an array, but each item in the list consists of a single object that has two properties:
The value property stored inside the object
The next property(node) that points to the next object
It is a collection of nodes in which each node is pointing to next node and last node points to null.
The linked list data structure value can be of any valid JavaScript data types (string, number, boolean, object, etc)
Declaration of type node for Linked List
We have to create a data structure or Node which contains two parts i.e, first part will contain the data to be stored and second will store address of next such node. We can create this by using user defined data type.
Linked lists is a more superior data structure. I'll update this post once my understanding is good enough to give conclusive information.
Conclusion
"Data structures is fun" may be a statement you may not want to hear but they are very interesting. The have grown on me, to be honest.
If you're one for solving puzzles I may, or may not have a challenge for you ;)
Let me not go there though.
Please don't google the Tower of Hanoi
challenge. It's too easy for your level.
Coffee break!!
Cheers!
Posted on February 21, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
November 30, 2024