Data Structure

In computer science, a data structure is a way of organizing and storing data in a computer’s memory. It provides a way to represent and manipulate data in a way that facilitates efficient access and modification of the data.

Data structures can be implemented using various programming languages and can be classified into two main categories: primitive and non-primitive data structures.

Primitive data structures are basic data types provided by programming languages such as integers, floating-point numbers, characters, and booleans. They are not modifiable and are used to represent simple values.

Non-primitive data structures, on the other hand, are more complex and can be further divided into linear and nonlinear data structures. Linear data structures include arrays, linked lists, stacks, and queues, while nonlinear data structures include trees and graphs. Non-primitive data structures can be modified, and they can represent more complex relationships between data.

Choosing the right data structure is essential to optimize the performance of algorithms that manipulate data. Data structures are a fundamental concept in computer science and are used extensively in programming and software development.

Here are some common data structure topics that you must know:

  1. Arrays – a collection of elements of the same type that are stored in contiguous memory locations.
  2. Linked Lists – a data structure that consists of a sequence of nodes, each containing a reference to an object and a reference to the next node.
  3. Stacks – a data structure that stores and retrieves elements in a “last in, first out” (LIFO) manner.
  4. Queues – a data structure that stores and retrieves elements in a “first in, first out” (FIFO) manner.
  5. Trees – a hierarchical data structure that consists of nodes connected by edges, with a single node called the root.
  6. Graphs – a collection of vertices connected by edges, where each edge has a weight or cost associated with it.
  7. Hash Tables – a data structure that uses a hash function to map keys to values, allowing for efficient lookup and insertion.
  8. Heaps – a data structure that represents a partially ordered tree, where the value of each node is greater than or equal to (or less than or equal to) the values of its children.
  9. Tries – a tree-like data structure that is used to store and retrieve associative arrays, where each node represents a prefix of a key.
  10. Sorting Algorithms – algorithms that are used to sort a collection of elements in a specific order, such as ascending or descending order.

Arrays

An array is a fundamental data structure used in computer programming to store and organize a collection of elements of the same data type. These elements are stored in contiguous memory locations, making it easy to access and manipulate them efficiently.

#include <iostream>

int main() {
    // Declare an array of integers with a size of 5
    int arr[5];

    // Assign values to the array elements
    arr[0] = 10;
    arr[1] = 20;
    arr[2] = 30;
    arr[3] = 40;
    arr[4] = 50;

    // Access and print array elements
    for (int i = 0; i < 5; i++) {
        std::cout << "Element at index " << i << ": " << arr[i] << std::endl;
    }

    return 0;
}

Linked List

A linked list is a linear data structure used in computer programming to organize and store a collection of elements, called nodes. Unlike arrays, which store elements in contiguous memory locations, linked lists store elements non-contiguously in memory and connect them using pointers.

#include<iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    Node(int data) {
        this->data = data;
        this->next = NULL;
    }
};

class LinkedList {
public:
    Node* head;

    LinkedList() {
        this->head = NULL;
    }

    void insert(int data) {
        Node* newNode = new Node(data);
        if (head == NULL) {
            head = newNode;
        }
        else {
            Node* temp = head;
            while (temp->next != NULL) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
    }

    void display() {
        Node* temp = head;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
};

int main() {
    LinkedList linkedList;

    linkedList.insert(1);
    linkedList.insert(2);
    linkedList.insert(3);

    linkedList.display();

    return 0;
}

Stack

#include <iostream>
using namespace std;

#define MAX_SIZE 100

class Stack {
private:
    int top;
    int arr[MAX_SIZE];

public:
    Stack() {
        top = -1;
    }

    bool isEmpty() {
        return (top == -1);
    }

    bool isFull() {
        return (top == MAX_SIZE - 1);
    }

    void push(int value) {
        if (isFull()) {
            cout << "Stack Overflow" << endl;
            return;
        }

        arr[++top] = value;
        cout << value << " pushed to stack" << endl;
    }

    int pop() {
        if (isEmpty()) {
            cout << "Stack Underflow" << endl;
            return -1;
        }

        int value = arr[top--];
        return value;
    }

    int peek() {
        if (isEmpty()) {
            cout << "Stack is empty" << endl;
            return -1;
        }

        return arr[top];
    }
};

int main() {
    Stack stack;

    stack.push(1);
    stack.push(2);
    stack.push(3);

    cout << stack.pop() << " popped from stack" << endl;

    cout << "Top element of stack: " << stack.peek() << endl;

    return 0;
}

Queues

#include <iostream>

template <typename T>
class Queue {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& value) : data(value), next(nullptr) {}
    };

    Node* front;
    Node* rear;

public:
    Queue() : front(nullptr), rear(nullptr) {}
    ~Queue() {
        while (!isEmpty()) {
            dequeue();
        }
    }

    bool isEmpty() const {
        return front == nullptr;
    }

    void enqueue(const T& value) {
        Node* newNode = new Node(value);

        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
    }

    void dequeue() {
        if (isEmpty()) {
            std::cout << "Queue is empty. Cannot dequeue from an empty queue." << std::endl;
            return;
        }

        Node* temp = front;
        front = front->next;
        if (front == nullptr) {
            rear = nullptr;
        }
        delete temp;
    }

    T& getFront() {
        if (isEmpty()) {
            throw std::runtime_error("Queue is empty. Cannot get the front element from an empty queue.");
        }
        return front->data;
    }
};

// Example usage
int main() {
    Queue<int> myQueue;
    myQueue.enqueue(10);
    myQueue.enqueue(20);
    myQueue.enqueue(30);

    std::cout << "Front element of the queue: " << myQueue.getFront() << std::endl;

    while (!myQueue.isEmpty()) {
        std::cout << myQueue.getFront() << " ";
        myQueue.dequeue();
    }

    return 0;
}

Tree

#include <iostream>
#include <vector>

using namespace std;

// Tree Node
class TreeNode {
public:
    int val;
    vector<TreeNode*> children;

    TreeNode(int x) : val(x) {}
};

// Tree Traversal
void preOrder(TreeNode* root) {
    if (root == nullptr) return;

    cout << root->val << " ";
    for (TreeNode* child : root->children) {
        preOrder(child);
    }
}

int main() {
    // Create Tree
    TreeNode* root = new TreeNode(1);
    
    TreeNode* node2 = new TreeNode(2);
    TreeNode* node3 = new TreeNode(3);
    TreeNode* node4 = new TreeNode(4);
    TreeNode* node5 = new TreeNode(5);

    root->children.push_back(node2);
    root->children.push_back(node3);
    root->children.push_back(node4);
    node3->children.push_back(node5);

    // Traverse Tree (preorder)
    cout << "Tree traversal (preorder): ";
    preOrder(root);

    return 0;
}