Thread by @Vinaystwt

Do you often forget the basics of a Data structure or algorithm?

No Again!!

Data Structure and Algorithms Cheatsheet

A MEGA Thread🧵

Data Structure and Algorithms are the basics of your Programming Journey.

You are making Websites or apps or some Complex Machine learning Model, you still need knowledge Data Structure and Algorithms

Given Thread takes you from the basic Data structure to advance algorithms

1. Array: An array is a collection of items stored at contiguous memory locations.

The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value

2. Linked List: A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations.

The elements in a linked list are linked using pointers as shown in the below image:

3. Stack: Stack is a linear data structure that follows a particular order in which the operations are performed.

The order may be LIFO(Last In First Out) or FILO(First In Last Out).

4. Queue: A Queue is a linear structure that follows a particular order in which the operations are performed.

The order is First In First Out (FIFO).

5. Tree: A tree is a hierarchical data structure defined as a collection of nodes. Nodes represent value and nodes are connected by edges.

The tree has one node called root. The tree originates from this, and hence it does not have any parent.

6. Heap: A heap is a special Tree-based data structure in which the tree is a complete binary tree.

Generally, Heaps can be of two types: Max-Heap and Min-Heap

7. Priority Queue: A priority queue is an abstract data type that behaves similarly to the normal queue except that each element has some priority, i.e., the element with the highest priority would come first in a priority queue.

Removing Highest Priority Element👇

8. Huffman Tree: Huffman coding provides codes to characters such that the length of the code depends on the relative frequency or weight of the corresponding character.

Huffman codes are of variable length, and without any prefix (that means no code is a prefix of any other).

9. Union Find: Union–find is a data structure that stores a collection of disjoint sets.

Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets and finding a representative member of a set.

10. Trie is an efficient information retrieval data structure. Using Trie, search complexities can be brought to optimal limit (key length).

11. Hash Table: Hash Table is a data structure that stores data in an associative manner.

In a hash table, data is stored in an array format, where each data value has its own unique index value.

Access to data becomes very fast if we know the index of the desired data.

12. TreeMap: TreeMap class is like HashMap. TreeMap stores key-value pairs. The main difference is TreeMap sorts the key in ascending order.

TreeMap is sorted as the ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

13. Segment Tree: A Segment Tree is a data structure that allows answering range queries over an array effectively, while still being flexible enough to allow modifying the array.

14. Binary Indexed Tree: Binary Indexed Tree also called Fenwick Tree provides a way to represent an array of numbers in an array, allowing prefix sums to be calculated efficiently.

15. Suffix Array: A suffix array is a sorted array of all suffixes of a given string. The definition is similar to Suffix Tree which is a compressed trie of all suffixes of the given text.

16. Sparse Table: Sparse Table is a data structure, that allows answering range queries.

It can answer most range queries in O(logn), but its true power is answering range minimum queries. For those queries it can compute the answer in O(1) time.

17. Range Tree: A range tree is defined as an ordered tree data structure to hold a list of points.

It permits all points within a given range to be efficiently retrieved and is typically implemented in two or higher dimensions.

18. Suffix Automation: A suffix automaton is a powerful data structure that allows solving many string-related problems.

19. Suffix Tree: A Suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values.

20. Heavy-Light Decomposition: Heavy-light decomposition is a fairly general technique that allows us to effectively solve many problems that come down to queries on a tree.

21. Treap: Treap is a data structure that combines binary tree and binary heap (hence the name: tree + heap ⇒ Treap).
More specifically, treap is a data structure that stores pairs (X, Y) in a binary tree in such a way that it is a binary search tree by X and a binary heap by Y

22. Aho-Corasick: The Aho-Corasick algorithm constructs a data structure similar to a trie with some additional links, and then constructs a finite state machine (automaton) in O(mk) time, where k is the size of the used alphabet.

23. K-d tree: A K-D Tree(also called as K-Dimensional Tree) is a binary search tree where data in each node is a K-Dimensional point in space.

24. Splay Tree: A splay tree is a binary search tree with the additional property that recently accessed elements are quick to access again.

Like self-balancing binary search trees, it performs basic operations such as insertion, look-up and removal in O(log n) amortized time.

25. Palindromic Tree: Palindromic Tree’s actual structure is close to the directed graph. It is actually a merged structure of two Trees that share some common nodes

26. Ropes: A Rope is a binary tree structure where each node except the leaf nodes, contains the number of characters present to the left of that node.

27. Dancing Links: Dancing links is a technique for reverting the operation of deleting a node from a circular doubly linked list.

28. Radix Tree: Radix tree is a data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent.

29. Dynamic Suffix Array: Dynamic suffix array is a suffix data structure that reflects various patterns in a mutable string.

Dynamic suffix array is rather convenient for performing substring search queries over database indexes that are frequently modified.

30. Big O Notation: Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.

31. Recurrence Basics: A recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs.

32. Divide & Conquer: A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.

33. Time Complexity fxn. : Time complexity is the amount of time taken by an algorithm to run, as a function of the length of the input.

34. Linear Search Algorithm: Linear search is a simple search algorithm in which a sequential search is made over all items one by one.

Every item is checked & if a match is found then that particular item is returned, otherwise the search continues till the end of the data

35. Binary Search: Binary search is an efficient algorithm for finding an item from a sorted list of items.

It works by repeatedly dividing in half the portion of the list that could contain the item until you've narrowed down the possible locations to just one.

36. Jump Search: In Jump Search, the sorted array of data is split into subsets of elements called blocks.

We find the search key (input value) by comparing the search candidate in each block. As the array is sorted, the search candidate is the highest value of a block.

37. Graph: A Graph is a non-linear data structure consisting of nodes and edges.

The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.

38. Directed Graph: A directed graph is a graph, i.e., a set of objects (called vertices or nodes) that are connected together, where all the edges are directed from one vertex to another.

A directed graph is sometimes called a digraph or a directed network.

39. Depth-first Search: DFS algorithm is for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

40. Breadth-First Search: BFS is a graph traversal algorithm that starts traversing the graph from the root node and explore all the neighbouring nodes.

Then, it selects the nearest node and explores all the unexplored nodes.

41. Weighted Graph: A weighted graph is a graph in which each branch is given a numerical weight

42. Floyd-Warshall Algo: The Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem.

The problem is to find the shortest distances between every pair of vertices in a given edge-weighted directed Graph.

43. Topological Sort: Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering.

Topological Sorting for a graph is not possible if the graph is not a DAG.

44. Spanning Tree: A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges.

Hence, a spanning tree does not have cycles and it cannot be disconnected.

45. Prim's Algo: Prim's Algorithm is used to find the minimum spanning tree from a graph.

Prim's algorithm finds the subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized.

46. Kruskal's Algo: Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph.

The main target of the algorithm is to find the subset of edges by using which, we can traverse every vertex of the graph.

47. String: Strings are defined as an array of characters. The difference between a character array and a string is the string is terminated with a special character ‘\0’.

48. Hamming Distance: Hamming distance is a metric for comparing two binary data strings. While comparing two binary strings of equal length,

Hamming distance is the number of bit positions in which the two bits are different

49. String Hashing: String hashing is the way to convert a string into an integer known as a hash of that string.

An ideal hashing is the one in which there are minimum chances of collision (i.e 2 different strings having the same hash).

50. Rabin-Karp Algo: Rabin-Karp algorithm is an algorithm used for searching/matching patterns in the text using a hash function.

51. Insertion Sort: Insertion sort is the simple sorting algorithm which is commonly used in the daily lives while ordering a deck of cards.

In this algorithm, we insert each element onto its proper place in the sorted array.

52. Merger Sort: Merge sort is one of the most efficient sorting algorithms. It work on the principle of Divide and Conquer.
Merge sort repeatedly breaks down a list into sublists until all sublist consists of a single element and merging those sublists in a manner give result

53. Bubble Sort: Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

54. Counting Sort: Counting sort is a sorting algorithm that sorts the elements of an array by counting the number of occurrences of each unique element in the array.

55. Quick Sort: Quick Sort is one of the most efficient sorting algorithms and is based on the splitting of an array (partition) into smaller ones and swapping (exchange) based on the comparison with 'pivot' element selected.

56. Selection Sort: Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end.

57. Dynamic Programming: Dynamic Programming is mainly an optimization over plain recursion.

Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming.

58. Edit Distance: Minimum Edit distance between two strings str1 and str2 is defined as the minimum number of insert/delete/substitute operations required to transform str1 into str2.

59. Binary Heap: A binary heap is a data structure, which looks similar to a complete binary tree.

60. Binary Search Tree: Binary Search tree can be defined as a class of binary trees, in which the nodes are arranged in a specific order. This is also called ordered binary tree.

61. Tree Traversals: tree traversal means traversing or visiting each node of a tree.

Linear data structures like Stack, Queue, linked list have only one way for traversing, whereas the tree has various ways to traverse or visit each node.

If you want to more about Data Structure and Algorithms, you can Check following Sites:

geeksforgeeks.org

programiz.com/dsa

If you want to learn more about Algorithms used in competitive Programming, you can checkout all at here: cp-algorithms.com

If you want to learn about Algorithms from book then checkout this free handbook with hints and tricks around Algorithms:
goalkicker.com/AlgorithmsBook…

Thank you for Reading

I'm Vinay👋
A flutter Developer sharing my flutter knowledge and Some Developer Resource you never know

If you enjoyed Reading this Thread
-Press that like button,
-Retweet the first Tweet,
-Follow me @Vinaystwt for more such content

If you like this, please Retweet the first tweet below, it motivates me to create more such content