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.

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. In this case, vertex will contain the key of the adjList and edges will be the value, in this case it is a unordered set
				cout << vertex << ": [";
				for (auto edge: edges){				// Here, we are getting the value of each element in the set as a variable edge from the unordered_set called edges which was the value of the key in the unordered map
					cout << edge << " ";
				}
				cout << "]" << endl;
			}
		}

		bool addVertex (string vertex){
			if (adjList.count(vertex) == 0){				// Check is the given vertex exists in the adjList unordered_map
				adjList[vertex];
				return true;
			}
			return false;
		}

		bool addEdge(string vertex1, string vertex2){				// Get the name as a string of the two vertex that are to be connected
			if (adjList.count(vertex1) != 0 && adjList.count(vertex2) != 0){				// Check for if the given vertex exist in the adjList unordered_map
				adjList.at(vertex1).insert(vertex2);				// Insert (associate) the value of the vertex to the other vertex in it's corresponding unordered_list (edge) 
				adjList.at(vertex2).insert(vertex1);				// Do the vice-versa of the previous instruction
				return true;
			}
			return false;
		}

		bool removeEdge(string vertex1, string vertex2){				// Get the name as a string of the two vertex that are to be disconnected
			if (adjList.count(vertex1) != 0 && adjList.count(vertex2) != 0){				// Check for if the given vertex exist in the adjList unordered_map
				adjList.at(vertex1).erase(vertex2);				// erase (remove) the value of the vertex to the other vertex in it's corresponding unordered_list (edge) 
				adjList.at(vertex2).erase(vertex1);				// Do the vice-versa of the previous instruction
				return true;
			}
			return false;
		}

		bool removeVertex(string vertex){
			if (adjList.count(vertex) == 0) return false;				// If the vertex does not exist in the Graph, return false
			for (auto otherVertex: adjList.at(vertex)){				// For every vertex given in the unordered_list which contains the edges of the associated Vertex, apply the following operation on it (that is to go to that vertex and delete the given vertex that is to be deleted) 
				adjList.at(otherVertex).erase(vertex);				// Erase the linkage of the given vertex with that vertex in the unordered_map
			}
			adjList.erase(vertex);				// Finally, erase the given vertex as whole (the key that is the name of the vertex as well as the unordered_list associated with that vertex)
			return true;
		}
};

int main(){
	Graph* myGraph = new Graph();
	myGraph->addVertex("A");
	myGraph->addVertex("B");
	myGraph->addVertex("C");
	
	myGraph->addEdge("A", "B");
	myGraph->addEdge("B", "C");
	myGraph->addEdge("C", "A");
    
    myGraph->removeVertex("A");
	
	myGraph->printGraph();
}