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

9 comments

Leave a Reply