Data Structures - amitbhilagude/userfullinks GitHub Wiki

1. Time complexity
	○ Time complexity:
		§ Amount of time take to run an algorithm
	○ O(1) - Constant TIme
		§ Best time complexity, same time with no matter how long or short list
	○ O(n)-  Linear Time
		§ N is size of data working on
		§ Usually apply for for-each
		§ Linear search
	○ O(log n) - Algorithimic time
		§ Better than O(n)
		§ e.g. find square root of 16.  2^4
		§ How many time to multiply 2 to get 16 which O(log n)
		§ Binary search time complexity
	○ O(n2) - Quadratic time
		§ Worst performance
		§ Usually happened for nested for each loop
	○ O(2^n) -Exponential
		§ Recursive calls
	○ https://adrianmejia.com/most-popular-algorithms-time-complexity-every-programmer-should-know-free-online-tutorial-course/
2. Space Complexity
	a. Space complexity
		i. Memory consumed during algorithm run
	b. o(1) - Constant Space
		i. Fixed number of Variables
	c. o(n) - Linear space
		i. Array size is depends on n
	
3. LinkedIn List
	a. Types
		i. Single linked list
		ii. Doubly LinkedIn list
	b. Main Concepts
		i. First Node Reference
		ii. Tail Node reference
	c. Scenarios for Programming
		i. Empty check
		ii. Only one node
		iii. Two Nodes
		iv. Is it tail node
	d. C#.net Linked List Class
		i. https://www.geeksforgeeks.org/c-sharp-linkedlist-class/

4. Stack
	a. Implementations Options
		i. using Linked list
			1) Recommended for object but not for int value 
			2) Setting null in .net will deallocate memovry
		ii. Using Array 
			1) Create fixed size
			2) Option to copy array functionality. (Initialise and copy)
	b.   Postfix calculator using stack
	c.  Undo functionality using Stack 
	d. C#.net Stack class
		i. https://www.geeksforgeeks.org/c-sharp-stack-class/
                    ii. https://www.geeksforgeeks.org/linked-list-set-2-inserting-a-node/
5. Queue
	a. C#.net class
		i. https://www.geeksforgeeks.org/c-sharp-queue-with-examples/
6. Binary Search Tree (BST)
	a. 0-2 Nodes and Left child node smaller than root and Right child node greater than root
	b. Search Option
		i. Pre
		ii. In
		iii. Post
	c. Delete scenarios
		i. No node
		ii. Left child has only one node
		iii. Right child has right node only
	d. Sorting 
		i. Sorting binary search tree
		ii. Sorting Word
7. Array
	§ Need to define size and allocate memory
	§ Dynamic array: ArrayList in c# and Vector in C++ and Java
	§ Array passed as argument always points for first element and treat as pointer. It is size is first element

8. String
	a. C#.net class
		i. https://www.geeksforgeeks.org/c-sharp-string/
9. Hash tables
	a. Key-value pairs
	b. Stores any data type
	c. C#.net class (HashTable)
		i. https://www.geeksforgeeks.org/c-sharp-hashtable-with-examples/
10. Dictionary
	a. Key-value pairs
	b. Stores same data type
	c. C#.net class
11. Heap
	a. Tree Data Structure: complete binary tree
		i. https://www.geeksforgeeks.org/heap-data-structure/
	b. Min Heap
	c. Max Heap
12. Graphs
https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/