Forem: Fernando Baptistella

Graph - Data Structure & Algorithm Part VIII

Fernando Baptistella — Mon, 28 Dec 2020 22:00:21 +0000

Hello everyone, today I intend to continue this series that we discussed data structure and for this post we will learn graphs. This incredible structure you can apply to many problems in the real world, so it is one of the most important structures and also very common in interview questions.

So, let's dive into this new adventure!

💭 "The trick is to fix the problem you have, rather than the problem you want." - Bram Cohen

Outline

What is a Graph?
Basic concepts.
The main operations and properties.
Learning BFS and DFS functions.

Graph

Many people often confuse a graph with a tree structure, and that's happened because a tree is a type of graph!

Basically, a graph is a non-linear structure of a set of vertices V connected by edges E that can be represented as ordered pair of vertices G(V,E) .

More precisely, a graph is composed of paths that contain adjacency vertices connected by edges. Usually, you can find many books and articles using different terms to refer to vertices and edges, the most common of which are:

Vertex: Nodes or points;
Edges: Lines, links or arcs;

▪️ Graph visualization

One of the most interesting things that make graphs a powerful structure is how they can represent a lot of information for some applications. There are many examples that we can use and the most common are a network of cities, streets, flights, ferries, railway maps, social network connections, and so on...

From theses examples, a graph structure can obtain a lot of information, such as how many cities are close to another or which is the sort path between two cities, for example. Can you see how powerful this structure can be?

Even though a graph is just a collection of nodes and edges, there are two ways to represent it, which are:

Adjacency Matrices

As the name suggests, this representation uses a square matrix where rows and columns mean that there is a relationship from one vertex to another. We can see how it works in the image below.

Figure 1: Adjacency Matrice visualization.

As we can see, the matrix represents which vertices are connected by edges, we can simply find out if there is a relationship between the vertices looking at the matrix.

Adjacency List

Is the most common and efficient way to represent a graph, because creates an array that can store all vertices in a list for each vertex of the graph. Using the same set used in the adjacency matrix above:

Figure 2: Adjacency list visualization.

▪️ Graph Representations

After talking about visualizations, the next step is to learn how many types of a graph exists. Here we will see how the vertices are organized and connected.

Directed or undirected

Directed

In this type of graph, the edges are directed from one vertex to another. As we can see, the edge between 0 and 1 vertices is directed, right?

Figure 3: Directed graph representation.

Undirected

Unlike the directed graph, this type of graph has all vertices pointing towards each other, that is, all edges are bidirectional.

Figure 4: Undirected graph representation.

Cyclic or acyclic

A cycle graph means if the graph contains a path that begins at a given vertex and after few vertices ends at the same starting vertex. The example below contains the following cycle: 5 -> 2 -> 1 -> 4.

Figure 5: Cyclic graph representation.

▪️ Basic operations

Okay, now that we already understand what a graph is, let’s see how to implement it. First thing first, we need to create our main class and, as we have seen, there are two ways to build this structure and will use the adjacency list representation, where a key and all its connections are associated.

Let's see how below:

class Graph {
    constructor() {
        this.adjacencyList = {}
    }
    ...

}

Simple right? 😁 We just need to initialize the adjacencyList variable that will be used as a dictionary to add key-value pairs. The next step is to know how to insert a vertex in our graph using the dictionary that was created.

When a new vertex is added to the structure, it takes only a constant time, the time complexity of O(1). This is because we just need to add the new element to the array.

Great! Moving forward, we need to use a real-world example to facilitate our understanding and we will use a social network to exemplify operations.

addVertex(vertex){
    this.adjacencyList[vertex] = [];
}

A social network needs some users, right? So, let's fill it out by adding some people from middle-earth using the following code:

const middle_earth = new Graph();

middle_earth.addVertex('Gandalf');
middle_earth.addVertex('Saruman')
middle_earth.addVertex('Frodo')
middle_earth.addVertex('Billy')
middle_earth.addVertex('Sean')
middle_earth.addVertex('Merry')
middle_earth.addVertex('Sméagol')

Well, something is missing from our social network. We need interactions between the users, the next step is to create some connections between the vertices created.

As discussed earlier, the main differences between these types of graphs are in the fact that only the undirected function creates connections on both sides.

The code below shows how we can create connections using directed and undirected approaches.

addEdgeDirected(vertex1, vertex2) { 
    if(!this.adjacencyList[vertex1]){
       this.addVertex(vertex1)
    }
    if(!this.adjacencyList[vertex2]){
       this.addVertex(vertex2)
    }

    if(!this.adjacencyList[vertex1].includes(vertex2))
        this.adjacencyList[vertex1].push(vertex2);   
}

addEdgeUndirected(vertex1, vertex2) { 
    if(!this.adjacencyList[vertex1]){
        this.addVertex(vertex1)
    }
    if(!this.adjacencyList[vertex2]){
        this.addVertex(vertex2)
    }

    if(!this.adjacencyList[vertex1].includes(vertex2))
        this.adjacencyList[vertex1].push(vertex2);    

    if(!this.adjacencyList[vertex2].includes(vertex1))
        this.adjacencyList[vertex2].push(vertex1); 
}

In this example of social networking, we will use the undirected approach, however, the directed type graph also can be used. Moving on, let's now imagine that Gandalf added some hobbits and a wizard to his social network.

middle_earth.addEdgeUndirected('Gandalf', 'Billy');
middle_earth.addEdgeUndirected('Gandalf', 'Merry')
middle_earth.addEdgeUndirected('Gandalf', 'Sean')
middle_earth.addEdgeUndirected('Gandalf', 'Frodo')
middle_earth.addEdgeUndirected('Gandalf', 'Saruman')

After that, our graph looks something like this:

Figure 6: Middle-earth network representation.

Awesome! 😁

Okay, moving forward with the discussion, let's imagine the scenario where the Sméagol user had a bad behaviour and it is necessary to removed it, how we can do this?

For now, we have no way to remove any vertex. So, we need to fix this, right? To delete a vertex from the graph, it is necessary to iterate through the list of each vertex and validate whether an edge exists or not. If it exists, then we have to remove the vertex. Let’s take a look:

removeVertex(vertex) { 
    if(vertex in this.adjacencyList){
        delete this.adjacencyList[vertex];
        var vertexList = Object.keys(this.adjacencyList);
        vertexList.forEach(element => {
            if(this.adjacencyList[element].includes(vertex) == true){
                var index = this.adjacencyList[element].indexOf(vertex);
                this.adjacencyList[element].splice(index,1);
            }
        });
    }
}

As you may be thinking, this function is O(n) because we need to iterate over the vertices and then remove the element.

And the edges? I mean, what if Gandalf had a big argument with Saruman and then decides to remove him from his social network? What do we have to do? 🧐 Well, to remove an edge, we need to check if the vertices are connected and then remove them from the array.

removeEdge(vertex1, vertex2) { 
    if(this.adjacencyList[vertex1].includes(vertex2)){
        var adjacents = this.adjacencyList[vertex1];
        var index = adjacents.indexOf(vertex2);
        this.adjacencyList[vertex1] = adjacents.splice(index,1);
    }
}

Great! Can you see the progress? 🚀

There are functions like print_all_path_destination, print_adjacency_matrix, countPaths, isAdjacent and others that I would like to discuss, but I’ll skip the explanations for not taking too much of your time.

⚡️ But if you would like to learn or see others functions that I implemented you can access all the code just clicking here.

Now we are going to use all the acknowledgement that we learned to implement search function.

▪️ Graph Search

Let's dive into the most important topic related to this structure! We want to traverse all the vertices and edges of that graph. What does that mean? Well, we can put an example: Gandalf had a map and try to travel across middle-earth. 😁 But relax, we'll see all the steps of these functions using an example along the way. Let's create a graph to be used.

var graph_example = new Graph();
graph_example.addEdgeDirected(0, 1)
graph_example.addEdgeDirected(0, 2)
graph_example.addEdgeDirected(1, 3)
graph_example.addEdgeDirected(1, 4)
graph_example.addEdgeDirected(2, 5)
graph_example.addEdgeDirected(2, 6)

After creating the vertices and edges, our graph will look something like this:

Figure 7: Graph example to be used on BFS and DFS functions.

Breadth-first search (BFS)

This approach is the most common and used. It starts by considering all vertices as unvisited and all edges undiscovered. With that in mind, we can choose an arbitrary vertex and then discover all vertices connected by an edge and visited.

Every time that an adjacent vertex is visited, we must mark it and insert it in a queue. Since none of the edges that incident on the vertex are undiscovered, we can proceed and explore the next vertex.

Using the example above and considering vertex 0 as the current vertex, the result is:

Visited Vertex: 0
Visited Vertex: 1
Visited Vertex: 2
Visited Vertex: 3
Visited Vertex: 4
Visited Vertex: 5
Visited Vertex: 6

We must repeat the process until no undiscovered and unvisited are left in the structure. When the queue is empty, it means that the algorithm covers all vertices and edges. With all that in mind, let's put everything in a code.

breadthFirstSearch(current_vertice) {
    var vertices = Object.keys(this.adjacencyList);
    if(vertices.length === 0){
        return;
    }else {
        var discovered = {};
        vertices.forEach(function(item) {
            discovered[item] = false;
        })
        this._breadthFirstSearch(current_vertice, discovered);
    }
}

_breadthFirstSearch(vertex, discovered){
    var queue = [];
    discovered[vertex] = true;
    queue.push(vertex);

    while(queue.length > 0){
        var u = queue.shift();
        console.log('Visited Vertex: ' + u);

        var listAdjacents = this.adjacencyList[u].sort((a, b) => a - b)
        listAdjacents = listAdjacents.sort()

        for (let index = 0; index < listAdjacents.length; index++) {
            const element = listAdjacents[index];
            if(!discovered[element]){
                discovered[element] = true;
                queue.push(element);
            }
        }
    }
}

Depth First Search (DFS)

Initially, this function has conditions similar to the BFS function, all vertices are unvisited and edges are not discovered. Then, we can choose an arbitrary vertex that will be our root element, which will be visited and called the current vertex.

Now is when the difference between DFS and BFS functions begins! The current vertex has to explore as far as possible along each vertex visited, moving to the next undiscovered adjacent edge and printing the path.

We must continue this loop until there are no unvisited and undiscovered elements. Instead of queuing, the DFS function uses a stack to find the shortest path. After that, with no undiscovered edges left, we have to go back to the initial visited vertex and start again checking other unvisited vertices until cover all vertices and edges of the graph.

Using vertex 0 as the current vertex, we will obtain the following result:

Visited Vertex  0
Visited Vertex  1
Visited Vertex  3
Visited Vertex  4
Visited Vertex  2
Visited Vertex  5
Visited Vertex  6

depthFirstSearch(current_vertice) {
    var vertices = Object.keys(this.adjacencyList);
    if(vertices.length === 0){
        return;
    }
    var discovered = {};
    vertices.forEach(function(item) {
        discovered[item] = false;
    })
    this._depthFirstSearch(current_vertice, discovered);
}

_depthFirstSearch(current_vertice, discovered){
    discovered[current_vertice] = true;
    console.log('Visited Vertex ', current_vertice);

    var listAdjacents = this.dictAdj[current_vertice].sort((a, b) => a - b)
    for (let index = 0; index < listAdjacents.length; index++) {
        const element = listAdjacents[index];
        if(!discovered[element]){
            this._depthFirstSearch(element, discovered);
        }
    }
}

That's all folks!

I hope you have fun learning. 😁

Code: https://github.com/FernandoBLima/data-structures

So we finished our discussion about Graph structure. 🙌

If you found something I miss out or find this article helpful, feel free to let me know. 😁

Heap - Data Structure & Algorithm Part VII

Fernando Baptistella — Mon, 14 Dec 2020 00:49:07 +0000

It's been a while since the last post in this series. I was very busy with other things, but I'm back! Yes! 😁 In this post, we will continue to learn a new data structure and how to implement it. 👨‍💻👩‍💻

💭 "Falling in love with code means falling in love with problem solving and being a part of a forever ongoing conversation. To be a computer programmer does not mean to live in isolation and solitude, but rather the exact opposite." - Kathryn Barrett

Outline

What is a Heap?
Basic concepts
The main operations and properties.

Let's start to work! 😃

Pre-requisite : Tree

If you haven't read tree and binary search tree, I recommend you check it out first!

- What is a Heap? 🧐

If you've seen how the heap structure organizes values, you might think that there are some similarities to the tree structure. Yes, indeed. Basically, we can define a heap structure as a special full binary tree structure where each element has exactly two children, the only exception can be the deepest level.

One important thing to keep in mind about this structure is that there are two types of the heap and the differences between them are related to the property of storing a value, which can be:

Max-heap: The root element has the maximum value and the value for every element is equal or greater than the value in the node’s children.

Figure 1: Max-heap representation.

Min-heap: Here we have the opposite side because the root element has the minimum value and the value for every element is equal to or less than the value in the node’s children.

Figure 2: Min-heap representation.

As we can see, every element can be actually called as the root of its own sub-heap. For instance, using min-heap example given above we can say that the value 8 is the root of 7 and 3 sub-heap.

Figure 3: Example of sub-heap.

After describing the basics and understanding what the heap is, how do we create this data structure? First things first, let's start building the constructor.

So, you may be thinking and assuming based on the last post about tree structure that we could implement a simple class that contains left and right elements, right? 🧐

You are absolutely right! 😃 We can certainly implement it that way, however, there is another and better approach that we can use to create an efficient way of implementing it.

Instead of creating these elements, we can use an array to store all the heap values, simple right? In this way, we just need to store all the values top to bottom, left to right, and that's it! Using this approach, we can know that the fifth value in the array will be the fifth value in the heap, for instance.

Let's use the min-heap example used above and take a look at the following image:

Figure 3: Array-heap representation.

The use of array indexes can describe the parent-child structure. But, wait! ✋ What that's mean? 🤔 Looking at the element, we can get the left child element by Arr[(2*i)+1] that returns the value. And the parent and right element? Let's take a look below:

Index of element = i
Returns the left child element = Arr[(2*i)+1]
Returns the right child element = Arr[(2*i)+2]
Returns the parent element = Arr[i/2]

For example, let's use the value X in the array, which is the third element of the structure. To get the parent value, we just have to get the index value and divided it by 2. Simple right? That said, understanding how we can access these values will be extremely important in the next function in the heap structure.

Now that we're on the same page, let's move on and put everything that we've learned into our code. First, we need to create the skeleton of our heap class.

class Heap {

    constructor() {
        this.list = [];
    }
    ...
}

Basic operations

Okay, now that we already know how to build the heap structure let's diving into the main operations.

Talk is cheap. Show me the code! 😁

◼️ Insert

To insert a new element it is necessary to find the first available space in the structure looking for an empty spot from top to bottom and left to right order.

After that, it may be necessary to rearrange the structure, this process will compare the value inserted with the parent value based on the type of heap. The elements should be swap if not follow the heap property and continue to bubble until finding the right spot in the structure.

In this function, we might have to make a comparison at each level of the structure and then swap the elements until the root element. Every time a new value goes up it takes O(1) time. So, the worst-case time complexity is O(nlg n) because we insert the value at the end of the heap and traverse up.

insert(value){
      this.list.push(value);
      var childrenIndex = this.list.indexOf(value);

      while(this.hasParentByIndex(childrenIndex)){
          if(this.shouldSwap(childrenIndex, this.getParentByIndex(childrenIndex))){
            this.swapElements(childrenIndex, this.getParentByIndex(childrenIndex));
            childrenIndex = this.getParentByIndex(childrenIndex);
          } else{
             break;
          }
      }
}

⚡️ If you would like to learn others functions that I implemented you can access all the code just clicking here.

◼️ Deletion

In the Heap, we remove the root element of the structure and then replace it with the last value added. As you may be thinking, the new root element might probably not be in the right position. To solve this problem it is necessary to call the heapify function, which is the most critical operation in this structure where it reorganizes the values until the heap property is satisfied.

removeFromTop(){
     if(this.isEmpty())
         throw new Error('The Heap is Empty');
     if(this.getSize() == 1){
         this.list.pop();
     } else {
         this.swapToRemove();
         this.heapify();
     }
}

swapToRemove(){
    this.swapElements(this.list.length - 1, 0);
    this.list[this.list.length - 1] = null;
    this.list = this.list.filter(function (element) {
        return element != null;
    });
}

swapElements(childrenIndex, parentIndex) {
    const tmp = this.list[parentIndex];
    this.list[parentIndex] = this.list[childrenIndex];
    this.list[childrenIndex] = tmp;
}

Using a top-down approach, this function will bubble it down comparing the new root element and the left and right child, then swap elements according to the type of heap and repeat the process until the new root element finds a valid spot and the heap property has been satisfied.

Let's see how we can put these words in a code.


heapify(index=0){
     let left = this.getLeftChildrenIndex(index),
         right = this.getRightChildrenIndex(index),
         largest = index;

     if(!this.list[left]) return;

     if(this.shouldSwap(left, largest) ){
         largest = left;
     }
     if(this.shouldSwap(right, largest) ){
         largest = right;
     }
     if(largest !== index){
        [this.list[largest],this.list[index]] = [this.list[index],this.list[largest]];
          this.heapify(largest);
     }
}

We can say that the main point of heapify function is to make sure that the structure follows the heap propriety by comparing the elements and the child elements.

The time complexity for swap element in each level is O(1) and the worst-case time is O(lg n) and it depends on how far an element can move down, which is related to the height of the heap. In the worst case, the element might go down all the way to the leaf level.

⚡️ If you would like to learn others functions that I implemented you can access all the code just clicking here.

◼️ Merge heaps

To merge two existing heap into a single one can be done by all values moved from the smallest heap to the largest using the insert function. However isn't the best way because involves moving N items and rearranging at cost 0(log n), giving an overall time complexity of O(nlog n).

The best approach is just to concatenate the values of two heaps and then use heapify algorithm, as we can see below:

mergeHeaps(heap){
     var array = []
     for (var i = 0; i < this.size; i++) { 
         array[i] = this.list[i]; 
     } 
     for (var i = 0; i < heap.size; i++) { 
         array[this.size + i] = heap.list[i]; 
     } 
     var total = this.size + heap.size; 
     this.list = array

     for (var i = total / 2 - 1; i >= 0; i--) { 
         this.heapify(i)
     } 
}

We are done 🙌

That's all, folks! I see you arround and wash your hands and use masks. 😁😷

Code: https://github.com/FernandoBLima/data-structures

We finished our discussion about Heap structure. 🙌

If you found something I miss out or find this article helpful, feel free to let me know. 😁

Trie - Data Structure & Algorithm Part VI

Fernando Baptistella — Wed, 27 May 2020 23:46:22 +0000

In this post our main goal is to understand the Trie Data Structure, learning the concepts, how it works, and how to implement it (a.k.a code!).

It is important to understand the tree structure before diving into the trie. So, if you need to, you can read the last post about the tree and binary search tree.

Moving on, let’s discuss the data structure journey! 😁

💭 "Those hours of practice, and failure, are a necessary part of the learning process."- Gina Sipley

Outline

The article is divided into the following parts:

Understanding the Trie structure;
The main operations

◼️ Trie

Pre-requisite : Tree

We can say that the trie structure stores a set of strings that can be visualized like a tree where each node is a character. This structure is stored in a top to the bottom manner and the order that appears is based on the prefix of a string that all the descendants' nodes have in common.

But what do I mean about prefix? 🧐

Let's consider using the word 'Batman' for the set S of n strings to clarify our mind.

S1 = { B,a,t,m,a,n }

First all, the root of the structure is started with a node with value ε that represents the empty string. The next inserted node has the first value in the set S1 that is 'B'. Then, the next node to be used is the value 'a' and so on.

As we can see, each node can have several child values (or not). At most, the size of the alphabet that the children are connected to, in our case can have up to 26 children.

So, let’s see an example using the word that we are discussing.

Figure 1: Inserted a new word

Great! Let's use this structure and add a new set that has the word 'Bat', using as the set S2 of n strings.

S2 = { B,a,t}

Here, the first letter 'B' of the set S2 has already been inserted in the first node. Therefore, we do not have to create another node, and the same happens to the letters 'a' and 't'. As a consequence, just need to mark the letter 't' as the end of a word.

See the next figure below that shows a trie with the words “Batman” and “Bat”.

Figure 2: Inserting a word that already have the as prefix in the structure

What's happens if we add the word 'Batgirl'?

S3 = { B,a,t,g,i,r,l}

As we discussed earlier, the structure already have the letters 'B', 'a', and 't'. So, just needs to create the node for other words. See below:

Figure 3: Inserting a word that already have a prefix

What if we add a word that starts with a different letter instead of 'B'? Don't worry, just need to insert a new node with a value. In this example, we will add the word 'Joker', in this way, the letter 'J' will be added after the node that represents the empty string. Keep in mind, don't forget to mark the last letter at the end of the word.

This happens with other words that can be added to our structure, such as Penguin, Ivy, Two-Face, and so on.

Figure 4: Inserting a word that start with a different first letter

After all, why should we use this structure? Why not use the tree structure? Well, the trie structure is faster compared to the tree and hash table because we do not need to calculate any hash functions or worry about dealing with collisions.

Awesome! Now that we understand the behaviors and how we can add values, let's build our structure. At first, we need to create our main class.

Talk is cheap. Let’s see the code. 😁

class TrieNode {
    constructor(isEnd, value ) {
        this.children = {};
        this.isEndOfWord = isEnd;
        this.character = value;
    }

}

class Trie {
    constructor() {
        this.root = new TrieNode(true, '*');
        this.length = 0;
    }

    ...

}

Each TrieNode represents a letter in the structure and has the following parameters:

children: As we discussed above, there can be more than one child.
isEndOfWord: Represents if the letter is the end of the word.
character: Is the node value.

Done! 😁

But not entirely! We need to create and add methods to our class. The implementation of insert, search and delete functions are a simpler way to implement these functions using Javascript, and all of these operations have the complexity of time O(L) where L is length of key.

Let's check out:

Insert

As mentioned earlier, this structure starts with a node that represents the empty string. We have to insert the first character of the set of strings, but if the value to be inserted has already been added, we just have to get down to the next level and continue to add the following values from the set.

However, if at some point there is no node, we will have to create and continue the process until the whole set is inserted, and of course, mark the last value of the set as the end of the word node. The space complexity of this structure in the worst case is when the word to be inserted is higher than the maximum number of nodes in the structure.

    insert(key){
        var currentValue = this.root;

        for (let index = 0; index < key.length; index++) {
            const element = key[index];
            if (currentValue.children[element]) {
                currentValue = currentValue.children[element];
            } else {
                this.length++;
                const newNode = new TrieNode(false, element);
                currentValue.children[element] = newNode;
                currentValue = newNode;
            }
        }
        currentValue.isEndOfWord = true;
    }

Searching a string in this structure is a simple approach, we just have to iterate all characters of the set starting at the root and checking if the value matches and moving down to the next node. If the last letter used in the process is marked as the last node, then the set belongs to the searched word.

However, we can say that the set S is not present in the trie when:

There is no transition for children nodes and there is still a letter in the set.
If all the letters have been consumed and the last node in the process does not correspond to the string.
Or all characters exist in the structure, but the last letter is not marked as the end of the word node.

    searchWord(key){
        var currentValue = this.root;
        for (let index = 0; index < key.length; index++) {
            const element = key[index];
            if (currentValue.children[element]) {
                currentValue = currentValue.children[element];
            } else{
                return null;
            }
        }
        return currentValue;
    }

Suggestion Word

The main goal of this function is to show all words that have a prefix in common. At the beginning, is searched if the set of string already has been inserted in the structure and returns a list that contains all words that contain the word as a prefix.


    suggestionWord(key) {
        var word = this.searchWord(key);
        if(word){
            var suggestions = [];
            if(word.isEndOfWord){
                suggestions.push(key);
            }
            return this._suggestionWord(word, key, suggestions);
        }
        return [];
    }


    _suggestionWord(node, lastWord, suggestions){

        var letters = Object.keys(node.children); 
        for (let index = 0; index < letters.length; index++) {
            const element = letters[index];
            if(node.children[element].isEndOfWord){
                suggestions.push(lastWord + node.children[element].character);
                this._suggestionWord(node.children[element], lastWord + node.children[element].character, suggestions);
            }else{
                var rest = lastWord + node.children[element].character;
                this._suggestionWord(node.children[element], rest, suggestions);
            }
        }

        return suggestions;
    }

Remove

In this function, the word is removed from the structure if contains the prefix and does not have any other words that use as a prefix.

  remove(key) {
        if(this.search(key)){
            return this._removeNode(this.root ,key, key, 0);
        }else{
            return false;
        }
    }

    _removeNode(node, keySlice ,key, index) {
        var letter = key[index];
        var current = node.children[letter];
        if(current){
            keySlice = key.slice(index + 1, key.length);
            var shouldRemove = this._removeNode(current, keySlice, key, index + 1 );
            if(shouldRemove && !this.hasChild(node.children[letter].children)){
                this.length--;
                delete node.children[letter];
                key = keySlice;
                return true;
            }else{
                return false;
            }
        }
        return true;
    }

That's all folks! I hope you have fun learning. 😁

Code: https://github.com/FernandoBLima/data-structures

So we finished our discussion about Trie structure. 🙌

I hope you have a clear idea how to work. If you found this article helpful or if you find something I miss out or that you like it, feel free to let me know. 😁

Tree and Binary Search Tree - Data Structure & Algorithm Part V

Fernando Baptistella — Tue, 21 Apr 2020 17:45:52 +0000

Finally, this series will talk about the tree structure and I am very excited because it is one of the most important structures and there is a lot to cover. 😁

Of course, it will be impossible to cover everything in just one article. In this way, to keep things simple, we will have other articles to discuss this structure. However, this does not mean that what we are going to learn is not important! We will focus on the tree and binary search tree that are powerful concepts and that will help us to develop our knowledge to future articles! 👩‍💻👨‍💻

But wait for a second! Before winter comes, if you are unfamiliar or need to remember some concepts about data structures, I highly recommend reading the most recents posts in this series.

Now that you are ready for the winter, go ahead and may the Seven gods protect you in the game of thrones.

Because winter is coming!

💭 "People have an enormous tendency to resist change. They love to say, 'We've always done it this way'. I try to fight that." - Grace Hopper

Outline

Basic concepts
Terminology
Types of Trees: Tree, Binary Tree and Binary Search Tree
The main operations and properties.

◼️ Tree 🌳

We can describe the simplest definition of tree structure by saying that it stores and manipulates elements hierarchically, and this is one of the biggest differences with other structures.

So, let's look at how this structure works using the following example:

Figure 1: representation.

One of the first steps to understand the structure is to understand the main concepts. As we can see in the image above, each character in Stark House represents a node element in the tree structure. The node on the top is the Rickard Stark element and is called the root of the tree because it starts the structure and does not have a parent node.

All elements that are under an element are represented as children, for instance, Eddard, Benjen, and Lyanna elements are related as children of the Rickard node and the link between a node to another, like Rickard and Eddard, is called an edge.

Another thing to discuss in this picture is related to Robb, Sansa, Arya, Bran, Rickon, and Jon Snow (You know nothing!) elements, they represent leaves because they do not have children.

Okay, the next step is to define the main class which is NodeTree, as you can see in the following code:

class NodeTree {
    constructor(key) {
        this.key = key;
        this.descendents = [];
    }
}

Now we are going to create a simple example where we can add new values to the tree and then remove it. In this code, we create the Tree constructor that has the link to the root element and the number of nodes in the structure.

Besides that, there is a function to insert a new value that we can specify where the value will be added. For instance, if the structure already has the root element, a new value will be added as a descendent node. However, we can specify the parent node of the new element. Another function is to remove a value from the structure that does a search on all child elements.

Take a look at the code below:

class Tree {
    constructor() {
        this.root = null;
        this.length = 0;
    }

    add(value, root = null) {
        if(!this.root){
            this.root = new NodeTree(value);
        } else {
            if(!root){
                this.root.descendents.push(new NodeTree(value));
            } else {
                var currentRoot = this.getValue(root);
                currentRoot.descendents.push(new NodeTree(value));
            }
        }
    }

    remove(value) {
        var queue = [this.root];
        while(queue.length) {
            var node = queue.shift();
            for(var i = 0; i < node.descendents.length; i++) {
                if(node.descendents[i].key === value) {
                    node.descendents.splice(i, 1);
                } else {
                    queue.push(node.descendents[i]);
                }
            }
        }
    }

    ...

}

◼️ Binnary Tree

As the name suggests, a binary tree it is a tree whose elements have at most 2 children, called left and right. Simple right? We should keep in mind that every node is a representation of a subtree itself. That said, a node can have two subtrees.

◼️ Binnary Search Tree (BST)

Binary Search Tree is a rooted binary tree and each node store a key and can have two children like the binary tree. But what is the difference between them? An important thing to remember is that the root element must satisfy the property to be greater than all keys stored in the left sub-tree, and not greater than all keys in the right sub-tree which provides the efficient way of data sorting, searching and retriving.

In general, the worst case of time complexity is O (h), where h is the height of the BST, because it depends on how many elements and the order we must go through.

To implement a binary search tree we have to update the NodeTree class, in order to support the binary search tree property.

class NodeTree {
    constructor(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
}

Let's take a look at the following image:

Figure 2: Binary Tree representation.

Operations

Now we will learn some operation to build our structure.

- Insert

As we discussed above, the root element must be greater than all left subtree elements and smaller than right subtree and this must occurs to all elements in the structure. In this way, when a new element is inserted must be verified the value. When a value is less than the node's key it must be added to the left sub-tree, otherwise it must be added to the right subtree. An important thing to get note is that duplicate nodes are not allowed in the tree.

We implement a binary search tree using the class NodeTree. Here is how a binary search tree insertion might be:

    insert(value){
        if(!this.root){
            this.root = new NodeTree(value);
            this.length++;
        }else{
            this._insertNode(this.root, value);
            this.length++;
        }
    }

    _insertNode(currentNode, value){
        if(currentNode.key){
            if(value < currentNode.key){
                if(!currentNode.left){
                    currentNode.left = new NodeTree(value);
                }else{
                    this._insertNode(currentNode.left, value);
                }
            } else {
                if(!currentNode.right){
                    currentNode.right = new NodeTree(value);
                }else{
                    this._insertNode(currentNode.right, value);
                }
            }
            return;
        }
    }

- Search

When we want to search for an element, we have to follow the same logic as the previous function. Remember that an element is searched from the root node if the value is less than the root node, then we must traverse to the left subtree, otherwise, the search will be directed to the right subtree. Once you understand how value is inserted, it becomes easier to create other functions, right?

One of the main differences between this structure to the others is the fact that we can search for an element more quickly than the Linked List, but it is slower compared to arrays. This behavior can occur in the same way to insert and delete functions.

    search(value){
        if(!this.root){
            return null;
        }else{
            return this._search(this.root, value);
        }
    }

    _search(node, value){
        if(node){
            if(node.key != value){
                if(value < node.key){
                    return this._search(node.left, value);
                }else{
                    return this._search(node.right, value);
                }
            }else{
                return node.key;
            }
        }else{
            return null;
        }
    }

- Delete

To remove an element in the binary search tree, three are some of the possibilities that must be followed, which are:

If the value to be deleted is a leaf, then we just need to remove it from the tree.
When a node has only one child, in this case, we need to remove the value and copy the child to the node.
If a node element to be deleted has two children, it is necessary to find the inorder successor of the node.

Below is an example:

    delete(value){
        if(!this.findNode(value)){
            return false;
        }
        this._delete(this.root, value);
        return true;
    }

    _delete(node, value){
        if(node == null) return node;

        var parent = this.findParent(value);
        if(!parent && node.left == null && node.right == null){
            return this.root.key = null;
        }

        if(value < node.key){
            node.left = this._delete(node.left, value);
        }else if(value > node.key){
            node.right = this._delete(node.right, value);
        }else{
            if(node.left == null){
                return node.right;
            }else if(node.right == null){
                return node.left;
            }
            node.key = this._minValue(node.right); 
            node.right = this._delete(node.right, node.key);
        }
        return node;
    }

⚡️ The binary Search Tree is a extend topic to discuss and learn, if you would like to learn others functions that I implemented such as listLeafNodes, findParent, findMaximum, findMinimum and others, you can access all the code just clicking here.

Types of binary trees

Okay, now that we already understand the main operations in a binary search tree, we can move on and discuss some other properties. We can classify the binary search tree into the following types of Binary Trees:

Full Binary Tree

It is considered a full binary tree if all nodes, except the leaves, have two children. The following image shows an example of a full binary tree.

Figure 3: A full binary tree example

   isFull(){
        if(this.root == null || this.root.left == null && this.root.right == null ) 
            return true; 
        return this._isFull(this.root);
    }

    _isFull(root){
        if(root == null || root.left == null && root.right == null ) 
            return true; 

        if ((root.left == null && root.right != null) ||
            (root.left != null && root.right == null))
                return false; 

        if((root.left != null) && (root.right != null)) 
            return (this._isFull(root.left) && this._isFull(root.right));    
    }

Complete Binary Tree

Here, we can say that a Binary Tree is complete when all levels are full, the only exception being the last level.

Figure 4: A complete binary tree example

    isComplete(){
        if (this.root == null)         
            return true; 
        let numberNodes = this.countNode();
        return this._isComplete(this.root, 0, numberNodes);
    }

    _isComplete(root, index, numberNodes) {
        if (root == null)         
            return true; 

        if (index >= numberNodes) 
            return false; 

        return (this._isComplete(root.left, 2 * index + 1, numberNodes) 
            && this._isComplete(root.right, 2 * index + 2, numberNodes));
    }

Perfect Binary Tree

When a binary tree is complete and full at the same time, it is considered a Perfect Binary Tree, which means that all levels have elements and all leaf nodes are at the same level.

Figure 5: A perfect binary tree example

   isPerfect() {  
        if (this.root == null)  
            return true;  
        let leftMostLeaf = this.leftMostLeaf(this.root);  
        return this._isPerfect(this.root, leftMostLeaf, 0);  
    }  

    leftMostLeaf(node) {  
        let depth = 0;  
        while (node != null)  
        {  
            depth++;  
            node = node.left;  
        }  
        return depth;  
    }  

    _isPerfect(root, d, level) {  
        if (root == null)  
            return true;  

        if (root.left == null && root.right == null)  
            return (d == level+1);  

        if (root.left == null || root.right == null)  
            return false;  

        return this._isPerfect(root.left, d, level+1) && this._isPerfect(root.right, d, level+1);  
    }

Binary Tree Traversal

We can visit all nodes in a tree differently, generally, it starts at the root node to search or locate a particular tree, or to print all the values it contains. With this concept in mind, let's take a look at in the most commons ways to traverse a binary tree.

Figure 5: A binary search tree example

Pre-order

In this function, the order that we must follow is to visit the root node first, and then go through all elements on the left subtree and the right subtree of the root.

Root -> Left Tree -> Right Tree

As I said before, every node is a representation of a subtree itself. With that in mind, when a leaf node is located, which has no left and right subtree, we say that it has been completely traversed. As a consequence, the right node of the subtree will be visited. This process occurs until all elements are visited.

Pre-order traversal : [ 100, 50, 25, 75, 150, 125, 175 ].

    preOrder(){ 
        if (this.root == null) 
            return null; 
        var listValues = [];
        return this._preOrder(this.root, listValues); 
    } 

    _preOrder(node, listValues){
        if(node.key != null) 
            listValues.push(node.key);
        if(node.left != null) 
            this._preOrder(node.left, listValues);
        if(node.right != null) 
            this._preOrder(node.right, listValues);
        return listValues;
    }

In-order

In this traversal method, its traverse to the left subtree first by recursively. At first, it visited all elements of the left subtree of the root, then the node root and all elements of the right subtree.

Left Tree -> Root -> Right Tree

In-order traversal : [ 25, 50, 75, 100, 125, 150, 175 ].

    inOrder(){ 
        if (this.root == null) 
            return null; 
        var listValues = [];
        return this._inOrder(this.root, listValues); 
    } 

    _inOrder(node, listValues){
        if(node.left != null) 
            this._inOrder(node.left, listValues);
        if(node.key != null) 
            listValues.push(node.key);
        if(node.right != null) 
            this._inOrder(node.right, listValues);
        return listValues;
    }

Post-order

In this method, we traverse the left subtree, the right subtree, and the root node.

Left Tree -> Right Tree -> Root

Post-order traversal: [ 25, 75, 50, 125, 175, 150, 100 ].

    posOrder(){ 
        if (this.root == null) 
            return null; 
        var listValues = [];
        return this._posOrder(this.root, listValues); 
    } 

    _posOrder(node, listValues){
        if(node.left != null) this._posOrder(node.left, listValues);
        if(node.right != null) this._posOrder(node.right, listValues);
        if(node.key != null) listValues.push(node.key);
        return listValues;
    }

Level order

Another important way to traverse in a tree is the level-order that visits every node on a level before going to a lower level.

Level order: [ 100, 50, 150, 25, 75, 125, 175 ].

   levelOrderQueue() {
        if (this.root == null)
            return null;

        var listOrderQueue = [];
        listOrderQueue.push(this.root);
        var listValues = []

        while (listOrderQueue.length > 0) {
            var n = listOrderQueue.shift();

            if (n.left != null)
                listOrderQueue.push(n.left);

            if (n.right != null)
                listOrderQueue.push(n.right);

            listValues.push(n.key)
        }
        return listValues;
    }

That's all, folks! I hope you are taking care of Yourself 😁

Code: https://github.com/FernandoBLima/data-structures

So we finished our discussion about Tree and Binary Search Tree structure. 🙌

I hope you have a clear idea how to work. If you found this article helpful or if you find something I miss out or that you like it, feel free to let me know. 😁

Disjoint Set - Data Structure Part IV

Fernando Baptistella — Wed, 04 Mar 2020 23:04:51 +0000

This is the fourth part of the Data Structure series. If you haven't read this series yet, I recommend you check it out first!

In this series, we’ve already learned that there are different ways to organize data using variables, arrays, hashes and objects in data structures. We discussed linked list, hash and set structure, however, this is just the tip of the iceberg! There is much more to come and learn. Relax, take it easy, because we will learn step by step. So, you don't have to worry, even if it sounds hard to hear.

💭 "Those hours of practice, and failure, are a necessary part of the learning process."- Gina Sipley

Outline

The article is divided into the following parts:

Understanding what Disjoint Set is.
How the union and merge function works?
How to optimize the union function?
Code implementation and complexity analysis.

◼️ Disjoint Set

We will continue what we already had learned in the last post about sets.
A disjoint-set data structure is also called a union-find or merge–find set. It's like every data structure has more than one name, right? 😂 So, I will refer only to the Disjoint Set, because it looks more sophisticated and scientific to me. 👨‍💻👩‍💻 This structure has several applications but the most known is in the Kruskal's algorithm.

But what is a Disjoint Set? 🧐

A good way to understand this structure is imagining that we have more than one element that belong to a set and is partitioned into further subsets. That is to say, in this structure, the elements can keep the track of elements of the set, as you can see on the following image, where each element can have a child and parent element.

Figure 1: Disjoint Set representation.

We can use the same approach that we used in the last post where we learned that the linked list is not a good option because it does not perform well. That's a result because the efficiency of an algorithm most of the time is related to how the data is used in an efficient way in a data structure. So, how we can build the Disjoint Set?

Before diving into this structure, we need first to discuss our main class. That said, when a Disjoint Set is created it is necessary to initialize our structure using the init function that creates all the elements, this function has O(n) of time complexity. But how exactly does this function work?

In this code, each element is a reference to the DisjointSetNode class and it is put as root at the beginning, which means that the parent property is mapped to itself. Furthermore, when an element has no child elements, it is called the root of a structure and is set to -1 for the parent property, as a consequence, all elements belong to a different set, pretty simple, right?

Our main class would look something like this:

class DisjointSetNode {
    constructor(value) {
        this.value = value,
        this.children = {};
        this.rank = 1;
        this.parent = -1;
    }
}


class DisjointSet {
    constructor() {
        this.list = {};
        this.size = 0;
    }

    init(size){
        this.size = size;
        for (var i = 0; i < this.size; i++) {
            var disjointSetNode = new DisjointSetNode(i);
            this.list[i] = disjointSetNode;
        }
    }

    ...

}

Okay, let’s move on and take more steps forward to continue the discussion now that we understand how to initialize the structure. We can summarize and define the Disjoint Set with just two primary operations: find and union.

Find

As the name suggests, this operation follows the parent element until a root element is reached, in other words, finding the value whose parent is itself.

    findRoot(x) {
        if (this.list[x] && this.list[x].parent !== -1) {
            return this.findRoot(this.list[x].parent);
        }else{
            return this.list[x];
        }
    }

Union

The basic idea for this function is to merge two distinct roots and making one of the roots as a parent of the root of the other.

I provided a simple code implementation for this function, note that the number of roots never increases and this occurs when the elements are merged, instead, the number of roots decreases. As we can see in our example below:

    union(x, y){
        var xRoot = this.findRoot(x);
        var yRoot = this.findRoot(y);

        yRoot.parent = -1;
        yRoot.children[xRoot.value] = xRoot;
        xRoot.parent = yRoot.value;
    }

Ok, let's see the example below that merges some values to help us make the understanding of this structure clearer, let's use the following subset S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } and merge some elements.

disjoinSet.init(10);

disjoinSet.union(2,1)
disjoinSet.union(2,3)
disjoinSet.union(3,4)
disjoinSet.union(5,4)
disjoinSet.union(4,6)

The result will look something like this:

Figure 2: Example of union operation.

After union operations, you can see that there are now 5 subsets. First there is the element {0}, then {6 4 3 1 2 5}, {7}, {8} and {9}. Another important function that we can use is isConnected, used to check whether the elements are in the same set or not. For instance, we can find out if the values 2 and 6 below in the same group if they have the same root, therefore, this will give us a true result. See the code below:

isConnected(value1, value2){
     if(this.findRoot(value1).value == this.findRoot(value2).value) 
         return true;
     return false;
}

⚡️ If you would like to know others functions that I implemented such as getSetSize, extractSets, getChildrenByItem, and others, you can access all the code just clicking here.

Can you see the problem that can occur if we continue to link one element as a child of another using the union function? To check if values 2 and 6 belong to the same group, you will need four hops in the example above. It is a consequence of the union function that makes the structure grow by 𝑂(𝑁). If we deal with a large data set, this approach may not be efficient, with that in mind, one way to optimize this problem and reduce the execution time is by using one of the following ways:

Union By Size

In this function, we connect the sets by the size where the root of the smaller structure is linked to the root of the larger structure. Initially, each element is a subset, in other words, it has size 1.

The code example:

    unionBySize(x, y){
        var xRoot = this.list[x];
        var yRoot = this.list[y];

        if(this.getSetSize(xRoot.value) > this.getSetSize(yRoot.value)){
            yRoot.parent = xRoot.value;
            xRoot.children[yRoot.value] = yRoot;
        } else {
            xRoot.parent = yRoot.value;
            yRoot.children[xRoot.value] = xRoot;
        }
    }

The getSetSize function is used to return the size of the structure, making the element that belongs to the smallest structure size points to the set that has the largest size. The following code is an example of this scenario.

disjoinSet.unionBySize(2,1);
disjoinSet.unionBySize(2,3);

disjoinSet.unionBySize(0,4);
disjoinSet.unionBySize(5,4);
disjoinSet.unionBySize(4,6);

disjoinSet.unionBySize(3,6);

Figure 3: Example of Union By Size operation.

Union By Rank

We can use a different way to optimize the structure using the rank, which means that is used the height of the set instead of the size to link the root of a smaller rank to the root with a larger rank. Another key thing to remember is that each element initially has 0 of rank. However, when the roots have the same rank, only the rank of the new root increases by 1 otherwise, no change occurs. Let's create an example:

disjoinSet.unionBySize(4,5);
disjoinSet.unionBySize(6,7);
disjoinSet.unionBySize(4,6);
disjoinSet.unionBySize(3,4);

Take a look at the code below:

   unionByRank(x, y){
        var xRoot = this.findRoot(x);
        var yRoot = this.findRoot(y);

        if(xRoot.value == yRoot.value)
            return;

        if(xRoot.rank < yRoot.rank){
            xRoot.parent = yRoot.value;
            yRoot.children[xRoot.value] = xRoot;
        } else if (xRoot.rank > yRoot.rank) {
            yRoot.parent = xRoot.value;
            xRoot.children[yRoot.value] = yRoot;
        } else {
            xRoot.parent = yRoot.value;
            yRoot.children[xRoot.value] = xRoot;
            yRoot.rank = xRoot.rank + 1;
        }
    }

Using the union by rank function the worst-case running time per operation is 𝑂(log𝑛).

Path Compression

We can use Path Compression to optimize the Union by size and that’s what makes this structure remarkable. The idea behind this function is to flatten the structure when the find() function is used. After finding the root of all the elements along the way, the elements point each one directly to the root. As a result, efficiency is increased compared to the basic union operation.

But before showing how this operation works, let's take a few steps back and compare it to the worst case scenario. Let's say there are 4 elements {0,1,2,3} and then we merge to understand how the find and join operation are important in this function. As we can see:

disjoinSet.union(0,1);
disjoinSet.union(1,2);
disjoinSet.union(3,0);

As we discussed earlier, in this situation the height of our structure can grow quickly, after each step you can observe that the height is growing which brings us a poor performance. If we perform theses operations above, then the result it will be:

Figure 4: Example of the worst case scenario using the union operation.

We can avoid this, merging the same elements that we used on last example but using the union function and the path compression technique, where each element along the path is compressed and point to the root in the structure.

disjoinSet.unionByPathCompression(0,1);
disjoinSet.unionByPathCompression(1,2);
disjoinSet.unionByPathCompression(3,0);

Figure 5: Example of union operation using the path compression technique.

What if we use this path compression and union by rank? See the image below:

disjoinSet.unionByRankByPathCompression(0,1);
disjoinSet.unionByRankByPathCompression(1,2);
disjoinSet.unionByRankByPathCompression(3,0);

Figure 6: Example of union by rank operation using the path compression technique.

Great! We improved the performance and the time complexity of each operation becoming smaller than O(Logn), reducing the complexity of union. Let's see how is the code:

    unionByRankByPathCompression(x, y){
        var xRoot = this.findByPathCompression(x);
        var yRoot = this.findByPathCompression(y);

        if(xRoot == yRoot)
            return;

        if(xRoot.rank < yRoot.rank){
            xRoot.parent = yRoot.value;
            yRoot.children[xRoot.value] = xRoot;
        } else if (xRoot.rank > yRoot.rank) {
            yRoot.parent = xRoot.value;
            xRoot.children[yRoot.value] = yRoot;
        } else {
            xRoot.parent =  yRoot.value;
            yRoot.children[xRoot.value] = xRoot;
            yRoot.rank = xRoot.rank + 1;
        }
    }

However, the bad news is that we can not use this approach using the union by rank because as we can see, this operation changes the heights of the structure.

That's all folks! I hope you have fun learning the disjoint set structure 😁

Code: https://github.com/FernandoBLima/data-structures

< previous | next ( coming soon) >

So we finished our discussion about Disjoint Set structure. 🙌

I hope you have a clear idea how to work. If you found this article helpful or if you find something I miss out or that you like it, feel free to let me know. 😁

Set and MultiSet - Data Structure & Algorithm Part III

Fernando Baptistella — Tue, 31 Dec 2019 02:03:36 +0000

Welcome to the third part of the series, in this post I’ll tell you about the set and multiSet structure and continue our journey on data structure and algorithm. 👩‍💻👨‍💻 However, I recommend reading the hashtable post if you are not familiar with data structures.

Because, unlike the last post when we landed on a strange terrain, here we will be in a place where we should have seen it before. The focus of this post is to learn what a set is with examples of how it works, code implementation using javascript and, of course, answer any questions about it. This data structure is not difficult to learn at first, but it can be a bit complicated.

Let’s continuing our journey! 🌏 🚀

💭 "Those hours of practice, and failure, are a necessary part of the learning process."- Gina Sipley

Outline

The article is divided into the following parts:

Understanding what is Set and MultiSet.
Code implementation and complexity analysis.

◼️ Set

What is it

As you can imagine you already have some basic understanding about what is the sets structure. Basically is a collection of unique elements that can be objects, numbers, strings, Pokémon's ... In other words, anything! 😁

We can also find in many language that support the set such as Java, C, Python, ASP.NET and so on. For instance, the ECMAScript 6 or ES2015 introduced the Set data structure to the JavaScript language. We can initialized by calling:

const s = new Set()

Despite the fact that we can use this implementation, we will avoid and build our own because the goal here is to learn how this structure works behind the scenes.

With that in mind, what we need to create our structure is use an array and add some element. We can also use the list structure, but it is an inefficient and simple implementation where operations such as inserting or deleting do not perform well. Having been said that, there are better approaches to implemented using more efficient data structures such as trees, tries, or hash tables, however, in this post we will use the array and the hash table that we already have seen in this series.

Great! We already have a basic understanding of how we can build the structure of the set, now let's discuss some properties. Every value you insert have to appear only once because this structure does not allow repeated values, see the example below:

A = [1,2,3,4,5,6] // Allowed
B = [1,2,1,2,1,2] // Not Allowed

Moreover, other important factor about this structure is related by the fact that we do not need to order the elements, for instance:

C = [1, 2, 3] 
D = [3, 2, 1] 
// The Set C is the same as set D.

We can say that this structure is an implementation of the mathematical concept of a finite set using the operations of the algebra of sets. Okay, let's put everything that we had learned into our code. But first things first, we will be creating the skeleton off our set class and, as you can notice we have two functions created.

class SetStructure {
    constructor() {
        this.listValues = [];
        this.capacity = 0;
    }

    insert(value){
        if(this.listValues.indexOf(value)) {
            this.listValues.push(value);
            this.capacity++;
        }
    }

    remove(value){
        var index = this.listValues.indexOf(value);
        if(index >= 0) {
            if(this.capacity > 1){
                this.listValues.splice(index, 1);
            }
            this.capacity--;
        }
    }
}

But, wait a second! ✋ Before insert some values we must make sure if the value that we intend insert is not in our array. In the insert() function use the indexOf() propriety to verify if has any occurrence of a specified value in our structure. This method returns the position of element, however, if the array does not contain the data, the value -1 will be returned. We can use a similar logic in remove() function.

As mentioned earlier, this structure is based on the mathematical concepts of sets; therefore, we can use its properties in our code to define some operations using set algebra, such as union and intersection. Let's have a brief discussion of the core set theoretical operations, so take a look below:

Union

As the name suggest this operation will join two sets resulting in a new set structure that combine all members of either A or B set. We can use the math definition to define this operation:

A U B = {x : x ∈ A or x ∈ B}

Let's put in an example:

{1, 2} ∪ {1, 2} = {1, 2}.
{1, 2, 3} ∪ {3, 4, 5} = {1, 2, 3, 4, 5}

To give an illustration of how the union operation is, take a look at the following image:

Figure 1: The union of A and B

Now that we already have a clearly understanding, let's see how it works in our code.

union(set) {
     var newSet = new SetStructure();
     set.listValues.forEach(function(value) {
         newSet.insert(value);
     });
     this.listValues.forEach(function(value) {
         newSet.insert(value);
     });
     return newSet;
};

Intersect

In this operation a new set is created using all elements that the both sets have in common, that can be denoted by A ∩ B. In case of A ∩ B = ∅, then A and B are considered disjoint. The math concept about the intersect is defined as the following:

A ∩ B = {x : x ∈ A and x ∈ B}

Figure 2: The intersection of A and B

And we can write the function that receives a set as parameter like this:

    intersect(set) {
        var newSet = new SetStructure();
        this.listValues.forEach(function(value) {
            if(set.contains(value)) {
                newSet.insert(value);
            }
        });
        return newSet;
    };

Difference

The difference operation, or complement if you prefer, is the difference between the set A and B. But what does it mean? 🧐 In other words, is the result of the values that contains in only one set and can be denoted by the following definition:

A \ B or A − B where {x : x ∈ B, and x ∉ A}

Figure 3: The difference of A and B

Similar to union and intersect functions, we can iterate the list to get the difference between the sets:

    difference(set) {
        var newSet = new SetStructure();
        this.listValues.forEach(function(value) {
            if(!set.contains(value)) {
                newSet.insert(value);
            }
        });
        return newSet;
    }

Symmetric Difference

Another operation that we can create is the symmetric difference, also know as disjunctive union, which is the set where the elements not below in their intersection.

Figure 4: The symmetric difference of A and B

    symmetricDifference(set) {
        var newSet = new SetStructure();
        this.listValues.forEach(function(value) {
            if(!set.contains(value)) {
                newSet.insert(value);
            }
        });
        var setDifference = this;
        set.listValues.forEach(function(value) {
            if(!setDifference.contains(value)) {
                newSet.insert(value);
            }
        });
        return newSet;
    }

⚡️ If you would like to know others functions that I implemented such as removeAll, getAllSubsets, contains, and others, you can access all the code just clicking here.

Subset

The next operation define if every value of set A belongs to the set B and vice-versa. If they contain each other can denoted as A ⊆ B, which can be write as A is contained in B, is equivalent to A = B.

    isSubset(set) {
        return set.listValues.every(value => this.listValues.includes(value)); 
    }

Proper Subset

It is quite similar to subset operation, but two sets can be considered as proper subset if one set is not equal to another but has at least one element.

    isProperSubset(set){
        return set.listValues.some(value => this.listValues.includes(value));
    }

The set is mutable, however, we can create immutable frozenset objects initialized with elements of the given iterable. Which is a set that does not change after being build. In Python, we can use the frozenset () function to create this structure.

list = (1, 6, 7, 4, 9, 6, 2, 3, 5) 
frozenSet = frozenset(list)

Very cool and easy to understand, right? 😁

◼️ MultiSet

The Multiset structure or Bag is quite similar to set structure that we have learned before, but the difference is due to the fact that unlike the set structure allows more than one instance of the element in the structure.

An amazing thing that about programming it that there are many ways to develop the Multiset, we can continue using an array to store the values, or tuples if you are developing in Python.

This structure has the following properties:

items: List of element that contains the data and key.
multiplicity: Property which is a positive integer that gives how many elements has in the Multiset.
cardinality: Summing the multiplicities of all its elements.

Since multiset is a type of set generalization, there are several ways to apply it to problem solving, Fuzzy multisets and Rough multisets, are some examples.

Now that we already know what Multiset is, let's create the main operations, which are: insert and remove.

     insert(key, cardinality = 1){
        try{
            if(key == null || cardinality == null){
                throw new Error('Is not possible to insert a null value');
            }
            var flag = true;
            var listKeys = Object.keys(this.items);
            listKeys.forEach(item => {
                if(item == key){
                    this.items[key] = this.items[key] + cardinality;
                    flag = false;
                    this.cardinality = cardinality;
                }
            });
            if(flag){
                this.items[key] = cardinality;
                this.cardinality = cardinality;
            }
        }
        catch (error) {
            return error.message;
        }   
    }


    remove(chave, cardinality){
        if(this.items[chave]){
            var value = this.items[chave];
            if(cardinality > value){
                this.items[chave] = 0;
            }else{
                this.items[chave] = value - cardinality;
            }
        }
    }

We can use the hash table in our Multiset structure, that is to say, the time complexity is always a constant O(1) to add or search an element. As you can imagine this structure has the same functions as the set, however, there are some differences that we are going to learn together. 🤓

The algebra operations such as union, sum, intersect and difference have similar logic applies as the previous methods described before, so I’ll skip the code explanation of them to not waste our time and only discuss about the difference.

Union

The main difference in the union of two multiset is that each element has the number of instances equal to the maximum of the multiplicity in A and B.

{1, 2, 2} ∪ {2, 2, 3} = {1, 2, 2, 3}.

In this operation the intersection of two multisets is equal to the sum of the multiplicity of an element in A and B.

{1, 2, 2} + {2, 2, 3} = {1, 2, 2, 2, 2, 3}

Intersect

The intersection of two multisets is equal to the minimum of the multiplicity of an element in A and B.
⁡

{1, 2, 2} + {2, 2, 3} = {2, 2}.

Difference

The difference of two multisets is equal to the multiplicity of the element in A minus the multiplicity of the element in B.

{1, 2, 2} + {2, 2, 3} = {3}
{2, 2, 3} − {1, 2, 2} = {1}.

◼️ Conclusion

In conclusion, the most important factor that make the set structure special and unique comparing with the others is that use the core set-theoretical operations defined by the algebra of sets, which allows the use of properties and laws of sets using operation such as union and intersection. In this post we have a brief discussion about this operations.

We have learned that sets can be implemented using various data structures but the most common approach is using array or hash table. Even though the set structure looks like a simple structure there are many languages now include it can be applied in diverse scenarios and different generalizations, such as Fuzzy multisets, rough multisets and in relational databases.

That's all folks! I hope you have fun learning the set structure 😁

Code: https://github.com/FernandoBLima/data-structures

< previous | next ( coming soon) >

So we finished our discussion about Set and Multiset data structure. 🙌

I hope you have a clear idea how to work. If you found this article helpful or if you find something I miss out or that you like it, feel free to let me know. 😁

Dictionary and HashTable - Data Structure & Algorithms Part II

Fernando Baptistella — Mon, 25 Nov 2019 22:37:51 +0000

Continuing our journey in the data structure and algorithms in a galaxy far, far away...

In the previous post, we had learned about linked list, queue and stack. Now we will continue our journey and move on to covering the Dictionary and HashMap data structure.

In this post, I will try to help you to understand these data structure. Once again, I will use JavaScript code examples; however, the main goal is not to go deeper in the language, but to try to demonstrate what makes these structures unique. You can find this structure implemented in several languages such as Python, JavaScript and so on and also in various algorithms, so understanding the structure behind the code it’s important, because what is the point of just learning code?

💭 “You Can't Write Perfect Software. Did that hurt? It shouldn't. Accept it as an axiom of life. Embrace it. Celebrate it. Because perfect software doesn't exist. No one in the brief history of computing has ever written a piece of perfect software. It's unlikely that you'll be the first. And unless you accept this as a fact, you'll end up wasting time and energy chasing an impossible dream.”
― Andrew Hunt, The Pragmatic Programmer: From Journeyman to Master

Outline

The article is divided into the following parts:

Understanding what is Dictionary and Hash table.
How important is a hash function.
Code implementation and complexity analysis.
What is factor load.

◼️ Dictionary

Dictionary, which some people prefer refer as map structure, is a collections of pairs [key, value] of distinct elements that use a key to find a value. A little bit confusing, right? I will try to explain in a different way.

As the name suggest this structure is like a dictionary book, where we can use as an example of being applied to a real-world when you search and found a word followed by his definition. 📚 In our case, the word is the key and the description is the value stored.

At first, you might be wondering if there is some way we can use what we had learned in the last post and use the linked list to create this structure, right? Of course! We can use but we have to adapt the structure adding the key property because a linked list add a new element at the beginning of the list, resulting in an O(1) complexity of time. If we want to delete some value, we need to search the key and as you can remember, is not so efficient. So how we can build this structure? Programming is a kind of magic and we can implement in different ways, let's discover together! 🧐

◼️ Bucket array

As we saw, the linked list couldn’t be used; on the other hand an array can solve our problem. However, do you know what an array is? It is a collection with N elements where each position, called as bucket, in the array can have a value stored. I will try to illustrate in the following figure an array with an element at position 8.

Figure 1: An array illustration

In a bucket array, we can use a key to identify any value stored, like a dictionary book. To get a better understanding of how it works why not create an example to store a key-value pairs. Suppose we have an array and we want to add some value let’s take a look at the example:

var bucketArray = [];
key = 1;
value = 'Darth Vader';
bucketArray[key] = value;

Yeah! We got it! 🙌 It was added the value in to our array using a key. The element stored in the hash table is quickly retrieved using the key. We can add, delete and search the pair value [key, value] with the O(1) constant time. Great! All the problems were solved, right? No, unfortunately. ☹️🥺

Look at the following example assuming that both of our keys has the same value in this case 1.

var bucketArray = [];

key = 1;
value = 'Darth Vader';
bucketArray[key] = value;

key = 1;
value = 'Obi Wan Kenobi';
bucketArray[key] = value;

Do you know what happens when the value 'Obi Wan Kenobi' is added using a key that already have being used? Collision! 💥 And bug! 🐞 We can't add the value because the key has to be unique. With this in mind the bucket array didn't resolve all our problems. ☹️

◼️ HashTable

We don’t need to be hurry about that! We can create a function to convert the key in an integer to resolve and handle our problem. Then using the hash value created we can use as an index in our array to avoid the collisions and that is what makes the hash table particularly useful. Is it confused? I will try to explain.

We need to keep in mind that the hash table is another approach to implement the dictionary data structure and the difference between them is by the fact how we can store and access data. Just remember that a hash table is composed with two parts, an array and hash function.

Figure 2: A example of hash table

Talk is cheap. Show me the code! 😁 Our main hash table class would looks something like this:

class DumpHashTable {
    constructor() {
        this.list = {};
        this.length = 0;
    }
}

Hash Function

In order to understand hash table we first need to know what the purpose of hash function is. As I said before, the main goal in a hash function is to convert a key in an integer and try to minimize the collision that can happen when we are adding a new value in the array.

In this function, the key is the input parameter and has a range between 0 and infinite and we need to distribute the keys uniformly across an array. It is necessary to reduce the value of the key and compress in the map function to convert in a range between 0 and N - 1, where N is the length of our array. Suppose we have an array of size 10 and our key has the value 23, it doesn’t fit because the value is larger than the size. Therefore, we need to compress the key into the size of the array.

hash(x) : x → {0, 1, 2, N − 1}

There are many ways to achieve a good hashing mechanism, let’s take a look in the most common function, the modulo operation.

Suppose our array has length N and we need to add a new value. Then is necessary to convert the key into the array size using the mod operation, which result in the hash value, right?

hash(x) = x mod N

However, we cannot choose a random number to be used in the mod operation because we want to avoid clusters. If we choose a small number or a hash value that has many multiples we will get similar values, and as a result, the hash table will not be distributed. Let's consider a table of size 24 and assuming we have a set of keys between 0 and 100 in a uniformly random distribution.

𝐾 = {0,1,...,100}

Every number in 𝐾 that has a common factor with the number 24 will be hashed as multiple of this factor; in this case, the factors of 24 are 1, 2, 3, 4, 6, 8, 12 and 24. That is to say, the values won’t be spread over all possible value between 0 and the array size.

24 % 24 = 0
48 % 24 = 0
72 % 12 = 0

We can use a large prime number to avoid this problem, using a value we can spread more the hash values over all possible index between 0 and the array size, and as consequence, every value stored in the array will be within the range of prime number.

To minimize collisions it is important to reduce the number of common factors and choosing a prime number is how we can deal with because are the only number that have two different dividers: 1 and itself. For instance, let’s take a closer look in the following image where 100000 values were generated between the range {0,1,...,1000} in a normal distribution using 97 and 100 mod value. Can you notice which one is the best option?

Table 1: Comparing a hash function using a normal distribution using 97 and 100 mod value

We can have the same result using uniform, triangular and exponential distribution.



UNIFORM	TRIANGULAR	EXPONENCIAL

Table 2: Comparing others distributions using 97 and 100 mod value

Allright, now that we understand how deal with hash function; we can see how our hash function would be considering the last example given:

hash(data){
   return data % 97;
}

We also can use a string instead a number to use as the key, we just need to sum of the ASCII values of the characters in our string as we can see

hash(data){
    var hashTable = 0;
    for(var i = 0; i < data.length; i++){
       hashTable += data.charCodeAt(i);
    }
    return (hashTable) % 97;
}

Another common hashing mechanism is the MAD (Multiply, Add, Divide).

◼️ Collision Handling

Even though we use some hash function sometimes it is almost impossible to create a uniform random distribution to avoid collisions. Therefore are many ways to handling collisions, as we can see below.

Separate chaining

We use this method when the key is already used, which means it is impossible to store a new value. We can handle this situation creating in the index a point to a linked list structure to store the new value into our array, in this way; the number of keys can exceed the size of the hash table. Nevertheless, is required more space to store the keys using the linked list, and at the same time, some buckets could be never used, which leads to wasted space.

In addition, using a linked list bring us to the disadvantage of searching and deleting values and to minimize this problem is common to limit the number of values that can be inserted in the linked list. The worst scenario of separate chaining is when all values are inserted at the same index and all the keys will be in only one linked list. To give an illustration of this approach, let’s look at the following image.

Figure 3: Using separate chaining approach to handle collision in hash table.

    insert(value) {
        var key = this.hash(value); 
        let indexHash = new IndexHash(value, key);
        if(this.list[key]){
            indexHash.next = this.list[key];
        }
        this.list[key] = indexHash;
        this.length++;
    }

◼️ Open addressing

Another way to improve the hash function is using the open addressing approach. On contrast of separate chaining, all values are stored in the bucket array and the hash table can never exceed the size. There are different ways to implement and the most common approaches are:

Linear Probing

Our hash function that we are working on it happens to have collision on the index; one way to resolve is increasing the index and check if the next element on the bucket array is available to insert the new value.

hash(key) = (hash(key) + i) mod N

The probing sequence for linear probing will be:

newIndex = (index + 0) % hashTableSize
newIndex = (index + 1) % hashTableSize
newIndex = (index + 2) % hashTableSize
newIndex = (index + 3) % hashTableSize
and so on…

We have to iterate the array to check if the index of hash value of the 'hash(key) + i' is available. We can see how it works:

    insert(value) {
        try{
            var key = this.hash(value);
            key = this.proibingHash(key, value);
            let indexHash = new IndexHash(value, key);
            this.list[key] = indexHash;
            this.length++;
        }
        catch (error) {
            return error.message;
        }   
    }

    proibingHash(key){
        if(this.list[key] == null){
            return key;
        }else{
            let flag = false;
            let index = 1;
            do{
                if(index >= this.ARRAY_LENGTH || this.length == this.ARRAY_LENGTH){
                    throw new Error('Error! Array size exceeds');
                }else{
                    let indexTable = index;
                    indexTable = key + indexTable;
                    if(this.list[indexTable] == null){
                        flag = true;
                        index = indexTable;
                    }else{
                        index++;
                    }
                }
            }while(flag == false);
            return index;
        }
    }

In proibingHash function, we iterate the array to check if the next index is available and if the size is exceed. It is important to say that the remove function has a similar logic of insert function, as we can see in the code bellow:

    remove(value){
        if(value == null){
            return false;
        }
        var key = this._hash(value);
        key = this.removeProibingHash(key, value);
        if(this.list[key]){
            this.list[key].value = null;
            this.length--;
            return true;
        }else{
            return false;
        }
    }

    removeProibingHash(key, value){
        if(this.list[key] && this.list[key].value == value){
            return key;
        }else{
            if(this.list[key] == undefined){
                return null;
            }
            let flag = false;
            let index = 1;
            do{
                if(index >= this.ARRAY_LENGTH || this.length == this.ARRAY_LENGTH){
                    return false;
                }else{
                    let indexTable = index;
                    indexTable = key + indexTable;
                    if(this.list[indexTable] && this.list[indexTable].value == value){
                        flag = true;
                        index = indexTable;
                    }else{
                        index++;
                    }
                }
            }while(flag == false);
            return index;
        }
    }

⚡️ If you would like to know how I implemented, you can access the code just clicking here.

Quadratic Probing

Okay, we talked about how linear probing can be useful, but let’s spend a minute to talk about the disadvantages of this approach. The biggest problem is the fact that can occur clusters when many elements are in the consecutive array index. Just imagine the following scenario where our bucket list has more than 1 million of element and we need to add a new element which index already was stored.

Consequently, we have to go through many indexes to find an empty space in the array. Can you see that linear probing is not so efficient? It could take time to search an element or find an empty bucket. The biggest problem is when clustering of values in our array occur. We might want to solve this problem using a different probing approach, which lead us to the quadratic probing. Instead, add the index we have to add the power of the original index.

hash(key) = (hash(key) + I^2 ) mod N

The sequence will be:

newIndex = hash(key) % hashTableSize
newIndex = (hash(key) + 1^2 ) % hashTableSize
newIndex = (hash(key) + 2^2 ) % hashTableSize
newIndex = (hash(key) + 3^2 ) % hashTableSize
and so on…

On the other hand, depending on the size of the array an infinite loop may be created and not able to add the new element.

Double Hashing

Here we have a different approach comparing to linear and quadratic probing, because a secondary hash function is used as a fixed increment in the jump distance, an advantage is that we can use a unique jump value.

hash(key) = (hash1(key) + j hash2(key)) % hashTableSize

Where j is the index, the probing sequence will be:

newIndex = (hash1(key) + 1 * hash2(key)) % hashTableSize;
newIndex = (hash1(key) + 2 * hash2(key)) % hashTableSize;
and so on…

Furthermore, as we can see the open addressing, such as linear, quadratic and double hashing has almost the same drawback and we cannot exceed the number of spaces in the bucket array.

◼️ Time complexity

In general, we can say that the time complexity in big O notation is:

Algorithm	Average	Worst case
Search	O(1)	O(n)
Insert	O(1)	O(n)
Delete	O(1)	O(n)

Table 3: The time complexity of Hash table

◼️ Load Factor

Now we will discuss the relationship between the number of entries and buckets, the load factor, which is equal to the number of elements divided by the number of buckets.

It is expected to have emptier bucket to accommodate all the elements that we inserted in our bucket, resulting in a load factor less than 1. When is more than 1 is necessary to rehashing, which means to increase the number of buckets and change the hash function, otherwise, the element can't be add into our array.

◼️ Conclusion

That’s it! The Hash table is an extended topic and is almost impossible to cover everything in just only one article. However, as we can see, it is crucial to understand how and why the data structure is used, even though a linked list could be used to create a structure of collections of pairs [key, value] of distinct elements, the result won't be so efficient.

Which makes us to use the bucket array that have the speed advantage, where we can access a value in a constant time O(1), however, many values can be added resulting in collisions. We have learnt that there are many ways to build a hash function to avoid this behavior but sometimes is almost impossible to create a perfect function, which can make this structure quite inefficient when many collisions occur. As consequence, some approaches were developed to try to solve or handle this issue but each one has advantage and drawbacks.

All of this points to the conclusion that by comparing the approaches we can see that we do not have a better one, because depend on context and other factor, such as where an extra space is needed or not, or even whether the number of keys to be stored cannot be exceeded, for instance.

That's all folks! Now that we had a chance to discuss this data structure I hope you keep coding and having fun. 🤓

Code: https://github.com/FernandoBLima/data-structures

< previous | next ( coming soon) >

So we finished our discussion about Dictionary and Hash Table data structure. 🙌

I hope you have a clear idea how to work. If you found this article helpful, if you find something I miss out or that you like it, feel free to let me know. 😁

Linked List, Queue and Stack - Data Structure & Algorithm Part I

Fernando Baptistella — Sat, 26 Oct 2019 01:46:00 +0000

Learning the concepts and how to implement Linked List, Queue and Stack.

Welcome to my first article where I am going to talk about Data Structures. I am so excited to be writing this series! I have been postponed this for a long time and many reasons, maybe I can write about it another time, but finally I decided to complete this goal.

Here I will show how important this topic is and why you should understand all the concepts. In my point of view is important to know the concepts and how it works behind the scenes, although there are many frameworks that already have the complete implementation. But, trust me, it is essential for your career and maybe you may need it in the future to resolve some problem. 👨‍💻👩‍💻

Here we are going to have a brief discussion with Javascript examples and I will start from the beginning, gradually, because we do not have to be hurry! So, let’s diving in this fantastic world called data structure and algorithms together. 😀

💭 "Bad programmers worry about the code. Good programmers worry about data structures and their relationships." - Linus Torvalds

Outline

Discussion about Singly, Doubly and Circular Linked List.
What is a Queue and Stack?
Terminology.
When and where is used?
Code implementation and complexity analysis.

What is a Linked List?

Before we start to discuss, we need to formulate a clear understanding of what a linked list is. A collection structure represents a sequence of nodes. But, wait! ✋ What does node mean? 🤔 An object that contains value and pointer with reference to stores the address for the next element into the sequence of the list, as you can see in the following figure:

Figure 1: Linked List representation.

Actually, you can imagine a pointer, as a place where you can find and obtain the stored value in the node, is a reference to a location in memory. The first node in the list represent a head and has a pointer to the next element, and as you can imagine the last node is the tail because has a null pointer to the next node.

You also can use a pointer to the previous object. As a result, a Doubly Linked List type is created.

Another important aspect to understand linked list is related to the efficient memory utilization. Is not necessary to pre-allocate memory, as a consequence you can add as much items you want in the list. However, some problems can show up if is required more memory than you can have, because each node has a pointer and other memory for itself.

Terminology

As you can see in the image in the section above, we define two properties:

value: Element that holds the data.
next: Point to the next node.

prev (optional): Can be used to point to the previous node. You can see more about in Doubly Linked List Structure.

Let's begin!

Now that we are on the same page with the concepts, let’s start the discussion more deeply about Linked List methods, translate the concepts into to our code, and finally implement our data structure. At the beginning, we are going to focus in the Linked List, because it is the most common and simplest data structure linear collection of data elements.

Let's start to work! 😃

◼️ Singly Linked List

Is called as singly because a node only hold a reference to the next element of the sequence and you cannot access previous elements because it does not store any pointer or reference to the previous node, as you can see in the figure.

Figure 2: A singly linked list that contain an element and a pointer to the next node

Before we describe the operations, we need to define the most important part in our code that will help us to build the linear list structure, the node class.

class Node {
   constructor(value, next) {
      this.value = value;
      this.next = next;
   }
}

Our main class only has a reference to the value and the next node, pretty simple, right? So, let’s move on and define the Linked List class, which has the head property that point to the first element into the list, other property we have to declared is the size, which give to us the number of nodes that exist into our list.

class LinkedList {
    constructor() {
       this.head = null;
       this.length = null;
    }
}

Okay, continuing the discussion we have to add methods to our class. Let’s check out:

addAtHead: Our first method is used to add a new element at the beginning of our data structure. This method has a constant running time (O(1)). But what does it mean? 🧐 It means that it takes the same amount of time to add a value in the list, is a constant time. In this case is necessary only to move one time to add a new element in the first position into the list. As result, we need to update only the current head that will be pointing to the new item that we are going to be creating. Here’s how it should be:

addAtHead(value){
   if(linkedList.head){
      var newNode = new Node(value, this.head );
      this.head = newNode;
   }else{
      var newNode = new Node(value, null);
      this.head = newNode;
   }
   this.length++;
}

removeAtHead: If we want remove one element from the head all we have to do is replace the head by the following element. Like the method before the constant running time is O(1).

removeAtHead(value){
    if(this.head){
       var newHead = this.head.next;
       this.head = newHead;
       this.length--;
    }else{
       return false;
    }
}

search: If we are looking for a specific item? Do not be hurry; we only need iterate the list until the end to find the element in the list. But imagine the following scenario: We have a list with 1000 items and we are looking for the 999 item. Can you guess what can happen? If we want to get some specific value or node at position N then we have to moving the pointer throw the entire list to find it. This can cause a problem with the access time.

    search(value){
        if(this.head){
            var node = this.head;
            var count = 0;
            while(node != null && node.value != value){
                if(count >= this.length && node.value != value){
                    return false;
                }
                node = node.next;
                count++;
            }
            if(node == null){
                return false;
            }else{
                return true;
            }
        }else{
            return false;
        }
    }

There are others functions like getAtIndex, addAtIndex, removeAt and reverse that I would like to discuss, but they have similar logic applies as the previous methods described before, so I’ll skip the explanation of them to not waste your time.

⚡️ But if you would like to know how I implemented, you can access all the code just clicking here.
__

◼️ Doubly Linked List

As I mentioned earlier, the Doubly Linked List is a structure that has capacity to pointer to the previous node, which is the biggest difference comparing with the Singly List. Now we gain the power to move traversed backward in the list. For instance, each node has a pointer to the previous element, allowing you to move through the list from the tail, as show in the picture below.

As Uncle Ben said to Peter Parker, “with great power comes great responsibility”. As consequence, is required more space to store the addresses of previous elements instead just one to the next element in list, so takes two more memory comparing with the singly structure.

Besides that, mostly all functions and behaviors are quite similar with the Singly List. With basic understanding of Linked List, it is so easy to build and extend functionality to make it a Double List. So easy, right? 😁 You can feeling that we are having progress. 💪

Figure 3: A doubly linked list with pointer to the previous element

Even though the behavior is similar, we need to update the Singly List functions such as addAtHead, removeAtHead, search and others to consider the previous property. Besides these functions, we have new weapons to use here, as you can see below:

addAtTail: We define a new element at the bottom of the list and point the last element as the tail. Can you imagine the constant running time?

    addAtTail(value){
        var newNode = new Node(value, null, this.tail);
        if(this.tail){
            this.tail.next = newNode;
            this.tail = newNode;
        }else{
            this.head = newNode;
            this.tail = newNode;
        }
        this.length++;
    }

removeAtTail: Here the last item from the list is set to the null value. As a result, the final element become the previous element of the last element.

    removeAtTail(){
        if(this.length === 1){
            this.removeAtHead();
            this.tail = null;
            return;
        } else if (this.length > 1){
            this.tail = this.tail.prev;
            this.tail.next = null;
            this.length--;
            return;
        }
        return false;
    }

◼️ Circular Linked List

The only difference between the doubly Linked List is the fact that the tail element is linked with the first element in the list. As a result, a loop was created and now we can move forward and back-forward into the entire list.

Figure 4: Circular linked list that contain a link between the first and last element.

Now we will use the entire acknowledgement that we learned to implement two new data structure.

◼️ Queue

The First-In-First-Out (FIFO) is an example of a linear data structure where the first element added to the queue will be the first to be removed. For instance, you can visualize this behavior where you are in a queue in a store, bank or supermarket.

🚶‍♂️🏦🚶‍♀️🚶‍♂️🚶‍♀️🚶‍♂️

A new element is added to the end of the list by the enqueuer (addFromTail) function and removed from the top of the list using the dequeue (removeFromTail) function. You can see other people or find in a book referencing the queue as removing or poling method, for me I prefer only dequeue. Other common operation in this structure is the peek that return the item at the top of the stack as peek.

However, when should I use these structure data? 🤔 It is suggested to use Queue when the order matter, like a queueing system for requests.

Figure 5: Representation of a Queue.

◼️ Stack

Known as LIFO (last in, first out) data structure, you can visualize understanding how it works making an analogy when a set of items is stacked on top of each other, creating a pile of books.

Like I said before, this structure has some similarities from Linked List and you can use addFromTail (Push) and removeFromTail (Pop) operations in your stack structure. Just like a queue, the operation that return an item at the top of the stack is called as peek.

You can find this structure in mechanisms in text editors, compiler syntax checking or also on a graph.

Figure 6: A representation of a stack and the Push and Pop functions.

◼️ Time Complexity

You can see the time complexity in the image below, where n is the length of Linked List.

Figure 7: The time complexity.

Let’s create an example by adding some values in the head and then removing in a Linked List using addAtHead and removeAtHead functions. In addition, using the time() object in Javascript will allowed us to time and analyzes the performance of our code, as the follow figure:

Figure 8: Output after insert and remove some values in the Singly Linked List.

As you can see, we add some values in the list that show us how faster it is. Seeing the values we can realize that the execution time become a constant. The image below show the plot using Python with the Panda DataFrame library.

Figure 9: The consume time between addAtHead and removeAtHead functions.

We are done 🙌

◼️ And that's it!

To sum up our brief discussion, we have learnt that the Linked List is a simplest and dynamic data structure that can be used to implement others structures such as Queue and Stack.

You can use these structures to perform a huge amount of insertion and deletion of items. It run fast by the fact that we need update only the next pointer in the node. However, if we want to get some specific value or node at position N, a problem with access time may occur if the size of the list is longer.

Other important factor is the efficient memory utilization, it not necessary to pre-allocate memory. Nevertheless, in case you need more space, a problem related to a contiguous block of memory can occur.

That's all folks!

Code: https://github.com/FernandoBLima/data-structures

| next ( coming soon) >

So we finished our discussion about Linked List, Queue and Stack data structure. 🙌

I hope you have a clear idea how to work. If you found this article helpful, or if you find something I miss out or that you like it, feel free to let me know and subscribe!. 😁