DATA STRUCTURES IN C++

 This page contains the list of data structure programs implemented in C++.

1. Linked list in C++ 

2. Double linked list in C++

3. Stack using array in C++

4. Stack using linked list in C++

5. Queue using dynamic array in C++

6. Queue using linkedlist in C++

7. Binary Search Tree in C++

8. AVL Balance Binary Search Tree in C++

9. Binary Heap In C++

10. Trie in C++

11. Circular Buffer / Ring Buffer in C++

Popular posts from this blog

Binary Heap in C++

Image
Implementation Binary heap data structure in C++.  This class implemeted for MAX HEAP data structure.  Github:  sourcecode/binaryheap.h #include <iostream> #include <vector> using namespace std; /* class binary heap (priority queue) */ /* This class implemented for MAX_HEAP */ template <typename T> class binaryheap { private: int heaptype; //Max heap or min heap. This class implemented for MAX_HEAP vector<T> heap; //heap datastructure public: //constructor binaryheap(int type) :heaptype(type) {} //parameterised constructor binaryheap(T *arr, int _size) { if (_size != 0) { for (int i=0; i<_size;i++) { //push all the elements to the vector heap.push_back(arr[i]); } } //heapify for (int i = (_size / 2) - 1; i >= 0; i--) { sink(i); } } //add the element void add(T elem) { int m_size = (int)heap.size(); //add element at the back heap.push_back(elem); if (m_size != 0) { //hea...
Read more

AVL Balance Binary Search Tree in C++

Image
Implementation of AVL Balance binary search tree in C++.  Github:  sourcecode/AVLbalancedtree.h #include <iostream> #include "queueusinglinkedlist.h" using namespace std; /* AVL balanced binary search tree class*/ template <typename T> class avlbalancedbst { private: /* node */ template <typename T>class Node { public: Node<T>* left; //left tree Node<T>* right; //right tree T data; //data int height; //height of the tree int bf; //balance factor //constructor Node<T>() :left(nullptr), right(nullptr) { } }; //root node Node<T>* root; public: //constructor avlbalancedbst() :root(nullptr) { } //add element void addrecursive(T elem) { //if the element is already found, return if (findelement(root, elem)) { return; } //add element root = addrecursive(root, elem); } //recursive call to add the element to the tree Node<T>* addrecursive(Node<T>* node, T elem) { //...
Read more

Trie in C++

Image
 Implementation of Trie data structure in C++. GitHub:  sourcecode/trie.h #include <iostream> #include <unordered_map> #include <string> using namespace std; /* trie class */ class trie { public: //trienode class class trienode { public: char m_ch; //char which node holds it bool m_endofstring; //end of string //trie class should have 26 pointers (characters in alphabets) to point the child nodes, //as it takes more memory also not all the child nodes are used, instead of creating the 26 pointer nodes //used unordered_map to hold child nodes. //unorderemap is based on hash table, it doesn't store sorted values. unordered_map<char, trienode*> child; int count; //num of shared prefix for different words //constructor trienode() : m_ch{ '\0' }, m_endofstring(false), count(0) { } trienode(char ch) :m_ch(ch), m_endofstring(false),count(0) { } //add character as child of the current node...
Read more

Generic Circular Queue / Circular Buffer / Ring buffer in C++

Image
Circular queue / Circular buffer / Ring buffer: Introduction:     The intention of this design to provide the generic circular buffer which can be used for any data types. What is circular buffer ?           Circular buffer/queue is a liner data structure which has fixed size of array where both the ends are connected. This data structure works as FIFO(First In First Out) model.  That means old data is read first.  If the buffer is full or reached max size, it will start overwriting the old data from the beginning.  Circular/ring buffer is used in producer consumer problem, where consumer is not meeting the speed of the producer, Producer produces the new data and overwrite with the old data , if the buffer reached maximum size. Circular buffer is the good choice for implementing queue that has fixed maximum size. All the operation happens at constant time (push, pop).      Implementation: Source code :    source...
Read more

Stack using array in C++

Implemenation of stack class using array in c++.  GitHub :  sourcecode/stackusingarray.h #ifndef _STACK_USING_ARRAY_H #define _STACK_USING_ARRAY_H #include <iostream> using namespace std; #define MAX_ARRAY_SIZE 10 /* stack class usign array */ template <typename T> class stackarr { private: T arr[10]; //static array int size; int index; //helper functions inline void increaseSize() { ++size; } inline void decreaseSize() { --size; } public: //constructor stackarr() :size(MAX_ARRAY_SIZE),index(-1) { } //push element to the stack void push(T elem) { //when max size reached if (MAX_ARRAY_SIZE == size) { cerr << "stack reached max size" << endl; } else { arr[++index] = elem; increaseSize(); } } //Get the top element of the stack T top() { if (!isEmpty()) { //return the data from the array return arr[index]; } else { //if stack is empty cerr << "Top(): empty stack"...
Read more

Stack using Linkedlist in C++

Implementation of stack datastructure using linkedlist. Here, I have used Linkedlist class which I have implemented https://learnprogrammingconcepts2023.blogspot.com/2023/06/linkedlist-implementation-in-c.html.  GitHub : sourcecode/stacksinglelinkedlist.h #ifndef _STACK_SINGLE_LINKEDLIST_H #define _STACK_SINGLE_LINKEDLIST_H /* Stack class using linked list */ template <typename T> class liststack { linkedList<T>* stack; //linkedlist public: //constructor liststack() { stack = new linkedList<T>(); } //push the data to the stack void push(T elem) { //add the data as last element in the stack. stack->addlast(elem); } //Get the top element in the stack. T top() { if (stack->isEmpty()) { cout << "empty list" << endl; //return -1; } //get the last element of the linked list return stack->peeklast(); } //pop the last element in the stack void pop() { if (stack->isEmpty()) { cout << ...
Read more

Linkedlist class in C++

Image
Implemented linkedlist in C++.  Used the below linkedlist class to create custom stack , queue classes.  Github path : sourcecode/linkedList.h #include <iostream> using namespace std; /*single linkedlist class */ template <typename T> class linkedList { private: /* create node class */ template <typename T> class Node { public: T data; //data Node<T>* next; //next pointer //constructor Node() :next(nullptr) { } }; int m_size; //size of the linked list Node<T>* m_head; //head pointer Node<T>* m_tail; //tail pointer //helper functions inline void increaseListSize() { m_size++; } inline void decreaseListSize() { m_size--; } public: //constructor linkedList() :m_head(nullptr), m_tail(nullptr), m_size(0) { } //get size of the linked list int getsize() { return m_size; } //check whether linked list is empty bool isEmpty() { return (0 == m_size) ? true : false; } //Add elements to the list v...
Read more

Numpy Tutorials

Image
Introduction: numpy is python library created to provide the fast access to array elements. numpy array is stored in the continuous memory locations, so its faster than the list to access. This also provides functions to work with linear algebra, fourier transform, and metrices. Array creation: Slicing array: Slicing array means taking elements from the given index (start) to another given (end)  index. If we don't pass the starting index, then starting index considered as 0. Similarly if no end index provided, then end index considered as length of the array. Default step size is 1. Start index considered from 0 index value, end index considered from 1 index. For example: from 3rd index from the end to first index from the end. In this time, start index starts count from 1 index, end index start count from 0 index View and Copy The difference between the copy and view is that copy is the new array and view is the view of the original array.  Copy owns the array data. Any chan...
Read more

Queue using dynamic array in C++

Implementation queue datastructure using dynamic array.  Github:  sourcecode/queueusingdynamicarray.h #include <iostream> using namespace std; #define MAX_CAPACITY 10 /* queue class using dynamic array*/ template <typename T> class queueArray { private: T* queue; //queue data pointer int size; //size of the queue int capacity; //capacity of the queue int front; //front element of the queue int rear; //last element of the queue public: //constructor queueArray() :queue(nullptr), size(0), capacity(MAX_CAPACITY), front(-1), rear(-1) { //create the dynamic array based on the MAX_CAPACITY queue = new T[capacity]; } queueArray(int cap) :queue(nullptr), size(0), capacity(cap), front(-1), rear(-1) { //create the dynamic array based on the capacity queue = new T[capacity]; } //return true, if size of the queue is zero bool isEmpty() { return (size == 0) ? true : false; } //add the element to queue void enqueue(T elem) { //adding firs...
Read more

Double linked list in C++

 Implementation of double linked list class in C++ Github :  sourcecode/doublelinkedlist.cpp #include <iostream> using namespace std; /* Double linked list class */ template <typename T> class doublelinkedlist { private: int m_size; //size of the list //data structure Node class template <typename T> class Node { public: T data; Node<T>* prev_node; Node<T>* next_node; //constructor of the node Node() :prev_node(nullptr), next_node(nullptr) {} }; //head pointer Node<T>* m_head; public: //constructor doublelinkedlist():m_size(0),m_head(nullptr) {} //add element void add(T elem); void addatfirst(T elem); void addatlast(T elem); void addat(int pos, T elem); void removefirst(); void removelast(); void removeat(int pos); void printlist(); }; //Add element at the first node template <typename T>void doublelinkedlist<T>::addatfirst(T elem) { //create new node Node<T>* new_node = new Node<T...
Read more