Introduction to Data Structures

What Are Data Structures?

Data structures are a way of organizing and storing data in a computer so that it can be accessed and modified efficiently. They are essential for creating efficient algorithms and play a crucial role in software development. Common data structures include arrays, linked lists, stacks, queues, and trees.

Types of Data Structures

Data structures can be broadly classified into two categories:

• Linear Data Structures: Elements are arranged in a sequential manner. Examples: Arrays, Linked Lists, Stacks, Queues.
• Non-linear Data Structures: Elements are arranged in a hierarchical manner. Examples: Trees, Graphs.

Arrays

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).

int arr[5] = {1, 2, 3, 4, 5};

Linked Lists

A linked list is a linear data structure where each element is a separate object. Each element (node) of a list is comprising of two items - the data and a reference to the next node. The last node has a reference to null.

struct Node {
    int data;
    Node* next;
};

Node* head = new Node();
head->data = 1;
head->next = new Node();
head->next->data = 2;
head->next->next = nullptr;
                

Stacks

A stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out). Mainly the following three basic operations are performed in the stack:

• Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.
• Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.
• Peek or Top: Returns the top element of the stack.

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

int main() {
    stack<int> s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << "Top element: " << s.top() << endl;
    s.pop();
    cout << "Top element after pop: " << s.top() << endl;
    return 0;
}
                

Queues

A queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.

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

int main() {
    queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);
    cout << "Front element: " << q.front() << endl;
    q.pop();
    cout << "Front element after pop: " << q.front() << endl;
    return 0;
}
                

Trees

A tree is a non-linear data structure which organizes data in a hierarchical structure and this is a recursive definition. A tree is a collection of nodes, where nodes contain a value and a list of references to other nodes (the "children"). Each tree has a root node (the starting point of the tree) and can have any number of children nodes.

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int value) {
        data = value;
        left = right = nullptr;
    }
};

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    cout << "Root Node: " << root->data << endl;
    cout << "Left Child of Root: " << root->left->data << endl;
    cout << "Right Child of Root: " << root->right->data << endl;
    return 0;
}