Learning data structure in JavaScript for beginners

Introduction

It’s the note for learning data structure in JavaScript. I studied the source code form trekhleb’s Github repository. It’s a nice material for the JavaScript developers and beginners to learn data structure.

Besides trekhleb’s Github, I also refer to Break Away: Programming And Coding Interviews from Udemy and the videos from Hackerrank. This course uses Java to implement and explain data structures.

This article summarizes and includes the following data structure.

The table shows the time complexity of the common operations. The implementations of stack and queue are based on the linked list. They allow users to insert or delete nodes efficiently.

To have better performance for traversing the entire container, we may consider using a hash table or binary search tree. It depends on whether you want to order data or not.

1. Linked list
2. Doubly linked list
3. Queue
4. Stack
5. Hash table
6. Binary search tree
7. Binary heap

1. Linked list

The single linked list is a unidirectional list.

The advantage of a linked list is that it allows users to insert or delete nodes efficiently with constant time.

However, the linked list is not good at access data. We are not allowed to access data with index in the linked list. We can only find the target data by traversing the container.

Complexity Analysis

• O(1): append, prepend, deleteHead
• O(n): insertAt, deleteAt, delete, search

Implementations

In this section, I refer to the source code trekhleb’s Github and do some modifications with my personal thoughts.

1.Create a linked list

A single linked list has the head and the tail node. Each node has a value field and a pointer to the next node

Implementation for the data structure

2.Append

• The time complexity is O(1) or O(n) and it depends on how we implement the linked list

• The solution for the doubly linked list

3. Prepend

• Time complexity: O(1)

• The solution for the doubly linked list

4. Insert at a specific index

• Time complexity: O(n)

5.Delete the head node

• Time complexity: O(1)

• The solution for the doubly linked list

6. Delete the node for the specific position

• Time complexity: O(n)

7. Search and Delete

The deleting operation has to follow these orders because the linked list doesn’t have the pointer to point the previous node.

• Delete the head node if the value equals the target value
• Delete the immediate node if the value equals the target value
• Delete the tail node if the value equals the target value

• The solution for the doubly linked list

8.Search

Go through the entire list and return the target node with the target value or the callback function returns true

References

• Data Structures: Linked Lists

Related LeetCode questions

• 86. Partition List (medium)

2. Doubly linked list

A doubly linked list is a bidirectional list. It has an extra pointer called the previous pointer to link the previous node. The main difference between the linked list and the doubly list is the search and delete operation.

In this section, I refer to the source code on trekhleb’s Github and do some modifications with my personal thoughts.

Complexity Analysis

• O(1): append, prepend, deleteHead
• O(n): insertAt, deleteAt, delete, search

Implementations

1.Create a linked list structure

A double linked list has the head and the tail node. A node has a value, a pointer to the next node, and a previous pointer to the previous node which is different from linked list.

2.Append

• It’s the same as the linked list. The difference is to set the previous pointer of the new node to the tail node.

3. Prepend

• Insert new node from the head node. It’s the same as the linked list. The difference is to set the previous pointer of the head node to the new node.

4.Delete the head node

• Time complexity: O(1)
• The difference is to set the previous pointer of the head node to null.

5. Search and Delete

• Time complexity: O(n)
• Unlike the linked list, the deleting operation doesn’t have to follow orders because the doubly linked list has the previous pointer.

3. Queue

The queue is a linear data structure that is based on the linked list. The character of the queue is that it’s a FIFO (first in first out) data structure.

In this section, I refer to the source code on trekhleb’s Github and do some modifications with my personal thoughts.

Complexity Analysis

Implementations

1.Create a queue structure

We can use a linked list to implement a queue. We’ll push new nodes from the tail node and pop the node from the head node.

Implementation for the data structure:

2. Enqueue: append a node at the end of the linked list (back)

• Time complexity: O(1)

3.Dequeue: remove the head node of the linked list (front)

• Time complexity: O(1)

Queue related questions

• Implement a circular queue (enqueue, dequeue, front, rear, isEmpty)
• Implement a queue by 2 stacks (enqueue, dequeue, front, rear, isEmpty)
• BFS questions

References

• Data Structures: Stacks and Queues
• Algorithms, Part 1 Course from Princeton — Stack, Queue, and Week 2 Assignment Deques and Randomized Queues

4. Stack

Like queue, the stack is a data structure that is based on the linked list. The character of the stack is that it’s a LIFO (last in first out) data structure.

In this section, I refer to the source code on trekhleb’s Github and do some modifications with my personal thoughts.

Complexity Analysis

Implementations

1.Create a stack structure We can use a linked list to implement a stack. We’ll push new nodes from the tail node and pop the node from the head node.

Implementation for the data structure

2.Push: append the new node to the linked list from the head node

• Time complexity: O(1)

3.Pop: remove the head node of the linked list

• Time complexity: O(1)

Stack related questions

• Implement the min stack
• Recursive questions: backtracking

5.Hash table

A Hash table is a linear data structure based on an array. It’s an array of the linked list of the value.

Complexity Analysis

The advantage of the hash table is that it allows users to access data by index efficiently with constant time.

key => lookup
"John" => Person(20, "man")
"merry" => Person(22, "woman")
...

It uses the hash key to index data and deals with the collision issues with different kinds of methods.

string -> hash code -> index

ex. merry-> hash code -> 0

hashTable[0] = Person(22, "woman")

In this section, I refer to the source code on trekhleb’s Github and do some modifications with my personal thoughts.

Implementations in JavaScript

1.Create a hash table in JavaScript

• Use an array to store values in the different linked list
• Store the original key and the value to the linked list node

2.Hash function

The hash function is the most important component of a hash table which is used to map the key to a specific bucket. — from Leetcode

1. Turn the key into the hashed key and use linked lists to store the new node with the same original key inorder to handle the collision
2. Reduce the hashed number to fit the table size

3.Insert

• Time complexity: O(1)
• First, we use the hash key to decide which bucket we will store
• Second, we append to the linked list with original key

4.Search

• Time complexity: O(1) ~ O(n)
• First, we choose the bucket with the hash key
• Second, we search the value in the linked list with the original key

5.Delete

• Time complexity: O(1)
• First, we choose the bucket with the hash key
• Second, we delete the value in the linked list with the original key

Hash table related questions

• Implement the hash set without built-in hash table functions
• Implement the hash table without built-in hash table functions
• Duplicates

References

• Data Structures: Hash Tables

6. Binary search tree

In this section, I refer to the source code on trekhleb’s Github and do some modifications with my personal thoughts.

Definitions

A binary search tree (BST), a special form of a binary tree, satisfies the binary search property:

The value in each node must be greater than (or equal to) any values stored in its left subtree.

The value in each node must be less than (or equal to) any values stored in its right subtree. -Leetcode

Complexity Analysis

• Time complexity: depends on branches and the depth

Recursive runtime 

= O(branches ^ depth), depth = log N (N = total nodes)

Time complexity of BST
= O(2 ^ log N) (N = total nodes)
= O(N)

Time complexity of balanced BST 
= O(log N) (N = total nodes) -> don't have to go through every nodes

• Space complexity: depends on the number of nodes

O(N) (N = total nodes)

• The following table shows the time complexity of the binary tree (n total nodes)

Implementations

1. Create a binary tree structure

• A single node has left child, right child, parent, and value

2. Insert

• Time complexity: O(log n) ~ O(n)

3. Search

• Time complexity: O(log n) ~ O(n)
• Check the node’s value. Search to the left node if the value is less than the target value, vise versa.

4. Search the minimum node

• Time complexity: O(n)

5. Search and remove

• Time complexity: O(log n) ~ O(n)

Properties

1. Height (depth)

• The height of a node means the max depth of the right sub-tree and left sub-tree.

2. Balance

• For the balanced BST, the height difference between the left sub-tree should be less than or equal to one.

Common problems

• symmetric tree ->deep copy, is same, swap (101. Symmetric Tree)
• validate BST (98. Validate Binary Search Tree)
• lowest common ancestor

References

• What is the “get” keyword before a function in a class?
• getter
• static

7. Binary heap

Heap is just a tree with a special property or constraints on the values of its nodes which is called the heap property the constraint.

In this section, I learn to implement the data structure fromBreak Away: Programming And Coding Interviews with slight modifications.

Complexity Analysis

Shape property

1.Every level of the binary tree in a heap is filled except perhaps the last. The heap should form a complete binary tree

2.Implement by an array. If there is a node at index i.

• It has a left child at index: 2i + 1
• It has a right child at index: 2i + 2
• It has a parent at index: (i — 1)/2

Heap property

1.Minimum heap:

• Every node’s value should be <= value of its children
• The node with the smallest value should be the root of the tree

2.Maximum heap:

• Every node value should be >= value of its children
• The node with the largest value should be the root of the tree

Implementations in JavaScript

1.Heapify down (complexity: O(log n) for each call)

• Minimum heap

heapifyDown(index) {
    var leftIndex = getLeftChildIndex(index),
        rightIndex = getRightChildIndex(index),
        smallerIndex = -1;

if (leftIndex !== -1 && rightIndex !== -1) {
        smallerIndex = getNode(leftIndex) < getNode(rightIndex) ? leftIndex : rightIndex;
    } else if (leftIndex !== -1) {
        smallerIndex = leftIndex;
    } else {
        smallerIndex = rightIndex;
    }

if (smallerIndex === -1) {
         return
    }

if (getNode(smallerIndex) < getNode(index)) {
        swap(smallerIndex, index);
        heapifyDown(smallerIndex);
    }
}

2.Heapify up (complexity: O(log n) for each call)

• Minimum heap

heapifyUp(index) {
    var parentIndex = getParentIndex(index);
    if (parentIndex !== -1 &&
        getNode(index) < getNode(parentIndex)) {
        swap(parentIndex, index);
        heapifyUp(parentIndex);
    }
}

3.Insert (complexity: O(log n))

insert(value) {
    this.heapContainer.push(value);    
    this.heapifyUp(this.heapContainer.length - 1);    
    return this;
}

4.Search (complexity: O(n))

find(value)    
    const foundItemIndices = [];
    for (let itemIndex = 0; itemIndex < this.heapContainer.length; itemIndex++) {
        if (value === this.heapContainer[itemIndex]) {
            foundItemIndices.push(itemIndex);
        }
     }
     
     return foundItemIndices;
}

5.Remove (complexity: O(log n) for each call)

• Replace the target node with the last node
• Heapify down or heapify up the target node

remove(value) {
    const numberOfItemsToRemove = this.find(value).length;
    for (let iteration = 0; iteration < numberOfItemsToRemove; iteration ++) {
        const indexToRemove = this.find(value).pop();
        if (indexToRemove === (this.heapContainer.length) - 1) {
            this.heapContainer.pop();
        } else {
            this.heapContainer[indexToRemove] = this.heapContainer.pop();
        }

const parentNode = getNode(getParentIndex(iteration));
        if (this.getLeftChildIndex(indexToRemove) !== -1 && parentNode !== 'undefined') {
            this.heapifyDown(indexToRemove);
        } else {
            this.heapifyUp(indexToRemove);
        }
    }

return this;
}

Summary

Thanks for your patient. I am Sean. I work as a software engineer.

This article is my note. Please feel free to give me advice if any mistakes. I am looking forward to your feedback.

Please feel free to clap if this article can help you. Thank you.

You can also subscribe my page on Facebook.

Related topics

How to use the two-way binding in Knout.js and ReactJS?

Learn how to use SignalR to build a chatroom application

My reflection of :

IT & Network:

Database:

Software testing:

Debugging:

DevOps: