MY SHORT NOTE TO DATA STRUCTURE Author: Nuelgeek | Software Engr | Smart Contract Developer

ABOUT :

This note will contain a summary of different data structures, algorithms, and some implementation on typescript. These contents are notes I made up from Data structure classes from Frontend masters.

AIM :

This note is to help you with snippet of data structure and algorithms meanings and how it works.
It can be useful for preparation of job interview without the hassle of reading voluminous information.
Looking for straight forward contents on Data structure, this is for you.

! Let's Gooooooooooo

What is Data Structure ?

Data structures frame the organization of information so that machines and humans can better understand it.

What is Alogrithm ?

Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output.

What is Big O ?

Big O is a way to categorize your algorithms time or memory requirements based on input. It is not meant to be an exact measurement. It will not tell you how many CPU cycles it takes, instead it is meant to generalize the growth of your algorithm.

Important Concepts

Growth is with respect to the input
Constants are dropped
Worst case is usually the way we measure

SEARCH

Linear search is an alorithm technique, where you must traverse through the array's index to obtain a value. that is measurable in O(N) . typescript implementation
A form of search method called binary search involves halving the size of an ordered dataset until the target value is located. Measured in O(logN) or O(NlogN). typescript implementation

SORT

Bubble sort is a type of algorithm where a single iteration produces the largest number (data) at the last index till the dataset is sorted. The next iteration won’t include the last index. It is measured in O(N^2). typescript implementation
A linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. Runtime is O(1).
A Queue is a specific implementation of a linked list where there is no Bi link to the Node, which is denoted as FIFO (First In First Out) operation. The runtime is N(1). typescript implementation
A Stack is a single-Linked list where we get to add to it and remove from the head, denoted as FILO (First In Last Out). Runtime is O(1). typescript implementation

ARRAY

Array vs Linked list

Array	Linked list
1. Access to Indices	Indices don’t exist in the list.
2. It is O(1) when you want to write into an array.	It is O(1) when you want to insert into a listext
3. You have to allocate the memory of your array up front, even if you’re not aware of the memory length needed.	Memory are created instantly when a data is added to the node, but it costs a runtime to create the memory.
4. You have options of search methods in your array. E.g. Binary Search etc	Linear search is your only option when you want to search for a data in your list.

ArrayList uses the array as the fundament base to perform extra operations on it like Resizing, Pushing, Popping etc. Array list is time-consuming using Enqueue/Dequeue and fast with Push/Pop.typescript implementation
Array Buffer, is used when there is some uncertainty about the amount of data or the rate of arrival of the data that will be placed there.

RECURSION

Recursion is a type of algorithm that constantly calls its function until the base case is satisfied, or an action is completed. Understanding your base case will help you comprehend recursion better.

Three steps make up recursion.

Pre; Before recusing, you can do an operation.
Recuse; Does the calling of the function.
Post; After recusing, you can execute an operation.

Even if you don't use these stages directly, it's still vital to be aware of them because pathing depends heavily on them. MazeSolver algorithm Implementation to understand recursion

Note :

If you have a solid understanding of why you should stop recusing, that reason makes up a solid base case.
You might ask when should you use a recursion algorithm instead of loop algorithm?; Answer: When there is no defined end or when there is branching factor.

QUICK SORT

Divide and conquer is a strategy used by the QuickSort algorithm. The algorithm selects a pivot element and moves the array's elements in such a way that those that are smaller than the pivot element are moved to the left side and those that are greater are moved to the right side. The subarrays to the left and right of the pivot element are then sorted repeatedly by the algorithm. The running time of this algorithm is O(NlogN) or O(N^2)

TREE

The tree is a data structure that starts from a single point and goes all down like roots, the computer’s hard drives, its directories and how it is organized is a good illustration of a tree. A tree is a structure made up of one node called the root and zero, one, or more subtrees. It can also be empty and have no nodes.

TREE TERMINOLOGY

Root: The most parent node. The First. Adam.
Height: The longest path from the root to the most child node
Binary tree: A tree in which has at most 2 children, at least 0 children
General tree: A tree with 0 or more children
Binary search tree: A tree in which has a specific ordering to the nodes and at most 2 children
Leaves: A node without children
Balanced: A tree is perfectly balanced when any node's left and right children have the same height.
Branching factor: The amount of children a tree has.

Traversal | Visiting a Node

There are different ways in which you can visit the nodes of a tree.

Pre order
In order
Post order

Inorder traversal traverses one subtree of a node, visits the node, and then traverses its other subtree. Preorder traversal visits a node and then traverses both of its subtrees. Postorder traversal traverses both subtrees of a node, then visits the node. The traversal method makes use of recursion technique while visiting the nodes. The running time of this traversal is O(N). Implementation (PreOrder, InOrder, PostOrder). Note: This type of order is Depth First search | DFS, We implicitly used stack DS for calling the recuse function.

TREE SEARCH

Breath first search: This is a type of tree search that implicitly makes use of Queue data structure while visiting each node on a tree level. The run time of this data structure is O(N), but if make use of an array list, the run time will be O(N^2). Breath first search Implementation.

Note: An Interview question example of comparing two binary trees to see if they equal in both shape and structure. Depth-first search preserves tree shape, while breadth-first search does not. implementation.

Heap (priority queue)

Heap data structure as a binary tree, where every child and grandchild is smaller (MinHeap) or larger than (MaxHeap) the current node.

Whenever a node is added, we must adjust the tree
Whenever a node is deleted, we must adjust the tree
There is no traversing in the tree
Binary is always a complete tree

Some cool characteristics

It is self-balancing
It can be used for priority
Funnest data structure to implement, but easy to get wrong!

The runtime of this algorithm is O(N log n). Heap Typescript implementation .

Tries

A trie is a special tree that can compactly store strings. Also known as radix tree, prefix tree, digital tree, you can perceive is as an auto complete e.g., when you swipe through your phone keyboard it auto generates a word for you that’s how a trie works. Runtime O(1).

Graphs

Graphs are a series of node with some amount of connection or no connection, and they are connected nodes without roots.

Terminology of Graphs This is not an exhaustive list of terms, but it is the terms that we may end up using today.

Graph Terms

Circle: When you start at Node(x), follow the links, and end back at Node(x).
Acyclic: A graph that contains no cycles connected: When every node has a path to another node.
Directed: When there is a direction to the connections. Think Twitter
Undirected: !directed. Weighted: The edges have a weight associated with them. Think Maps.
Dag: Directed, acyclic graph.

Implementation Terms

Node: a point or vertex on the graph.

Edge: the connection betxit two nodes.

The BigO is commonly stated in terms of V and E where V stands for vertices and E stands for edges So O(V * E) means that we will check every vertex, and on every vertex we check every edge

How are graphs represented

Adjacency list: This is a type of list where the indices map to the node. DFS on Adjacency list typescript implementation.
Adjacency matrix: An adjacency matrix is a way of representing a graph as a matrix of booleans (0's and 1's). A finite graph can be represented in the form of a square matrix on a computer. BFS on Adjacency matrix typescript implementation.
Dijkstra shortest path search: Dijkstra's shortest path is an algorithm that finds the shortest paths between nodes in a graph. It produces the shortest path tree with the source node as the root. It is profoundly used in computer networks to generate optimal routes with the aim of minimizing routing costs. Runtime is O(logV(V + E)). Dijkstra implementation.

Maps & LRU (Least Recently Used)

A Map is a type of fast key lookup data structure that offers a flexible means of indexing into its individual elements.

Terms

load factor: The amount of data points vs the amount of storage (data.len / storage.capacity)
key: a value that is hashable and is used to look up data. The hash has to be consistent.
Value: a value that is associated with a key collision: when 2 keys map to the same cell.

LRU

The Least Recently Used (LRU) Cache mechanism, allowing you to quickly identify which item hasn't been used for the longest amount of time. An LRU cache is a combination of map and linked list data structures. This algorithm makes use of double linked list & Hash maps. LRU cache typescript implementation.

Thanks for reading my note, if you find this note valuable you can give me a follow on twitter @the_nuelgeek and subscribe to email list on hashnode Geeks Oasis
You can also make a pull request or contact me, if you have any extra data structure / Alogrithm you want to add.
Contact me for your smart contract development project and smart contract auditng. Next new skill Frontend development.
link to the course i took here
Feedbacks are highly welcomed.
Photo credit to Antlii

The Last Data Structure and Algorithm Summary You will Need

My short note to data structure.

Table of contents