Various types of Data Structure
Data structures are essential in organizing and managing data efficiently in computer
science and software engineering.
1. Linear Data Structures: Linear data structures store data elements in a sequential
manner, where each element is connected to its previous and next element.
a. Arrays
● Definition: A collection of elements, each identified by an index.
● Characteristics: Fixed size, homogeneous elements, random access,
contiguous memory allocation.
● Operations: Traversal, insertion, deletion, searching, sorting.
● Example: int arr[5] = {10, 20, 30, 40, 50};
b. Linked Lists
● Definition: A collection of nodes where each node contains data and a
reference (or link) to the next node in the sequence.
● Types:
● Singly Linked List: Each node points to the next node.
● Doubly Linked List: Each node points to both the next and previous
nodes.
● Circular Linked List: The last node points back to the first node.
● Operations: Traversal, insertion, deletion, searching.
● Example:
struct Node {
int data;
Node* next;
};
c. Stacks
● Definition: A collection of elements that follows the Last In First Out (LIFO)
principle.
● Characteristics: Allows operations at one end only (top of the stack).
● Operations: Push (insert), pop (delete), peek (top element), isEmpty.
● Example:
stack<int> s;
s.push(10);
s.pop();
d. Queues
● Definition: A collection of elements that follows the First In First Out (FIFO)
principle.
● Types:
● Simple Queue: Elements are inserted at the rear and removed from the
front.
● Circular Queue: The last position is connected back to the first position.
● Priority Queue: Each element is associated with a priority, and
elements are served based on priority.
● Double-Ended Queue (Deque): Insertion and deletion can occur at both
ends.
● Operations: Enqueue (insert), dequeue (delete), front, rear, isEmpty.
● Example:
queue<int> q;
q.push(10);
q.pop();
2. Non-Linear Data Structures: Non-linear data structures store data elements
hierarchically or in interconnected networks, where each element can connect to
multiple elements.
a. Trees
● Definition: A hierarchical structure with a root node and child nodes forming a
parent-child relationship.
● Types:
● Binary Tree: Each node has at most two children.
● Binary Search Tree (BST): A binary tree with left child nodes less than
the parent and right child nodes greater than the parent.
● AVL Tree: A self-balancing binary search tree.
● B-Tree: A self-balancing search tree for databases and file systems.
● Heap: A special tree-based structure satisfying the heap property.
● Operations: Insertion, deletion, traversal (in-order, pre-order, post-order).
● Example:
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
};
b. Graphs
● Definition: A collection of nodes (vertices) connected by edges.
● Types:
● Directed Graph (Digraph): Edges have a direction.
● Undirected Graph: Edges do not have a direction.
● Weighted Graph: Edges have weights (values).
● Unweighted Graph: Edges do not have weights.
● Operations: Traversal (DFS, BFS), shortest path (Dijkstra, Floyd-Warshall),
minimum spanning tree (Prim, Kruskal).
● Example:
struct Graph {
int V;
list<int> *adj;
};
c. Hash Tables
● Definition: A data structure that maps keys to values for efficient data
retrieval.
● Characteristics: Uses a hash function to compute an index into an array of
buckets or slots.
● Operations: Insertion, deletion, searching.
● Example:
unordered_map<int, string> hashTable;
hashTable[1] = “value”;
3. Other Data Structures
a. Heaps
● Definition: A specialized tree-based data structure satisfying the heap
property.
● Types:
● Max-Heap: Parent nodes are greater than or equal to their children.
● Min-Heap: Parent nodes are less than or equal to their children.
● Operations: Insertion, deletion, find-min/max, heapify.
● Example:
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
b. Trie (Prefix Tree)
● Definition: A tree-like data structure used for storing dynamic sets of strings.
● Characteristics: Each node represents a character of the string.
● Operations: Insertion, searching, deletion, prefix matching.
● Example:
struct TrieNode {
TrieNode* children[26];
bool isEndOfWord;
};
