Binary Tree
Trees A tree consists of Nodes that points to multiple nodes (In this case, binary tree has been consider where each node can point to at max 2 nodes). The Node that points to other Node is called it’s parent and the Node that is being pointed is called it’s child Node. A parent can have multiple child nodes but a child Node can’t have multiple parent Nodes. A child can also be a parent Node to other child Nodes.
Doubly Linked List
A doubly linked list is a type of linked list where each node contains data and references to two other nodes:
One pointer to the previous node in the list. Another pointer to the next node in the list. This allows you to traverse the list in either direction, which is different from a singly linked list that only allows traversal in one direction. #include <iostream> using namespace std; // Creating the Node Class class Node { public: int value; Node *next; Node *prev; Node(int value) { this->value = value; next = nullptr; prev = nullptr; } }; // Creating Double Linked List Class class DoublyLinkedList { private: Node *head; Node *tail; int length; public: // Constructor for the Doubly Linked List DoublyLinkedList(int value) { Node *newNode = new Node(value); head = newNode; tail = newNode; length = 1; } // Destructor for the Doubly Linked List ~DoublyLinkedList() { Node* temp = head; while (head) { head = head->next; delete temp; temp = head; } } // printList will print the Linked List void printList() { Node *temp = head; while (temp !
Graphs
In DSA (Data Structures and Algorithms), a graph is a collection of nodes (also called vertices) connected by edges.
Nodes represent data. Edges represent the relationships between that data. #include <iostream> #include <unordered_map> // Similar to hash table, there are two rows where key-value pair structures are stored. #include <unordered_set> // It's like a array. Here, if same data is pushed into the array, only one instance is created. (Close enough to Hash Table concept) using namespace std; class Graph{ private: unordered_map<string, unordered_set<string> > adjList; // unordered_map< data_type, data_type > map_name; // Here, in this case, key is s string and the value is a unordered_set with string values and this whole map is named adjList public: void printGraph(){ for (auto [vertex, edges] : adjList){ // As per the plan, the structuring is arranged.
Hash Tables
Hash tables are the tables where each piece of data is stored in a given index which is generated when the data is passed through some hash function.
For example: If {”dataset_1”:1000} would value of 4 (from the hash function), it would be stored in the index of 4. {”dataset_2”:2000} might be 8, so it would be stored in the index of 8.
It may happen in cases that data can get same index with hash function, in which case a condition on collision occurs.
Queue
Queue works as FIFO (First In First Out). The value that is added first will be the one that can be access first. Here, Linked List would be used in reverse order. A linked list will have prepend function operation complexity to be O(1) and deleteFirst also to be O(1).
#include <iostream> using namespace std; // Node Class will create a Node class Node{ public: int value; Node* next; Node(int value){ this->value = value; next = nullptr; } }; // Queue Class will develop the Queue class Queue{ private: Node* first; Node* last; int length; public: // Constructor for the Queue Class Queue(int value){ Node* newNode = new Node(value); first = newNode; last = newNode; length = 1; } // printQueue will print the values in the Queue void printQueue(){ Node* temp = first; while(temp){ cout << temp->value << endl; temp = temp->next; } } // getFirst will print the value of the first element in the Queue void getFirst(){ cout << "First: " << first->value << endl; } // getLast will print the value of the last element in the Queue void getLast(){ cout << "Last: " << last->value << endl; } // getLength will print the length of the Queue void getLength(){ cout << "Length: " << length << endl; } // enqueue will add a element to the Queue void enqueue(int value){ Node* newNode = new Node(value); if (length == 0){ first = newNode; last = newNode; } else{ last->next = newNode; last = newNode; } length++; } // dequeue will remove a element from the Queue int dequeue(){ if (length == 0) return INT_MIN; Node* temp = first; int dequeuedValue = first->value; if (length == 1){ first = nullptr; last = nullptr; } else{ first = first->next; } delete temp; length--; return dequeuedValue; } }; // info function will return information about the given Queue void info(Queue* myQueue){ cout << "----------------" << endl << "Printing the Queue" << endl; myQueue->printQueue(); myQueue->getFirst(); myQueue->getLast(); myQueue->getLength(); cout << "----------------" << endl; } int main(){ Queue* myQueue = new Queue(4); info(myQueue); myQueue->enqueue(2); myQueue->enqueue(8); myQueue->enqueue(4); myQueue->enqueue(5); info(myQueue); }
Singly Linked List
Linked Lists and Vectors are different concepts. A Vector has index assigned to it’s elements whereas there are no index in Linked Lists. A Vector has it’s elements stored in memory address consecutively whereas Linked List have it’s elements stored in memory address that are not in any order (arbitrarily assigned). Each element points to the next elements memory address and the last elements points to null value (that means no where).
Stack
The stack will be a vertical Linked List that will have it’s tail at the bottom (the actual tail pointer will not be present) and head at the Top (top pointer will be present instead of head pointer). Prepend like function called push will add a node at the top of the stack and pop function will return the value of the popped node and will delete the node when it will be called.