Posts

Showing posts from January, 2020

Tree Terminologies

Image
Root: Node with no parent / topmost node Edge: Link from parent to the child node Leaf: Node with no children Sibling: Children of the same parent Ancestor: Parent, grandparents, great grandparents and so on of a node Depth of node: Length of the path from the root to the node . Height of node:  Length of the path from the node to the deepest node Height of tree: Same as the height of the root node Depth of tree: Same as the depth of the root node, which is always 0  Predecessor:  Immediate previous node in Inorder traversal of the tree Successor:  Immediate next node in Inorder traversal of the tree

Linear Queue Linked List Implementation - All Operations

Image
  // Linked list node to maintain the queue class Node{     int data;     Node next;       // Cretaion of a queue node     // Time Complexity - O(1) , Space Complexity - O(1)     Node(int x){         this.data = x;         this.next = null;     } } public class Main {       // head and tail of the linked list     Node head;     Node tail;       // function to enqueue an element 'x' to the end of queue     // Time Complexity - O(1) , Space Complexity - O(1)     public void enQueue(int x){         // create a new linked list node         Node newNode = new Node(x);               // if linked list / queue is empty         if(head==null){             head=newN...

Circular Queue Implementation using Arrays - All Operations

Image
  Algorithm : Enqueue: Check if the queue is full. If the queue is full, throw an error else : Fixing the position of endOFQueue: Check if endOFQueue has reached the last cell of the array if yes, then make endOFQueue=0 , as the queue is not full and it has space left towards the start of the array if no, then just simply increment endOFQueue by 1, as the queue is not full and it has space left towards the end of the array Once the position of endOFQueue is fixed by above, we simply put the data in the array at endOFQueue using arr[endOFQueue] Dequeue: Check is the queue is empty. If the queue is empty, throw an error else: Remove the element from start of queue i.e. arr[startOFQueue] Fix the new Postion of startOFQueue: Check if there was only one element in queue, using if(startOFQueue==endOFQueue) if yes, just simply set startOFQueue=endOFQueue=-1 if no, i.e. there are more than 1 element in queue, check the current position of start: if st...

Linear Queue Implementation using Array - All Operations

Image
  public class Main {     // Array to implement Linear queue     int[] arr;     // variables to maintain indexes of start and end of queue     int startOFQueue;     int endOfQueue;       // constructor     // Creating a queue - Time Complexity - O(1), Space Complexity - O(n) , where n = size     Main(int size){         this.arr=new int[size];         this.startOFQueue=0;         this.endOfQueue=-1;     }       // function to initialize the queue array      //Time Complexity - O(n), Space Complexity - O(1)     public void initializeArray(){         if(this.startOFQueue==0 && this.endOfQueue==-1){             for(int i=0; i<arr.length; i++){                 this.arr[i...

Queue - Introduction

Image
Follows First In First Out (FIFO) Implementation Options of queue : Arrays Linear queue Circular queue Linked List Linear queue (only, and not Circular queue) Why we need circular queue ?         Because in the array implementation of linear queue, when we perform deque operation, it causes few blank cells in linear queue (at the start of queue). Due to this, we waste a lot of space. Also, we do not want to shift the elements in the array to left (or start) so as to prevent empty cells at start as it will take O(n) time. We have to do it in O(1) time. For doing that we can again add new elements to the start and at the same time maintaining two pointers i.e. startOfQueue and endOfQueue. (See actual code implementation of circular queue using arrays) When to use queue / Advantages of queue ? 1. When we want to access data in FIFO order. 2. Data is not easily corrupted as the insertion and deletion of the elements in queue is done in ...

Stack Implementation using Linked List

Image
  // the node of linked list used to implement stack class Node{     int data;     Node next;     Node(int x){         this.data=x;         this.next=null;     } } public class Main {     Node head;       // Function to push an element into stack     // Time Complexity - O(1) , Space Complexity - O(1)     public void push(int data){         Node newNode = new Node(data);               // if linked list is empty         if(head==null){             head=newNode;             return;         }               // else if linked list is not empty, we will add a new node to the start of linked list         newNode.next=head;  ...

Stack implementation and all operations on stack using Array

Image
  Example of stack implementation - back button of the browser _____________________________________ public class Main {     // The Array used to implement stack     int[] arr;     // topOfStack is used to maintain the index of the topmost element present in stack. If not present then it will store -1     int topOfStack;       // constructor     Main(int size){         this.arr = new int[size];         this.topOfStack=-1;     }       // used to initialize the array for stack     // Time Complexity - O(n), Space Complexity - O(n)     public void initializeArray(){         if(topOfStack==-1){             for(int i=0;i<this.arr.length;i++){                 this.arr[i]=Integer.MIN_VALUE;         ...

Deletion of entire Double linked list

Image
Simply, head = null; tail = null; will not work in case of Double Linked List. The reason for this is that, we have a previous node too, which will point to the previous node even if we make head=tail=null. So, the solution for this is that, we loop through the linked list and make all the prev=null (for each node.). Now, after this if we do head=tail=null, the entire linked list is deleted. Note : The nodes in any linked list is deleted one by one and not vanished all at once by garbage collection.

Circular Double Linked List - All Operations

Image
  // The Double linked list node / circular double linked list node class Node{     int data;     Node next;     Node prev;     Node(int x){         this.data=x;         this.prev=null;         this.next=null;     } } public class Main {     // head and tail references of circular double linked list     Node head;     Node tail;       // function to add a node to the last of circular double linked list // Time Complexity - O(1) , Space Complexity - O(1)     public void addNode(int x){         // create a new node         Node newNode = new Node(x);               // if linked list is empty         if(head==null){             head=newNode;         ...

Double Linked List - All Operations

Image
  // The Double linked list node class Node{     int data;     Node next;     Node prev;          Node(int x){         this.data=x;         this.next=null;         this.prev=null;     } } public class Main {          // the head and tail of the linked list     Node head;     Node tail;          // function to add a new node to the last of linked list // Time Complexity - O(1), Space Complexity - O(1)     public void addNode(int x){         Node newNode = new Node(x);         // if linked list is empty         if(head==null){             head=newNode;             tail=newNode;       ...

Circular Single Linked List - All operations

Image
  // the linked list node class Node{     int data;     Node next;     Node(int x){         this.data=x;         this.next=null;     } } public class Main {     // head and tail of the linked list     Node head;     Node tail;   // function to add a new node at last of linked list // Time Complexity - O(1) , Space Complexity - O(1)     public void addNode(int x){         Node newNode = new Node(x);               if(head==null){             head=newNode;             tail=newNode;             tail.next=head;             return;         }         // else         tail.next=newNode;     ...