Data Structures

Data Structures in C++

Table of Contents

1. Binary Search Tree (BST)
2. Heap
3. Forward List
4. Doubly Linked List
5. Circular Doubly Linked List
6. Singly Linked List

Binary Search Tree (BST)

Code

#include<iostream>
using namespace std;

struct node{
    int data;
    node* left;
    node* right;
    node():data(0),left(nullptr),right(nullptr){}
    node(int x):data(x),left(nullptr),right(nullptr){}
    node(int x,node* l,node* r):data(x),left(l),right(r){}
};

class bst{
    public:
    node* head;
    bst(){
        head=nullptr;
    }
    bst(int x){
        head=new node(x);
    }
    void insert(int x){
        node* temp=head;
        while(temp!=nullptr){
            if (x<temp->data)
            {
                if(temp->left==nullptr){
                    temp->left=new node(x);
                    return;
                }
                temp=temp->left;
            }
            else{
                if(temp->right==nullptr){
                    temp->right=new node(x);
                    return;
                }
                temp=temp->right;
            }
        }
    }
    void inorder(node* temp){
        if(temp==nullptr){
            return;
        }
        inorder(temp->left);
        cout<<temp->data<<" ";
        inorder(temp->right);
    }
    bool find(int x){
        node* temp=head;
        while(temp!=nullptr){
            if(temp->data==x){
                return true;
            }
            else if(x<temp->data){
                temp=temp->left;
            }
            else{
                temp=temp->right;
            }
        }
        return false;
    }
};

int main(){
    bst b(5);
    b.insert(3);
    b.insert(7);
    b.insert(2);
    b.insert(4);
    b.insert(6);
    b.insert(8);
    b.inorder(b.head);
    cout<<b.find(4);
    return 0;
}

Explanation

This code implements a Binary Search Tree (BST) in C++. The node struct represents a node in the tree, and the bst class manages the tree operations. The insert method adds a new value to the tree, the inorder method performs an in-order traversal of the tree, and the find method searches for a value in the tree.

Heap

Code

#include<iostream>
#include<vector>
using namespace std;

class Heap{
private:
    vector<int> h;
public:
    int top(){
        if(!h.empty()) return h[0];
    }
    void insert(int x){
        if(h.size()==0){
            h.push_back(x);
        }else{
            h.push_back(x);
            int s=h.size()-1;
            for(int n=s;n>=0;n=(n-1)/2){
                if(h[n]>h[(n-1)/2]){
                    swap(h[n],h[(n-1)/2]);
                }else{
                    break;
                }
            }
        }
    }
    void maxheap(int i){
        int left,right,mx=i;
        left=2*i+1;
        right=2*i+2;
        if(left<h.size()&&h[left]>h[i]) mx=left;
        if(right<h.size()&&h[right]>h[mx]) mx=right;
        if(mx!=i){
            swap(h[i],h[mx]);
            maxheap(mx);
        }
    }
    void del(){
        if(h.empty()) return;
        else{
            int temp=h.back();
            h[0]=temp;
            h.pop_back();
            maxheap(0);
        }
    }
    int pop(){
        int ans=h[0];
        del();
        return ans;
    }
    vector<int> heapsort(){
        vector<int> ans;
        while(!h.empty()){
            ans.insert(ans.begin(),pop());
        }
        return ans;
    }
};

int main(){
    Heap ob;
    vector<int> v={7,6,5,4,3,2,1};
    for(int i:v){
        ob.insert(i);
    }
    vector<int> ans=ob.heapsort();
    for(int i:ans){
        cout<<i<<" ";
    }
    cout<<endl;
    return 0;
}

Explanation

This code implements a max-heap in C++. The Heap class uses a vector to store the heap elements. The insert method adds a new element to the heap, the maxheap method ensures the heap property is maintained, the del method removes the root element, and the heapsort method sorts the elements using the heap.

Forward List

Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    forward_list<int> l;
    l.push_front(1);
    l.push_front(2);
    l.push_front(3);
    l.push_front(4);
    //print elements
    for(auto i=l.begin();i!=l.end();i++){
        cout<<*i<<" ";
    }
}

Explanation

This code demonstrates the use of the forward_list container from the C++ Standard Library. It creates a forward list, adds elements to the front, and prints the elements.

Doubly Linked List

Code

#include<iostream>
using namespace std;

struct Node{
    int data;
    Node* next;
    Node* prev;
    Node():data(0),next(nullptr),prev(nullptr){}
    Node(int x):data(x),next(nullptr),prev(nullptr){}
    Node(int x,Node* n,Node* p):data(x),next(n),prev(p){}
};

class DoubleLinkList{
    public:
    Node* head;
    DoubleLinkList(){
        head=nullptr;
    }
    void insertFront(int x){
        Node* temp=new Node(x);
        if(head==nullptr){
            head=temp;
            return;
        }
        temp->next=head;
        head->prev=temp;
        head=temp;
    }
    void insertEnd(int x){
        Node* temp=head;
        while(temp->next!=nullptr){
            temp=temp->next;
        }
        Node* newNode=new Node(x);
        temp->next=newNode;
        newNode->prev=temp;
    }
    void deleteFront(){
        Node* temp=head;
        head=head->next;
        head->prev=nullptr;
        delete temp;
    }
    void deleteEnd(){
        Node* temp=head;
        while(temp->next->next!=nullptr){
            temp=temp->next;
        }
        Node* del=temp->next;
        temp->next=nullptr;
        delete del;
    }
    void print(){
        Node* temp=head;
        while(temp!=nullptr){
            cout<<temp->data<<" ";
            temp=temp->next;
        }
    }
};

int main(){
    Node* head=new Node(1);
    Node* second=new Node(2);
    Node* third=new Node(3);
    head->next=second;
    second->next=third;
    second->prev=head;
    third->prev=second;
    //print elements
    Node* temp=head;
    while(temp!=nullptr){
        cout<<temp->data<<" ";
        temp=temp->next;
    }
    return 0;
}

Explanation

This code implements a doubly linked list in C++. The Node struct represents a node in the list, and the DoubleLinkList class manages the list operations. The insertFront and insertEnd methods add elements to the front and end of the list, respectively. The deleteFront and deleteEnd methods remove elements from the front and end of the list, respectively. The print method prints the elements of the list.

Circular Doubly Linked List

Code

#include<iostream>
using namespace std;

struct Node{
    int data;
    Node* next;
    Node* prev;
    Node():data(0),next(nullptr),prev(nullptr){}
    Node(int x):data(x),next(nullptr),prev(nullptr){}
    Node(int x,Node* n,Node* p):data(x),next(n),prev(p){}
};

class DoubleLinkList{
    public:
    Node* head;
    DoubleLinkList(){
        head=nullptr;
    }
    void insertFront(int x){
        Node* temp=new Node(x);
        if(head==nullptr){
            head=temp;
            head->prev=head;
            head->next=head;
            return;
        }
        temp->next=head;
        temp->prev=head->prev;
        head->prev->next=temp;
        head->prev=temp;
        head=temp;
    }
    void insertEnd(int x){
        Node* newNode=new Node(x);
        if(head==nullptr){
            head=newNode;
            head->prev=head;
            head->next=head;
            return;
        }
        head->prev->next=newNode;
        newNode->prev=head->prev;
        newNode->next=head;
        head->prev=newNode;
    }
    void deleteFront(){
        Node* temp=head;
        head=head->next;
        head->prev=nullptr;
        delete temp;
    }
    void deleteEnd(){
        Node* temp=head;
        while(temp->next->next!=nullptr){
            temp=temp->next;
        }
        Node* del=temp->next;
        temp->next=nullptr;
        delete del;
    }
    void print(){
        Node* temp=head;
        while(temp!=nullptr){
            cout<<temp->data<<" ";
            temp=temp->next;
        }
    }
};

Explanation

This code implements a circular doubly linked list in C++. The Node struct represents a node in the list, and the DoubleLinkList class manages the list operations. The insertFront and insertEnd methods add elements to the front and end of the list, respectively. The deleteFront and deleteEnd methods remove elements from the front and end of the list, respectively. The print method prints the elements of the list.

Singly Linked List

Code

#include<iostream>
using namespace std;

struct LinkNode{
 int val;
 LinkNode* next;
 LinkNode(): val(0),next(nullptr){}
 LinkNode(int x):val(x),next(nullptr){}
 LinkNode(int x,LinkNode* node):val(x),next(node){}
};

class linklistr{
    public:
    LinkNode* head;
    linklistr(){
        head=nullptr;
    }
    void insertFront(int x){
        LinkNode* temp=new LinkNode(x);
        if(head==nullptr){
            head=temp;
            return;
        }
        temp->next=head;
        head=temp;
    }
    void insertEnd(int x){
        LinkNode* temp=head;
        while(temp->next!=nullptr){
            temp=temp->next;
        }
        temp->next=new LinkNode(x);
    }
    void deleteFront(){
        LinkNode* temp=head;
        head=head->next;
        delete temp;
    }
    void deleteEnd(){
        LinkNode* temp=head;
        while(temp->next->next!=nullptr){
            temp=temp->next;
        }
        LinkNode* del=temp->next;
        temp->next=nullptr;
        delete del;
    }
    void print(){
        LinkNode* temp=head;
        while(temp!=nullptr){
            cout<<temp->val<<" ";
            temp=temp->next;
        }
    }
};

void insertAtEnd(LinkNode* head, int val){
    LinkNode* temp = head;
    while(temp->next!=nullptr){
        temp = temp->next;
    }
    temp->next = new LinkNode(val);
}

void insertAtBegin(LinkNode** head, int val){
    LinkNode* temp = new LinkNode(val);
    temp->next = *head;
    *head = temp;
}

int main(){
    LinkNode* third = new LinkNode(3);
    LinkNode* second = new LinkNode(2,third);
    LinkNode* head = new LinkNode(1,second);
    cout<<&head<<endl;
    insertAtBegin(&head,8);
    LinkNode* temp = head;
    while(temp!=nullptr){
    cout<<temp->val<<" ";
    temp = temp->next;
    }
    cout<<endl;
    return 0;
}

Explanation

This code implements a singly linked list in C++. The LinkNode struct represents a node in the list, and the linklistr class manages the list operations. The insertFront and insertEnd methods add elements to the front and end of the list, respectively. The deleteFront and deleteEnd methods remove elements from the front and end of the list, respectively. The print method prints the elements of the list.

Conclusion

This wiki provides a comprehensive overview of various data structures implemented in C++. Each section includes the code implementation, an explanation of the code, and any necessary refactoring. These implementations can be used as a reference for understanding and working with data structures in C++.