# Data Structures Tutorial

** Data structures **are essential components that help organize and store data efficiently in computer memory. They provide a way to manage and manipulate data effectively, enabling faster access, insertion, and deletion operations.

Common data structures include ** arrays, linked lists, stacks, queues, trees, and graphs **, each serving specific purposes based on the requirements of the problem. Understanding data structures is fundamental for designing efficient algorithms and optimizing software performance.

Table of Content

## What is a Data Structure?

A ** data structure** is a way of organizing and storing data in a computer so that it can be accessed and used efficiently. It defines the relationship between the data and the operations that can be performed on the data

## Why are Data Structures Important?

Data structures are essential for the following reasons:

They enable efficient storage and retrieval of data, reducing processing time and improving performance.**Efficient Data Management:**They organize data in a logical manner, making it easier to understand and access.**Data Organization:**They hide the implementation details of data storage, allowing programmers to focus on the logical aspects of data manipulation.**Data Abstraction:**Common data structures can be reused in multiple applications, saving time and effort in development.**Reusability:**The choice of the appropriate data structure can significantly impact the efficiency of algorithms that operate on the data.**Algorithm Optimization:**

## Classification of Data Structures

Data structures can be classified into two main categories:

These structures store data in a sequential order this allowing for easy**Linear Data Structures:**and**insertion**operations. Examples include arrays, linked lists, and queues.**deletion**These structures store data in a hierarchical or interconnected manner this allowing for more complex relationships between data elements. Examples include trees, graphs, and hash tables.**Non-Linear Data Structures:**

## Types of Data Structures

Basically, data structures are divided into two categories:

**Linear Data Structures:**

**Linear Data Structures:**

A collection of elements of the same type stored in contiguous memory locations.**Array:**A collection of elements linked together by pointers, allowing for dynamic insertion and deletion.**Linked List:**A First-In-First-Out (FIFO) structure where elements are added at the end and removed from the beginning.**Queue:**A Last-In-First-Out (LIFO) structure where elements are added and removed from the top.**Stack:**

### Non-Linear Data Structures:

A hierarchical structure where each node can have multiple child nodes.**Tree:**collection of nodes connected by edges, representing relationships between data elements.**Graph: A**A data structure that uses a hash function to map keys to values, allowing for fast lookup and insertion.**Hash Table:**

## Applications of Data Structures

Data structures are widely used in various applications, including:

To store and manage large amounts of structured data.**Database Management Systems:**To manage memory, processes, and files.**Operating Systems:**To represent source code and intermediate code.**Compiler Design:**To represent knowledge and perform reasoning.**Artificial Intelligence:**To store and process images, videos, and audio data.**Graphics and Multimedia:**

## Learn Basics of Data Structure:

- Introduction to Linear Data Structures
- Introduction to Hierarchical Data Structure
- Overview of Data Structures | Set 3 (Graph, Trie, Segment Tree and Suffix Tree)
- Abstract Data Types

**Most Popular Data Structures**:

**Most Popular Data Structures**

Below are some most popular Data Structure:

### 1. Array:

** Array** is a linear data structure that stores a collection of elements of the same data type. Elements are allocated contiguous memory, allowing for constant-time access. Each element has a unique index number.

**Important articles on****Array:**

- Search, insert and delete in an unsorted array
- Search, insert and delete in a sorted array
- Write a program to reverse an array
- Leaders in an array
- Given an array A[] and a number x, check for pair in A[] with sum as x
- Majority Element
- Find the Number Occurring Odd Number of Times
- Largest Sum Contiguous Subarray
- Find the Missing Number
- Search an element in a sorted and pivoted array
- Merge an array of size n into another array of size m+n
- Median of two sorted arrays
- Program for array rotation
- Reversal algorithm for array rotation
- Block swap algorithm for array rotation
- Maximum sum such that no two elements are adjacent
- Sort elements by frequency | Set 1
- Count Inversions in an array

**Related articles on Array:**

- All Articles on Array
- Coding Practice on Array
- Quiz on Array
- Coding Practice on Array
- Recent Articles on Array

### 2. Matrix:

A ** matrix **is a two-dimensional array of elements, arranged in rows and columns. It is represented as a rectangular grid, with each element at the intersection of a row and column.

**Important articles on****Matrix:**

- Search in a row wise and column wise sorted matrix
- Print a given matrix in spiral form
- A Boolean Matrix Question
- Print unique rows in a given boolean matrix
- Maximum size square sub-matrix with all 1s
- Print unique rows in a given boolean matrix
- Inplace M x N size matrix transpose | Updated
- Dynamic Programming | Set 27 (Maximum sum rectangle in a 2D matrix)
- Strassen’s Matrix Multiplication
- Create a matrix with alternating rectangles of O and X
- Print all elements in sorted order from row and column wise sorted matrix
- Given an n x n square matrix, find sum of all sub-squares of size k x k
- Count number of islands where every island is row-wise and column-wise separated
- Find a common element in all rows of a given row-wise sorted matrix

**Related articles on Matrix:**

### 3. Linked List:

A ** linear data structure** where elements are stored in nodes linked together by pointers. Each node contains the data and a pointer to the next node in the list. Linked lists are efficient for

**and**

**inserting****elements, but they can be slower for accessing elements than arrays.**

**deleting****Types of Linked List:**

** a) Singly Linked List: **Each node points to the next node in the list.

**Important articles on Singly Linked Lis:**

- Introduction to Linked List
- Linked List vs Array
- Linked List Insertion
- Linked List Deletion (Deleting a given key)
- Linked List Deletion (Deleting a key at given position)
- A Programmer’s approach of looking at Array vs. Linked List
- Find Length of a Linked List (Iterative and Recursive)
- How to write C functions that modify head pointer of a Linked List?
- Swap nodes in a linked list without swapping data
- Reverse a linked list
- Merge two sorted linked lists
- Merge Sort for Linked Lists
- Reverse a Linked List in groups of given size
- Detect and Remove Loop in a Linked List
- Add two numbers represented by linked lists | Set 1
- Rotate a Linked List
- Generic Linked List in C

** b) Circular Linked List: **The last node points back to the first node, forming a circular loop.

**Important articles on****Circular Linked List:**

- Circular Linked List Introduction and Applications,
- Circular Singly Linked List Insertion
- Circular Linked List Traversal
- Split a Circular Linked List into two halves
- Sorted insert for circular linked list

** c) Doubly Linked List: **Each node points to both the next and previous nodes in the list.

**Important articles on****Doubly Linked List:**

- Doubly Linked List Introduction and Insertion
- Delete a node in a Doubly Linked List
- Reverse a Doubly Linked List
- The Great Tree-List Recursion Problem.
- QuickSort on Doubly Linked List
- Merge Sort for Doubly Linked List

**Related articles on Linked List:**

### 4. Stack:

** Stack **is a linear data structure that follows a particular order in which the operations are performed. The order may be

**or**

**LIFO(Last In First Out)****.**

**FILO(First In Last Out)****implies that the element that is inserted last, comes out first and**

**LIFO****implies that the element that is inserted first, comes out last.**

**FILO****Important articles on****Stack:**

- Introduction to Stack
- Infix to Postfix Conversion using Stack
- Evaluation of Postfix Expression
- Reverse a String using Stack
- Implement two stacks in an array
- Check for balanced parentheses in an expression
- Next Greater Element
- Reverse a stack using recursion
- Sort a stack using recursion
- The Stock Span Problem
- Design and Implement Special Stack Data Structure
- Implement Stack using Queues
- Design a stack with operations on middle element
- How to efficiently implement k stacks in a single array?
- Sort a stack using recursion

**Related articles on Stack:**

### 5. Queue:

A ** Queue Data Structure **is a fundamental concept in computer science used for storing and managing data in a specific order. It follows the principle of

**” (**

**“First in, First out****), where the first element added to the queue is the first one to be removed**

**FIFO****Important articles on****Queue:**

- Queue Introduction and Array Implementation
- Linked List Implementation of Queue
- Applications of Queue Data Structure
- Priority Queue Introduction
- Deque (Introduction and Applications)
- Implementation of Deque using circular array
- Implement Queue using Stacks
- Find the first circular tour that visits all petrol pumps
- Maximum of all subarrays of size k
- An Interesting Method to Generate Binary Numbers from 1 to n
- How to efficiently implement k Queues in a single array?

**Related articles on Queue:**

### 6. Binary Tree:

** Binary Tree **is a hierarchical data structure where each node has at most two child nodes, referred to as the

**child and the**

**left****child. Binary trees are mostly used to represent hierarchical data, such as file systems or family trees.**

**right****Important articles on****Binary Tree:**

- Binary Tree Introduction
- Binary Tree Properties
- Types of Binary Tree
- Handshaking Lemma and Interesting Tree Properties
- Enumeration of Binary Tree
- Applications of tree data structure
- Tree Traversals
- BFS vs DFS for Binary Tree
- Level Order Tree Traversal
- Diameter of a Binary Tree
- Inorder Tree Traversal without Recursion
- Inorder Tree Traversal without recursion and without stack!
- Threaded Binary Tree
- Maximum Depth or Height of a Tree
- If you are given two traversal sequences, can you construct the binary tree?
- Clone a Binary Tree with Random Pointers
- Construct Tree from given Inorder and Preorder traversals
- Maximum width of a binary tree
- Print nodes at k distance from root
- Print Ancestors of a given node in Binary Tree
- Check if a binary tree is subtree of another binary tree
- Connect nodes at same level

**Related articles on Binary Tree:**

### 7. Binary Search Tree:

A ** Binary Search Tree** is a data structure used for storing data in a sorted manner. Each node in a

**has at most two children, a**

**Binary Search Tree****child and a**

**left****child, with the**

**right****child containing values less than the parent node and the**

**left****child containing values greater than the parent node. This hierarchical structure allows for efficient searching, insertion, and deletion operations on the data stored in the tree.**

**right****Important articles on****Binary Search Tree:**

- Search and Insert in BST
- Deletion from BST
- Minimum value in a Binary Search Tree
- Inorder predecessor and successor for a given key in BST
- Check if a binary tree is BST or not
- Lowest Common Ancestor in a Binary Search Tree.
- Inorder Successor in Binary Search Tree
- Find k-th smallest element in BST (Order Statistics in BST)
- Merge two BSTs with limited extra space
- Two nodes of a BST are swapped, correct the BST
- Floor and Ceil from a BST
- In-place conversion of Sorted DLL to Balanced BST
- Find a pair with given sum in a Balanced BST
- Total number of possible Binary Search Trees with n keys
- Merge Two Balanced Binary Search Trees
- Binary Tree to Binary Search Tree Conversion

**Related articles on Binary Search Tree:**

### 8. Heap:

A ** Heap **is a complete binary tree data structure that satisfies the heap property: for every node, the value of its children is less than or equal to its own value. Heaps are usually used to implement

**, where the smallest (or largest) element is always at the root of the tree.**

**priority queues****Important articles on****Heap:**

- Binary Heap
- Why is Binary Heap Preferred over BST for Priority Queue?
- Heap Sort
- K’th Largest Element in an array
- Sort an almost sorted array
- Binomial Heap
- Fibonacci Heap
- Tournament Tree (Winner Tree) and Binary Heap

**Related articles on Heap:**

### 9. Hashing:

** Hashing** is a technique that generates a fixed-size output (hash value) from an input of variable size using mathematical formulas called

**. Hashing is used to determine an index or location for storing an item in a data structure, allowing for efficient retrieval and insertion.**

**hash functions****Important articles on****Hashing:**

- Hashing Introduction
- Separate Chaining for Collision Handling
- Open Addressing for Collision Handling
- Print a Binary Tree in Vertical Order
- Find whether an array is subset of another array
- Union and Intersection of two Linked Lists
- Find a pair with given sum
- Check if a given array contains duplicate elements within k distance from each other
- Find Itinerary from a given list of tickets
- Find number of Employees Under every Employee

**Related articles on Hashing:**

### 10. Graph:

** Graph **is a collection of nodes connected by edges. Graphs are mostly used to represent networks, such as social networks or transportation networks.

**Important articles on****Graph:**

- Graph and its representations
- Breadth First Traversal for a Graph
- Depth First Traversal for a Graph
- Applications of Depth First Search
- Applications of Breadth First Traversal
- Detect Cycle in a Directed Graph
- Detect Cycle in Graph using DSU
- Detect cycle in an Undirected Graph using DFS
- Longest Path in a Directed Acyclic Graph
- Topological Sorting
- Check whether a given graph is Bipartite or not
- Snake and Ladder Problem
- Minimize Cash Flow among a given set of friends who have borrowed money from each other
- Boggle (Find all possible words in a board of characters)
- Assign directions to edges so that the directed graph remains acyclic

**Related articles on Graph:**

## Advanced Data Structure:

Below are some advance Data Structure:

**1. Advanced Lists:**

**1. Advanced Lists:**

** Advanced Lists **is a data structure that extends the functionality of a standard list. Advanced lists may support additional operations, such as finding the minimum or maximum element in the list, or rotating the list.

**Important articles on****Advanced Lists:**

- Memory efficient doubly linked list
- XOR Linked List – A Memory Efficient Doubly Linked List | Set 1
- XOR Linked List – A Memory Efficient Doubly Linked List | Set 2
- Skip List | Set 1 (Introduction)
- Self Organizing List | Set 1 (Introduction)
- Unrolled Linked List | Set 1 (Introduction)

**2. Segment Tree:**

**2. Segment Tree:**

** Segment Tree** is a tree data structure that allows for efficient range queries on an array. Each node in the segment tree represents a range of elements in the array, and the value stored in the node is some aggregate value of the elements in that range.

**Important articles on****Segment Tree:**

- Segment Tree | Set 1 (Sum of given range)
- Segment Tree | Set 2 (Range Minimum Query)
- Lazy Propagation in Segment Tree
- Persistent Segment Tree | Set 1 (Introduction)

**Related articles on Segment Tree:**

**3. Trie:**

**3. Trie:**

** Trie **is a tree-like data structure that is used to store strings. Each node in the trie represents a prefix of a string, and the children of a node represent the different characters that can follow that prefix.

**are often used for efficient string matching and searching.**

**Tries****Important articles on****Trie:**

- Trie | (Insert and Search)
- Trie | (Delete)
- Longest prefix matching – A Trie based solution in Java
- Print unique rows in a given boolean matrix
- How to Implement Reverse DNS Look Up Cache?
- How to Implement Forward DNS Look Up Cache?

**Related articles on**** Trie**:

**4. Binary Indexed Tree:**

**4. Binary Indexed Tree:**

** Binary Indexed Tree** is a data structure that allows for efficient range queries and updates on an array. Binary indexed trees are often used to compute prefix sums or to solve range query problems.

**Important articles on****Binary Indexed Tree:**

- Binary Indexed Tree
- Two Dimensional Binary Indexed Tree or Fenwick Tree
- Binary Indexed Tree : Range Updates and Point Queries
- Binary Indexed Tree : Range Update and Range Queries

**Related articles on**** Binary Indexed Tree**:

**5. Suffix Array and Suffix Tree**:

**5. Suffix Array and Suffix Tree**

** Suffix Array and Suffix Tree** is a data structures that are used to efficiently search for patterns within a string.

**and**

**Suffix arrays****are mostly used in bioinformatics and text processing applications.**

**suffix trees****Important articles on****Suffix Array and Suffix Tree:**

- Suffix Array Introduction
- Suffix Array nLogn Algorithm
- kasai’s Algorithm for Construction of LCP array from Suffix Array
- Suffix Tree Introduction
- Ukkonen’s Suffix Tree Construction – Part 1
- Ukkonen’s Suffix Tree Construction – Part 2
- Ukkonen’s Suffix Tree Construction – Part 3
- Ukkonen’s Suffix Tree Construction – Part 4,
- Ukkonen’s Suffix Tree Construction – Part 5
- Ukkonen’s Suffix Tree Construction – Part 6
- Generalized Suffix Tree
- Build Linear Time Suffix Array using Suffix Tree
- Substring Check
- Searching All Patterns
- Longest Repeated Substring,
- Longest Common Substring, Longest Palindromic Substring

**Related articles on Suffix Array and Suffix Tree:**

**6. AVL Tree:**

**6. AVL Tree:**

** AVL tree** is a self-balancing binary search tree that maintains a balanced height.

**are mostly used when it is important to have efficient search and insertion operations.**

**AVL trees****Important articles on****AVL Tree:**

**7. Splay Tree:**

**7. Splay Tree:**

** Splay Tree** is a self-balancing binary search tree that moves frequently accessed nodes to the root of the tree.

**are mostly used when it is important to have fast access to recently accessed data.**

**Splay trees****Important articles on****Splay Tree:**

**8. B Tree:**

**8. B Tree:**

** B Tree** is a balanced tree data structure that is used to store data on disk.

**are mostly used in database systems to efficiently store and retrieve large amounts of data.**

**B trees****Important articles on****B Tree:**

**9. Red-Black Tree:**

**9. Red-Black Tree:**

** Red-Black Tree** is a self-balancing

**that maintains a balance between the number of**

**binary search tree****and**

**black****nodes.**

**red****trees are mostly used when it is important to have efficient search and insertion operations.**

**Red-black****Important articles on****Red-Black Tree:**

- Red-Black Tree Introduction
- Red Black Tree Insertion.
- Red-Black Tree Deletion
- Program for Red Black Tree Insertion

**Related articles on Red-Black Tree:**

**10. K Dimensional Tree:**

**10. K Dimensional Tree:**

** K Dimensional Tree** is a tree data structure that is used to store data in a multidimensional space.

**dimensional trees are mostly used for efficient range queries and nearest neighbor searches.**

**K****Important articles on K Dimensional Tree:**

**Others Data Structure:**

- Treap (A Randomized Binary Search Tree)
- Ternary Search Tree
- Interval Tree
- Implement LRU Cache
- Sort numbers stored on different machines
- Find the k most frequent words from a file
- Given a sequence of words, print all anagrams together
- Tournament Tree (Winner Tree) and Binary Heap
- Decision Trees – Fake (Counterfeit) Coin Puzzle (12 Coin Puzzle)
- Spaghetti Stack
- Data Structure for Dictionary and Spell Checker?
- Cartesian Tree
- Cartesian Tree Sorting
- Sparse Set
- Centroid Decomposition of Tree
- Gomory-Hu Tree
- Recent Articles on Advanced Data Structures.

**Misc:**

- Commonly Asked Data Structure Interview Questions | Set 1
- A data structure for n elements and O(1) operations
- Expression Tree