Data Structures in C++

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.

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. The last child Node at the end of the tree which further does not point to any Node is called a leaf.

  • A Tree is called Full if all parent Nodes point to 2 child Nodes or does not point to any Node (In case of binary trees).
  • A Tree is called Perfect if all parent Nodes point to 2 child Nodes (In case of binary trees).
  • A Tree is called Complete if the Tree is filled from left to right (In case of binary trees).

Binary Search Tree

The arrangement of the Nodes is as per the values compared to the already existing Node. Just follow a simple rule:

  1. If the value of the Node is greater than the Parent Node, keep it to it’s right.
  2. If the value of the Node is less than the Parent Node, keep it to it’s left.

Operation Complexity of a Binary Search Tree

For a binary search tree, number of elements in a full tree with each levels filled will be (2^n) - 1. For larger values, 1 becomes insignificant. Thus to get to a point, n operations have to be applied which makes the operational complexity equal to O(log base 2 N) where N is the number of Nodes in the binary search tree.

But consider a case where there are all elements attached in increasing order in which case, all the further appending Nodes are at the right side. This will technically be a Linked List making it’s operational complexity to be O(n).

No two Nodes in a Binary tree can have same value.

#include <iostream>

using namespace std;

// Node Class will create a Node
class Node{
	public:
		int value;
		Node* right;
		Node* left;

		Node(int value){
			this->value = value;
			right = nullptr;
			left = nullptr;
		}
};

// BinarySearchTree Class develops a Binary Search Tree
class BinarySearchTree{
	public:
		Node* root;

	public:
		/*
		BinarySearchTree(int value){
			Node* newNode = new Node(value);
			root = newNode;
		}

		In this case, a Node is being created as soon as the BinarySearchTree class is called.
		This can be a approach can also be done differently.
		Rather than creating a new Node, keep the Binary Tree empty.
		Set the root pointer nullptr.
		*/

		// Constructor for BinarySearchTree Class
		BinarySearchTree(){
			root = nullptr;
		}

		// The insert function will insert a Node of given value to the Binary Search Tree
		bool insert(int value){
			Node* newNode = new Node(value);
			if (root == nullptr){
				root = newNode;
				return true;
			}
			Node* temp = root;
			while (true){
				if (newNode->value == temp->value) return false;
				if (newNode->value < temp->value){
					if (temp->left == nullptr){
						temp->left = newNode;
						return true;
					}
					temp = temp->left;
				}
				else{
					if (temp->right == nullptr){
						temp->right = newNode;
						return true;
					}
					temp = temp->right;
				}
			}
		}

		// The contains function will search the given value in the Binary Search Tree and return true if the value is present in the Tree or false if the value is not present in the Binary Search Tree
		bool contains(int value){
			Node* temp = root;
			while (temp){
				if (value < temp->value){
					temp = temp->left;
				}
				else if (value > temp->value){
					temp = temp->right;
				}
				else{
					return true;
				}
			}
			return false;
		}
};

int main(){
    BinarySearchTree* myBST = new BinarySearchTree;
    
    myBST->insert(12);
    myBST->insert(4);
    myBST->insert(23);
    myBST->insert(45);
    myBST->insert(21);
    myBST->insert(76);
    myBST->insert(44);
    myBST->insert(54);
    
    cout << myBST->root->right->left->value << endl;
}