Data Structure & Algorithms

• 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)

• Enqueue & Dequeue
• [Linked List Implementation of Queue] (https://github.com/ILearny/Standards/blob/master/DataStructure/Queue/LinkedListQueue.cs)
• Array Implementation of Queue
• Priority Queue
  • Same as Queue but an item can be added anywhere based on the priority of the item that is being added

Binary Tree

• A tree structure with only two children

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)

SOURCES

• My Own Github