DSA IMPORTANT NOTES

 📘 DATA STRUCTURES – COMPLETE NOTES (For Students)

🔹 Introduction to Data Structures

A Data Structure is a method of organizing, storing, and managing data in a computer so that it can be accessed and modified efficiently.

Data structures are very important in computer science because they help in efficient data processing and problem solving.

🔹 Why Data Structures are Important?

Efficient data storage

Faster data access

Better memory utilization

Easy data manipulation

Improves program performance

Foundation for algorithms and software development

🔹 Types of Data Structures

Data structures are mainly classified into two types:

1. Primitive Data Structures

These are basic data types.

Integer

Float

Character

Double

Example:

Copy code

C

int x = 10;

2. Non-Primitive Data Structures

These are further divided into:

a) Linear Data Structures

Array

Stack

Queue

Linked List

b) Non-Linear Data Structures

Tree

Graph

🔹 ARRAY

An array is a collection of elements of the same data type, stored in contiguous memory locations.

Example:

Copy code

C

int a[5] = {10, 20, 30, 40, 50};

Advantages of Array:

Easy and fast access using index

Simple to use

Disadvantages of Array:

Fixed size

Memory wastage

Insertion and deletion are difficult

🔹 STACK

A stack is a linear data structure that follows the LIFO (Last In First Out) principle.

Stack Operations:

Push – insert an element

Pop – remove an element

Peek – view the top element

Applications of Stack:

Function calls

Undo and Redo operations

Expression evaluation

Reversal of string

🔹 QUEUE

A queue is a linear data structure that follows the FIFO (First In First Out) principle.

Queue Operations:

Enqueue – insert an element

Dequeue – remove an element

Types of Queue:

Simple Queue

Circular Queue

Priority Queue

Double Ended Queue (Deque)

Applications of Queue:

CPU scheduling

Printer scheduling

Waiting line systems

🔹 LINKED LIST

A linked list is a linear data structure where elements are stored in nodes.

Each node contains:

Data

Address of the next node

Types of Linked List:

Singly Linked List

Doubly Linked List

Circular Linked List

Advantages:

Dynamic size

Efficient insertion and deletion

Disadvantages:

No direct access

Extra memory required for pointers

🔹 TREE

A tree is a non-linear hierarchical data structure.

Tree Terminology:

Root

Parent

Child

Leaf Node

Path

Height

Depth

🔹 BINARY TREE

A binary tree is a tree where each node has at most two children, called:

Left child

Right child

Applications of Binary Tree:

Expression evaluation

Searching

Sorting

File system representation

🔹 TREE TRAVERSAL

Traversal means visiting all the nodes of a tree.

Types of Tree Traversal:

Inorder Traversal (LNR)

Left → Node → Right

Preorder Traversal (NLR)

Node → Left → Right

Postorder Traversal (LRN)

Left → Right → Node

🔹 GRAPH

A graph is a non-linear data structure consisting of:

Vertices (nodes)

Edges (connections)

Types of Graph:

Directed Graph

Undirected Graph

Applications of Graph:

Social networks

Google Maps

Network routing

Web page linking

🔹 SEARCHING TECHNIQUES

1. Linear Search

Searches element one by one

Time Complexity: O(n)

2. Binary Search

Works only on sorted arrays

Time Complexity: O(log n)

🔹 SORTING TECHNIQUES

Sorting means arranging data in ascending or descending order.

Common Sorting Algorithms:

Bubble Sort

Selection Sort

Insertion Sort

Merge Sort

Quick Sort

🔹 APPLICATIONS OF DATA STRUCTURES

Operating Systems

Database Management Systems

Compiler Design

Artificial Intelligence

Machine Learning

Web Applications