DSA.h

Go to the documentation of this file.

 
#include <bits/stdc++.h>
 
#define ll long long int
 
#define vi vector<int>
 
#define vll vector<ll>
using namespace std;
 
/* ------------------------------- Data Structures ---------------------------------- */
 
// ------------------------------- Singly Linked List -----------------------------
 
class SinglyLinkedListNode {
 
    public:
 
        ll data;
 
        SinglyLinkedListNode* next;
 
        SinglyLinkedListNode();
 
        SinglyLinkedListNode(ll val);
 
};
 
ostream& operator<<(ostream &out, const SinglyLinkedListNode &node);
 
class SinglyLinkedList {
 
    public:
 
        SinglyLinkedListNode *head;
 
        SinglyLinkedListNode *tail;
 
        SinglyLinkedList();
 
        void insert(ll data);
 
        SinglyLinkedListNode* find(ll data);
 
        bool deleteVal(ll data);
 
        void printer(string sep);
 
        void reverse();
 
};
 
SinglyLinkedList merge(SinglyLinkedList list1, SinglyLinkedList list2);
 
// ------------------------------- Doubly Linked List -----------------------------
 
class DoublyLinkedListNode {
 
    public:
 
        ll data;
 
        DoublyLinkedListNode *next;
 
        DoublyLinkedListNode *prev;
 
        DoublyLinkedListNode();
 
        DoublyLinkedListNode(ll val);
 
};
 
ostream& operator<<(ostream &out, const DoublyLinkedListNode &node);
 
class DoublyLinkedList {
 
    public:
 
        DoublyLinkedListNode *head;
 
        DoublyLinkedListNode *tail;
 
        DoublyLinkedList();
 
        void insert(ll data);
 
        void printer(string sep);
 
        void reverse();
 
};
 
// ------------------------------- Binary Search Tree -----------------------------
 
class BSTNode {
 
    public:
 
        ll info;
        
        ll level;
 
        BSTNode *left;
        
        BSTNode *right;
 
        BSTNode (ll val);
 
};
 
ostream& operator<<(ostream &out, const BSTNode &node);
 
class BinarySearchTree {
 
    public:
 
        BSTNode *root;
 
        enum order {PRE, IN, POST};
 
        BinarySearchTree();
 
        void insert(ll val);
        
        void traverse(BSTNode* T, order tt);
 
        ll height(BSTNode *T);
 
};
 
// ------------------------------- Suffix Trie -----------------------------
 
class Trie {
 
    public:
 
        ll count;
 
        map<char,Trie*> nodes;
 
        Trie();
 
        bool find(Trie* T, char c);
 
        void insert(string s);
 
        bool checkPrefix(string s);
 
        ll countPrefix(string s);
 
};
 
// ------------------------------- Heap -----------------------------
 
void swap(int &x, int &y);
 
class Heap {
    int* H;
    int maxSize;
    int n;
    
    public:
 
        Heap(int capacity);
 
        int parent(int i);
 
        int left(int i);
 
        int right(int i);
 
        void insert(int e);
 
        int min();
 
        void Heapify(int root);
 
        void deleteMin();
 
};