Data Structure

Data Structure

1. List

   • List a dictionary in modern languages, List use the linked list to store it's value and it always moves the elements to the right before creating a space for new element

2. Linked List

   • Singly
     • data and link of next node just like chain last node next is always null
   • Doubly
     • Data + Previous and Next link information Last node next element is always null
   • Circularly
     • Circularly same as single but last node next element contains first node element link information
   • Josephus Problem

3. Abstract data type ( ADT )

   • The term abstract data type (ADT) refers to the basic mathematical concept that defines the data type
   • 4 implementations of ADT
     • arrays
     • singly
     • Doubly
     • Circularly
   • Stack
     • Collection of elements in linear order LIFO - last in first out
     • push
     • pop
     • isEmpty
     • isFull
     • top
     • array Implementation
       • size limitation in array we push and pop elements at the end the array adding elements on first will take extra resources
     • Linked list
       • 1. no size limitation 2. We can use singly linked list to implement it 3. we will add and delete stack at the top of linked list 4. no need for isFull method 5. if stack is empty then head value will be NULL
     • Array Or List
       • as both supports stack so which one is better in constant time allocating and deallocating memory for list nodes does take more time than preallocated list allocate memory when required whereas array allocate memory in start list head and tail pointer requires more memory
     • use of stack
       • prefix
         • to convert infix to prefix we first have to reverse the expression and then convert to the post fix and reverse the result to get the prefix
       • infix
         • binary operator e.g. + is infix between A+B +, -, *, / always requires to operands
       • postfix
         • parenthesis are not required in postfix https://www.youtube.com/watch?v=vXPL6UavUeA

4. DMAS Rule

   • Division, multiplication, addition and substraction
   • for operator same precedence left to right rule apply A+B+C
   • Exponentiation right to left rule apply

5. Operators

   • Binary Operator +, -, *, /, **
     • exponentiation **
   • uninary operator -1, !

6. Queue

   • enqueue / rear
     • One end is always used to insert data
   • dequeue / front
   • peek / front
     •  Gets the element at the front of the queue without removing it.
   • isfull
     • Checks if the queue is full.
   • isempty
     • Checks if the queue is empty.
   • Implementation
     • linked lists
       • insert works in constant time for either end of a linked list remove works in constant time only best to keep head of the linked list as front and remove from front and insert at the end of list front and rear two pointers are required
     • Array
       • insert at the end of the array delete at the top of the array without shifting, just javascript we will have two pointers front and rear
       • Circular Array
         • insert at the end of the array pop from the start of the array dequeue method int x = array[front] // array[front] = null; front = (front+1) % arraySize;noElements = noElements - 1;return x;enqueue methodrear = (rear+1) % arraySizearray[ rear ] = x;noElements = noElements + 1;
   • Usage
     • Popular is Simulation
       • virtual world, perform actions without creating it like flight simulation
       • Time based simulation
       • Event Based Simulation
   • Priority Queue
     • A queue where the dequeue operation not depends on FIFO is called a priority queue
     • All queue method + remove method

7. Definations

   • process
     • When we run an executable program, it becomes a process in memory
   • Heap
     • Heap is used to allocate dynamic memory
   • Stack
     • stack is used to allocate static memory
   • Queue
     • Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both its ends Queue is a linear structure

8. Tree

   • genealogy - Family tree
   • Binary Tree
     • consists of three disjoint subsets root, left subtree and right subtree
     • root
       • depth count formula log2( n +1 ) -1
     • left sub tree or left desendant
     • right sub tree or right descendent
     • Binary Tree Types, terminolgy
       • strictly Binary
         • if the left and right of leaf node is not null than the tree is strictly binary
       • Complete Binary
         • all leaf nodes are at the same level or depth is called complete binary tree
       • BST - Binary search tree
         • left are small than root and right are greator
         • ordered
         • unordered
       • Traversing
         • Preorder NLR
         • inorder LNR :sorted result
           • we can get sorted result with inorder
         • postorder LRN
         • level order - use queue instead of stack
     • Definations
       • root has level 0
       • maximum level leaf node is the depth of binary tree
       • count binary tree depth in a complete binary tree
         • count no leaf nodes = 2 power d
         • 2 power (d + 1) and - 1
       • a depth of a node is a number of edges from the root node
       • A height of the node is a number of edges from the node to leaf node
         • a depth of binary tree is 1 + the number of edges on longest path lead node
       • A binary tree is useful when two ways decision must be made at each point in a process
       • A binary tree with the property that items in the left subtree are smaller than the root and items are larger or equal in the right subtree is called a binary search tree (BST)
         • Ordered Tree: An Ordered Binary Tree is a form of rooted tree with a specific order. Started from the root element the smaller number is on the left side and the higher number on the right side.
           • unordered tree: An Unordered Binary Tree on the other side has no specific order of the elements.
       • Tree structure by nature is a recusive stucture
         • tail recursion: if you find recusion code at the end of function return functionName() then it's called tail recursion
     • Methods
       • left
       • right
       • parent
       • brother
       • info
       • setLeft(parent node p, info x)
       • setRight()
       • insert
         • find
     • add lesser values in left