Data Structure notes

Linear Data Non-linear Data

Structure Structure

1 Elements are arranged sequentially, one after

. another.

2 Traversed in a single run (one

. path).

Simple and easy to

3
implement.

4 Memory may be wasted (like in

. arrays).

5 Array, Stack,
. Queue

Non-linear Data Structure

1 Elements are arranged hierarchically or in a network.
2. requires multiple paths (not single).
3. More complex to implement.
4. Memory is efficiently utilized (dynamic allocation).
5. Linked List, Tree and Graph.

Array in Data Structure

● Definition:
An array is a collection of elements of the same data
type, stored in contiguous memory locations.
Each element can be accessed directly using an index
(position number).
● Key Features:
1. Stores multiple values of the same type (e.g., all
integers or all characters).
2. Elements are stored in continuous memory blocks.
3. Indexing starts from 0 (in most languages like C, C+
+, Java, Python).
4. Provides fast access to elements (O(1) time
complexity).
● Syntax Example (C/C++):
● int arr[5] = {10, 20, 30, 40, 50};

Here:
o arr[0] = 10
o arr[1] = 20

o … and so on.

● Types of Arrays:
0. One-dimensional array → [10, 20, 30, 40]
1. Two-dimensional array (Matrix) →
2. 1 2 3
3. 4 5 6
4. 7 8 9
5. Multi-dimensional array → arrays of arrays.
● Real-life Example:
o A row of seats in a movie theater (each seat has a
fixed position = index).
o A list of student roll numbers
Difference between Binary search and Linear Search.

Binary Search.
1. Works only on sorted data (ascending or descending).
2. Divides the search range into two halves repeatedly
(divide & conquer).
3. Time complexity: O(log n) → very fast for large
datasets.
4. Implementation: More complex than linear search.
5. Example: Searching a word in a dictionary (you open
the middle page, then decide left or right).

🔹 Linear Search
1. Works on unsorted or sorted data.
2. Checks each element one by one until the target is
found.
3. Time complexity: O(n) → slower for large datasets.
4. Implementation: Very simple and easy.
 5. Example: Searching a name in a random list (checking
line by line).

Time Complexity in Data Structure

Definition
Time complexity is the amount of time an algorithm takes
to run as a function of the input size (n).
It helps us analyze the efficiency of an algorithm, independent
of machine, compiler, or language.

Types of Time Complexity

1. Best Case (Ω - Omega Notation)
o The minimum time an algorithm takes for an input.
o Example: In Linear Search, if the element is found
at the first position, time complexity is Ω(1).
2. Average Case (Θ - Theta Notation)
o The expected time for an algorithm over all inputs.
o Example: In Linear Search, on average, we may
find the element in the middle, so Θ(n/2) ≈ Θ(n).
3. Worst Case (O - Big-O Notation)
o The maximum time an algorithm may take.
 o Example: In Linear Search, if the element is at the
last position or not present at all, complexity is
O(n).

Common Time Complexities

Here are the most common ones (from fastest to slowest):
Time
Name Example
Complexity
Constant Accessing array element by
O(1)
Time index
O(log n) Logarithmic Binary Search
O(n) Linear Linear Search
O(n log n) Linearithmic Merge Sort, Quick Sort (avg)
O(n²) Quadratic Bubble Sort, Insertion Sort
O(n³) Cubic Matrix multiplication (naïve)
O(2ⁿ) Exponential Solving recursive Fibonacci
Traveling Salesman Problem
O(n!) Factorial
(Brute Force)

Why Time Complexity Matters?

● Helps in comparing algorithms without coding them.

● Shows scalability → how well an algorithm performs as

data grows.
 ● Crucial in big data, machine learning, and competitive
programming.

Graphical Understanding
● O(1) → Flat line (no growth).

● O(log n) → Grows very slowly.

● O(n) → Straight line growth.
● O(n²) → Steep curve (bad for large inputs).
● O(2ⁿ), O(n!) → Explodes very fast (impractical for large
inputs).

In short:
● Time Complexity = Function of input size (n).
● Three cases: Best (Ω), Average (Θ), Worst (O).
● Always try to design algorithms with lower order of
complexity.

Linked List
Linked List in Data Structure

Definition
A Linked List is a linear data structure in which elements
(called nodes) are stored in non-contiguous memory
locations and connected using pointers.
Each node has two parts:
1. Data → stores the actual information.
 2. Pointer (link) → stores the address of the next node.

🔹 Structure of a Node
In C++-like syntax:
class Node {
int data;
Node* = new node()
};

Types of Linked List

1. Singly Linked List
o Each node points to the next node only.
o Last node points to NULL.
o Example: 10 → 20 → 30 → NULL
2. Doubly Linked List
o Each node has two pointers:
▪ One pointing to the next node
One pointing to the previous node
Example: NULL ← 10 ⇄ 20 ⇄ 30 → NULL
▪

3. Circular Linked List

o The last node points back to the first node instead
of NULL.
o Can be singly or doubly circular.
o Example: 10 → 20 → 30 → 10
4. Doubly Circular Linked List
o Both next and previous pointers form a circle.
Operations on Linked List
1. Traversal → Visiting each node to process data.
2. Insertion → Adding a new node.
o At beginning
o At end
o At specific position
3. Deletion → Removing a node.
o From beginning
o From end
o Specific node
4. Searching → Finding an element by value.
5. Updation → Changing the value of a node.

Advantages of Linked List

1. Dynamic memory allocation (size can grow/shrink).
2. Efficient insertion and deletion (no shifting like arrays).
3. Can implement advanced data structures like stacks,
queues, graphs.

Disadvantages of Linked List

1. Extra memory needed for pointer in each node.
 2. Sequential access only (no random access like arrays).
3. Slower traversal compared to arrays.
4. More complex implementation.

Applications of Linked List

● Implementing Stacks & Queues
● Graphs (Adjacency List representation)
● Dynamic memory allocation (malloc/free in C use
linked structures)
● Music player playlists, image viewers (Next/Previous
buttons)
● Undo/Redo functionality in editors

🔹 Time Complexity
Singly Linked Doubly Linked
Operation
List List
Traversal O(n) O(n)
Insertion
O(1) O(1)
(begin)
Insertion (end) O(n) O(1) with tail ptr
Deletion
O(1) O(1)
(begin)
Deletion (end) O(n) O(1) with tail ptr
 Singly Linked Doubly Linked
Operation
List List
Searching O(n) O(n)

In short:
● Linked List = Collection of nodes connected by pointers.
● Flexible size, easy insertion/deletion.
● Variants: Singly, Doubly, Circular.
● Applications: Queues, Graphs, Playlists, Undo/Redo,
Memory management.
Stack and Queue
STACK and QUEUE in Data Structure

1. STACK Definition
A Stack is a linear data structure that follows the LIFO (Last
In First Out) principle.
● The element inserted last is removed first.
● Think of a stack of plates: you put plates on top, and
remove from the top.

Operations on Stack
1. Push(x) → Insert an element on top.
2. Pop() → Remove the top element.
3. Peek/Top() → View the top element without removing.

Implementation
 ● Array (fixed size, overflow possible)
● Linked List (dynamic size)

Time Complexity of Stack

Operatio Time
n Complexity
Push O(1)
Pop O(1)
Peek O(1)
Traversal O(n)
Applications of Stack
● Expression evaluation (Postfix, Prefix, Infix conversions)
● Function calls (recursion uses system stack)
● Undo/Redo operations in editors
● Backtracking algorithms (e.g., maze solving)
● Browser history (back button)

2. QUEUE Definition
A Queue is a linear data structure that follows the FIFO
(First In First Out) principle.
● The element inserted first is removed first.
● Think of a queue at a ticket counter: first person enters
→ first person served.
Operations on Queue
1. Enqueue(x) → Insert element at the rear (end).
2. Dequeue() → Remove element from the front.
3. Peek/Front() → View the front element.
4. isEmpty() → Check if queue is empty.
5. isFull() → Check if queue is full (in array
implementation).

Types of Queue
1. Simple Queue → Normal FIFO.
2. Circular Queue → Connects rear to front (efficient
memory use).
3. Deque (Double Ended Queue) → Insert/delete from
both ends.
4. Priority Queue → Elements served based on priority,
not position.

Implementation
● Array (fixed size, may cause wastage if not circular).
● Linked List (dynamic, no wastage).

Time Complexity of Queue

Operatio Time
n Complexity
Enqueue O(1)
Dequeue O(1)
Peek O(1)
Traversal O(n)

✅ Applications of Queue
● CPU scheduling (Round Robin, FCFS)
● Disk scheduling
● Order processing systems
● Printers (spooling)
● Networking (data packets, buffering)
● Call center systems (first caller served first)

📊 Stack vs Queue (Quick Comparison)

Feature Stack (LIFO) Queue (FIFO)
Access order Last in, First out First in, First out
Insertion
Top only Rear (end)
point
Deletion
Top only Front
point
Undo in text Ticket counter
Example
editor line
✅ In short:
● Stack → LIFO → "Plates in a stack" → Used in
recursion, undo, backtracking.
● Queue → FIFO → "People in a line" → Used in
scheduling, printers, communication.