Data Structures in C++

A Data Structure is a way of storing, organizing, and managing data so that it can be accessed and modified efficiently. In C++, data structures can be:

• Built-in (provided by the language) — such as Arrays, Structures, Unions, and Classes.
• User-defined or complex (built using built-in data structures) — such as Stacks, Queues, Linked Lists, Trees, Graphs, Maps, and Sets.

1. Arrays

An Array is a static data structure that stores elements of the same type in consecutive memory locations. Its size must be known at compile time.

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

2. Lists

A List is a dynamic data structure that stores elements in a sequence. Unlike stacks and queues, lists allow insertion, deletion, and modification of elements at any position. In C++, lists are often implemented using the Standard Template Library (STL) list container.

3. Maps

A Map stores elements as key–value pairs. Each key is unique and maps to exactly one value. In C++ STL, map stores items in sorted key order, while unordered_map uses hashing for faster access.

4. Stacks

A Stack follows the LIFO (Last-In-First-Out) principle. Elements are added (pushed) and removed (popped) from the top only.

// Example using STL
stack s;
s.push(10);
s.pop();

5. Queues

A Queue follows the FIFO (First-In-First-Out) principle. Elements are added at the back and removed from the front.

6. Sets

A Set is a collection of unique elements of the same type. Operations include:

• Membership testing
• Insertion
• Deletion

C++ STL provides set (ordered) and unordered_set (faster lookup).

7. Linked List

A Linked List is a dynamic data structure made up of nodes, each containing:

• Data
• A pointer to the next node

Nodes can be stored anywhere in memory and are linked using pointers.

7.1 Circular Linked List

The last node points back to the first node instead of NULL. This allows continuous traversal from any point in the list.

7.2 Doubly Linked List

Each node contains:

• A pointer to the previous node
• A pointer to the next node

This allows traversal in both directions.

8. Trees

A Tree is a non-linear data structure consisting of nodes connected in a hierarchy. The top node is called the root, and each node may have child nodes.

8.1 Binary Tree

Each node has at most two children: left and right. The root pointer points to the top node of the tree.

8.2 Binary Search Tree (BST)

A special type of binary tree where:

• Left child contains values smaller than the parent
• Right child contains values greater than the parent

Used for efficient searching, insertion, and deletion.

9. Graphs

A Graph is a set of nodes (vertices) connected by edges. It can be:

• Directed — edges have a direction
• Undirected — edges have no direction

Graphs are used to represent networks like social connections, road maps, and computer networks.