Datastructure’s cheatsheet

4 forms of datastructure

There are 4 popular forms of datastructure

1. Linear datastructure
2. Hashing datastructure
3. Tree datastructure
4. Graph datastructure

1. Linear datastructure’s

Static linear datastructure

• Arrays

Dynamic linear datastructure

1. Linked List
   • Singly(simple) linked list
   • Doubly linked list
   • Circular(ly) linked list
   • Double ended list
   • Sorted list
   • Multilinked list
2. Stack
3. Queue
   • Circular queue
   • Dequeue
   • Priority queue

2. Hashing datastrucure’s (Linear / non-linear datastructure)

Hashing datastructure’s can be used with both linear datastructure and non-linear datastructure’s.

For example:

Hashmap in java used array and each element uses LinkedList / Binary Search Tree. Here LinkedList is the linear datastructure and BST is the non-linear datastructure. So most of the hashing datastructure’s can be used with linear/non-linear datastructures.

3. Tree datastructure’s (Non-linear datastructure)

1. Balanced tree
2. Balanced binary tree
3. Binary tree
   • Complete Binary tree
   • Full Binary tree
   • Perfect Binary tree
   • Extend Binary tree
4. Binary search tree
   • AVL tree
   • Splay tree
   • Tango tree
   • T-tree
5. B-Tree
6. B+ Tree
7. Degenerate tree
8. General tree
9. Heap
10. N-ary tree
11. Red-black tree
12. Skewed tree
13. Treap (Tree + Heap)
14. Trie

4. Graph Datastructure

1. Finite graph
2. Infinite graph
3. Trivial graph
4. Simple graph
5. Multi graph
6. Null graph
7. Complete graph
8. Pseudo graph
9. Regular graph
10. Directed graph
11. Undirected graph
12. Weighted graph
13. Unweighted graph
14. Connected graph
    1. Weekly connected graph
    2. Strongly connected graph
15. Disconnected graph
16. Cyclic graph
17. Acyclic graph
18. Directed acyclic graph
19. Digraph graph
20. Labelled graph
21. Bipartite graph
22. Subgraph
    • Vertex disjoint subgraph
    • Edge disjoint subgraph
23. Dense graph
24. Sparse graph