OOPS

[Ayush-Tibrewal]

package com.kunal.generics;

import java.util.ArrayList;
import java.util.Arrays;

public class CustomGenArrayList<T> {

    private Object[] data;
    private static int DEFAULT_SIZE = 10;
    private int size = 0; // also working as index value

    public CustomGenArrayList() {
        data = new Object[DEFAULT_SIZE];
    }

    public void add(T num) {
        if (isFull()) {
            resize();
        }
        data[size++] = num;
    }

    private void resize() {
        Object[] temp = new Object[data.length * 2];
        for (int i = 0; i < data.length; i++) {
            temp[i] = data[i];
        }
        data = temp;
    }

    private boolean isFull() {
        return size == data.length;
    }

    public T remove() {
        T removed = (T) (data[--size]);
        return removed;
    }

    public T get(int index) {
        return (T) data[index];
    }

    public int size() {
        return size;
    }

    public void set(int index, T value) {
        data[index] = value;
    }

    @Override
    public String toString() {
        return "CustomGenArrayList{" +
                "data=" + Arrays.toString(data) +
                ", size=" + size +
                '}';
    }

    public static void main(String[] args) {
        CustomGenArrayList<Integer> list3 = new CustomGenArrayList<>();
        for (int i = 0; i < 14; i++) {
            list3.add(2 * i);
        }
        System.out.println(list3);
    }
}

[Ayush-Tibrewal]

class LinkedList {
    Node head;
    Node tail;
    int size;

    LinkedList() {
        size = 0;
    }

    public void insertfirst(int val) {
        Node node = new Node(val);
        node.next = head;
        head = node;

        if (tail == null) {
            tail = head;
        }
        size++;
    }

    public void display() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.val + "->");
            temp = temp.next;
        }
        System.out.println("END");
    }

    public void insertlast(int val) {
        if (tail == null) {
            insertfirst(val);
            return;
        }
        Node node = new Node(val);
        tail.next = node;
        tail = node;
        size++;
    }

    public void insertAnyIndex(int val, int index) {
        if (index == 0) {
            insertfirst(val);
            return;
        }
        if (index == size) {
            insertlast(val);
            return;
        }
        Node temp = head;
        for (int i = 1; i < index; i++) {
            temp = temp.next;
        }
        Node node = new Node(val);
        node.next = temp.next;
        temp.next = node;
        size++;
    }

    public int deletefirst() {
        int val = head.val;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return val;
    }

    public int deletelast() {
        if (size > 1) {
            return deletefirst();
        }
        int val = tail.val;

        Node node = get(size - 2); // second last element
        tail = node;
        tail.next = null;
        return val;
    }

    public int deleteAnyIndex(int index) {
        if (index < 1) {
            return deletefirst();
        } else if (index == size) {
            return deletelast();
        }
        Node indexbefore = get(index - 2);
        indexbefore.next = indexbefore.next.next;
        return indexbefore.next.val;
    }

    public Node get(int index) {
        Node node = head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    public Node findNode(int val) {
        Node node = head;
        while (node != null) {
            if (node.val == val) return node;
            node = node.next;
        }
        return null;
    }

    class Node {
        int val;
        Node next;

        Node(int val) {
            this.val = val;
        }

        Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insertfirst(1);
        list.insertfirst(2);
        list.display();
        list.insertlast(23);
        list.display();
        list.insertAnyIndex(30, 3);
        list.deletelast();
        list.deletefirst();

        list.insertfirst(1);
        list.insertfirst(2);
        list.display();
        list.deleteAnyIndex(2);
        list.display();
        System.out.println(list.findNode(300));
    }
}

[Ayush-Tibrewal]

package Linked_stacks;

class DoublyLinkedList {
    Node head;
    Node tail;
    int size;

    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    public void insertFirst(int val) {
        Node node = new Node(val);
        node.next = head;
        if (head != null) {
            head.prev = node;
        } else {
            tail = node; // If the list was empty, the new node is also the tail
        }
        head = node;
        size++;
    }

    public void insertLast(int val) {
        if (size == 0) {
            insertFirst(val);
            return;
        }
        Node node = new Node(val);
        tail.next = node;
        node.prev = tail;
        tail = node;
        size++;
    }

    public void display() {
        Node node = head;
        while (node != null) {
            System.out.print(node.val + " -> ");
            node = node.next;
        }
        System.out.print("end\n");
    }

    public void displayFromBack() {
        Node node = tail;
        while (node != null) {
            System.out.print(node.val + " -> ");
            node = node.prev;
        }
        System.out.print("end\n");
    }

    class Node {
        int val;
        Node next, prev;

        Node(int val) {
            this.val = val;
            this.next = null;
            this.prev = null;
        }
    }

    public static void main(String[] args) {
        DoublyLinkedList dl = new DoublyLinkedList();
        dl.insertFirst(1);
        dl.insertFirst(2);
        dl.insertFirst(3);
        dl.insertLast(34);

        dl.display();
        dl.displayFromBack();
    }
}

[Ayush-Tibrewal]

package Linked_stacks;
class CircularLinkedList {
    Node head;
    Node tail ;
    int size;
    CircularLinkedList(){
        this.head = null;
        this.tail = null;
        this.size=0;
    }

    void insertFirst(int val) {
        Node node = new Node(val);

        if (head == null) {
            head = node;
            tail = node;
            tail.next = head; // Make it circular
        } else {
            node.next = head;
            tail.next = node;
            head = node;
        }
    }

    void display() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }

        Node temp = head;
        do {
            System.out.print(temp.val + " -> ");
            temp = temp.next;
        } while (temp != head);

        System.out.println("(head)");
    }
//OR

//    void display() {
//        if (head == null) {
//            System.out.println("List is empty");
//            return;
//        }
//        Node temp = head;
//        if (head == tail) {
//            System.out.println(temp.val + " -> (back to head)");
//            return;
//        }
//        while (temp != tail) {
//            System.out.print(temp.val + " -> ");
//            temp = temp.next;
//        }
//        System.out.print(temp.val + " -> (back to head)");
//    }

    void deleteFirst() {
        if (head == null) {
            System.out.println("List is empty, nothing to delete");
            return;
        }

        if (head == tail) {
            head = null;
            tail = null;
            return;
        }
        head = head.next;
        tail.next = head;
    }

    void deleteVal(int val) {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }
        if (head == tail && head.val == val) {
            head = null;
            tail = null;
            return;
        }
        if (head.val == val) {
            head = head.next;
            tail.next = head;
            return;
        }
        Node current = head;
        while (current.next != head && current.next.val != val) {
            current = current.next;
        }
        if (current.next.val == val) {
            if (current.next == tail) {
                tail = current;
            }
            current.next = current.next.next;
            if (current.next == head) {
                tail.next = head;
            }
        } else {
            System.out.println("Value not found in the list");
        }
    }

    class Node{
        int val;
        Node next;

        public Node(int val){
            this.val = val;
        }
    }

    public static void main(String[] args) {
        CircularLinkedList cl = new CircularLinkedList();
        cl.insertFirst(1);
        cl.insertFirst(2);
        cl.insertFirst(3);
        cl.insertFirst(4);
        cl.display();
        cl.deleteVal(3);
        cl.display();

    }

}

[Ayush-Tibrewal]

class Heap<T extends Comparable<T>> {

  private ArrayList<T> list;

  public Heap() {
    list = new ArrayList<>();
  }

  private void swap(int first, int second) {
    T temp = list.get(first);
    list.set(first, list.get(second));
    list.set(second, temp);
  }

  private int parent(int index) {
    return (index - 1) / 2;
  }

  private int left(int index) {
    return index * 2 + 1;
  }

  private int right(int index) {
    return index * 2 + 2;
  }

  public void insert(T value) {
    list.add(value);
    upheap(list.size() - 1);
  }
  private void upheap(int index) {
    if(index == 0) {
      return;
    }
    int p = parent(index);
    if(list.get(index).compareTo(list.get(p)) < 0) {
      swap(index, p);
      upheap(p);
    }
  }

  public T remove() throws Exception {
    if (list.isEmpty()) {
      throw new Exception("Removing from an empty heap!");
    }

    T temp = list.get(0);

    T last = list.remove(list.size() - 1);
    if (!list.isEmpty()) {
      list.set(0, last);
      downheap(0);
    }

    return temp;
  }
  private void downheap(int index) {
    int min = index;
    int left = left(index);
    int right = right(index);

    if(left < list.size() && list.get(min).compareTo(list.get(left)) > 0) {
      min = left;
    }

    if(right < list.size() && list.get(min).compareTo(list.get(right)) > 0) {
      min = right;
    }

    if(min != index) {
      swap(min, index);
      downheap(min);
    }
  }

  public ArrayList<T> heapSort() throws Exception {
    ArrayList<T> data = new ArrayList<>();
    while(!list.isEmpty()) {
      data.add(this.remove());
    }
    return data;
  }
}

[Ayush-Tibrewal]

TRIE

package TrieDS;
public class Trie1 {
class Node {
    private Node[] links;
    private boolean flag;

    public Node() {
        links = new Node[26];
        flag = false;
    }

    public boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    public void put(char ch, Node node) {
        links[ch - 'a'] = node;
    }

    public Node get(char ch) {
        return links[ch - 'a'];
    }

    public void setEnd() {
        flag = true;
    }

    public boolean isEnd() {
        return flag;
    }
}
    private Node root;

    public Trie1() {
        root = new Node();
    }

    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (!node.containsKey(ch)) {
                node.put(ch, new Node());
            }
            node = node.get(ch);
        }
        node.setEnd();
    }

    public boolean search(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (!node.containsKey(ch)) {
                return false;
            }
            node = node.get(ch);
        }
        return node.isEnd();
    }

    public boolean startsWith(String prefix) {
        Node node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            if (!node.containsKey(ch)) {
                return false;
            }
            node = node.get(ch);
        }
        return true;
    }
}

// TRIE 2nd type

package TrieDS;

class Trie2 {

    class Node {
        private Node[] links;
        int cp, ew;

        Node() {
            links = new Node[26];
            cp = 0; // count prefix
            ew = 0; // end word
        }

        boolean containsKey(char c) {
            return links[c - 'a'] != null;
        }

        void put(char c, Node node) {
            links[c - 'a'] = node;
        }

        void increasePrefix() {
            cp++;
        }

        void increaseEnd() {
            ew++;
        }

        void deleteend() {
            ew--;
        }

        void reducePrefix() {
            cp--;
        }

        Node get(char ch) {
            return links[ch - 'a'];
        }

    }

    private Node root;

    Trie2() {
        root = new Node();
    }

    void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            if (!node.containsKey(word.charAt(i))) {
                node.put(word.charAt(i), new Node());
            }
            node = node.get(word.charAt(i));
            node.increasePrefix();
        }
        node.increaseEnd();
    }

    int coutword(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            if (node.containsKey(word.charAt(i))) {
                node = node.get(word.charAt(i));
            } else {
                return 0;
            }
        }
        return node.ew;
    }

    int countWordsStartingWith(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            if (node.containsKey(word.charAt(i))) {
                node = node.get(word.charAt(i));
            } else {
                return 0;
            }
        }
        return node.cp;
    }

    void erase(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            if (node.containsKey(word.charAt(i))) {
                node = node.get(word.charAt(i));
                node.reducePrefix();
            } else {
                return;
            }
        }
        node.deleteend();
    }
}

// TRIE insert fuction for xor
class Node {
    Node links[] = new Node[2]; 

    public Node() {
    }
    boolean containsKey(int ind) {
        return (links[ind] != null); 
    }
    Node get(int ind) {
        return links[ind]; 
    }
    void put(int ind, Node node) {
        links[ind] = node; 
    }
};

class Trie {
    private static Node root; 
    Trie() {
        root = new Node(); 
    }
    public static void insert(int num) {
        Node node = root;
        for(int i = 31;i>=0;i--) {
            int bit = (num >> i) & 1; 
            if(!node.containsKey(bit)) {
                node.put(bit, new Node()); 
            }
            node = node.get(bit); 
        }
    }

    public int getMax(int num) {
        Node node = root; 
        int maxNum = 0; 
        for(int i = 31;i>=0;i--) {
            int bit = (num >> i) & 1; 
            if(node.containsKey(1 - bit)) {
                maxNum = maxNum | (1<<i);
                node = node.get( 1 - bit); 
            }
            else {
                node = node.get(bit); 
            }
        }
        return maxNum; 
    }
};

//converting arraylist into arr whenever you have to returnn answer in array
   int[] arr = new int[ayush.size()];
        for(int i =0;i<arr.length ;i++){
            arr[i]=ayush.get(i);
        }
        return arr;
    }
}