Skip to content

Data Structure & Algorithms

Jump to bottom
Sandesh Kota edited this page Jun 4, 2019 · 36 revisions

Data Structure

  • Node (value | next-pointer)
  • Node Chains (two/more nodes connecting with help of next-pointers)
public class Node
{
  public int Value { get; set; }
  public Node Next { get; set; }
}

Node first = new Node { Value = 3 };
Node middle = new Node { Value = 5 };
first.Next = middle;
Node last = new Node { Value = 9 };
middle.Next = last;

Linked List

  • Single chain of nodes
  • Head Pointer
  • Tail Pointer
  • Operations: Add, Remove, Find, Enumerate
    • If there is only one item in the list, then both head and tail pointers will point to single node
    • Adding: Will update the head/tail pointer and the corresponding next-pointer (in case of array there will be performance impacts ex: adding a new value at the beginning will have to shift all the other values by one step)
  • Doubly Linked List: .Net's linked list is Doubly Linked List

Stack (LIFO)

  • Push & Pop
  • Linked List Implementation of stack
    • Pros: No hard size limit. No bounds check (as in case of array)
    • Cons: memory allocation push, per node memory overhead, performance issues
  • Array Implementation of stack
  • Always best to use the Stack that comes in the framework ( C# Stack - stores in array)
  • Stack Usages:
    • Undo operation
    • compiler's syntax check for matching braces is implemented by using stack
    • During Function Calls because it Follows A LIFO Structure
    • Back/Forward stacks on browsers

Queue (FIFO)

Binary Tree

  • A tree structure with only two children
  • Finding an item in Binary Tree
Find(Node current, Data value){
  if(current == null) return null;
  if(current.Value == value) return current;
  if(value < current.Value) return find(current.Left, value);
  return Find(current.Right, value);
}
// starts with Find(RootNode, value)
  • Traversal
    • PreOrder: Process Node -> Visit Left Node -> Visit Right Node (recurring)
    • InOrder: Visit Left Node -> Process Node -> Visit Right Node (recurring) - processed based on sorted order
    • PostOrder: Visit Left -> Visit Right -> Process Node (recurring)
    • Tree traversals (post/pre) - compliers use trees for traversal - consider tree as dependency graph and child should be processed before parent (which is not the case in In-Order)
  • Binary Tree Implemenration
  • Binary Tree in .Net has default Enumerator as In-Order

Hash Table

  • Key/Value, key is hashed
  • Performance: hashing should be efficient since it is involved in all operations get/save.
  • Types if Hashing Ex: Additive, Folding, CRC32, MD5, SHA-2 etc...
  • Linked List Implementation

Algorithms

Sorting

  • Bubble Sort
    • Compare each array item to it's right neighbor
    • If the right neighbor is smaller then swap right and left
    • Repeat for the remaining array items
    • Perform subsequent passes until no swaps are performed
    • Results
    • for sorting "n" values n*n operations are required (worst and Average case) | "n" operations (best case)
    • Space (n) is required. No additional space since it is done on the array(data) provided
  • Insertion Sort
    • Sorts each item in the array as they are encountered
    • Current item works from left to right. Everything left of the item is known to be sorted. Right is unsorted
    • The current item is "inserted" into place within the sorted section
    • Results
    • for sorting "n" values "n*n" (Big-O n square) operations are required (worst and Average case) | "n" operations (best case)
    • Space (n) is required. No additional space since it is done on the array(data) provided
  • Selection Sort
  • Enumerate the array from the first unsorted item to the end (for each run)
  • Identify the smallest item
  • Swap the smallest item with the first unsorted item
  • (foreach) find smallest item in the complete array put it in the first place - repeat (keep filling second, third place)
  • Results - for sorting "n" values "n*n" (Big-O n square) operations are required (worst, average & best case)
    • Typically better than Bubble sort but worse than insertion sort - Space (n) is required. No additional space since it is done on the array(data) provided
  • Merge Sort
    • Array is recursively split in half
    • When the array is in groups of 1, it is reconstructed in sort order
    • Each reconstructed array is merged with the other half
      [3,8,2,1,5,4,6,7] 
  => [3,8,2,1] & [5,4,6,7] 
  => [3,8] & [2,1] & [5,4] & [6,7] 
  => [3] & [8] & [2] & [1] & [5] & [4] & [6] & [7]
  => [3,8] & [1,2] & [4,5] & [6,7] 
  => [1,2,3,8] & [4,5,6,7] 
  => [1,2,3,4,5,6,7,8]
    • Results
    • for sorting "n" values "n log n" (Big-O n log n) operations are required (worst & average) | "n log n" operations (best case)
      • Data splitting means that the algorithm can be made parallel
    • Space (n) is required. No additional space since it is done on the array(data) provided
      • Even though the data is split the no of items in the memory is same
  • Quick Sort
    • Divide and Conquer algorithm, Pick a pivot value & partition the array
    • Put all values before the pivot to the left and above to the right
    • Perform pivot and partition algorithm on the left and right partitions
    • Repeat until sorted
    [3,4,2,1,5,8,6,7]
=> [3,4,2,1,5,8,6,7] (pivot point is 5)
=> [1,2,3,4,5,8,6,7] (pivot point is 2)
=> [1,2,3,4,5,8,6,7] (pivot point is 1)
=> [1,2,3,4,5,8,6,7] (pivot point is 3)
=> [1,2,3,4,5,6,7,8] (pivot point is 7)
  • Results
    • for sorting "n" values "n*n" (Big-O n square) operations are required worst) | "n log n" operations (average & best case)
    • Space (n) is required. As a recursive algorithm the array space as well as the stack space must be considered

Set Collection & Algorithms

AVL Tree

  • Self-balancing Binary Search Tree (works based on the heights)

Sources

Clone this wiki locally