Scribd
Upload
4 views3 pages

DSA Short Notes Without Stack Tree

The document provides short notes on various data structures and algorithms, including Quick Sort, Merge Sort, Hashing, Queue, Linked List, and Searching Techniques. It outlines definitions, algorithms, time complexities, and applications for each topic. Additionally, it discusses time and space complexity concepts.

Uploaded by

stylish725035
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views3 pages

DSA Short Notes Without Stack Tree

The document provides short notes on various data structures and algorithms, including Quick Sort, Merge Sort, Hashing, Queue, Linked List, and Searching Techniques. It outlines definitions, algorithms, time complexities, and applications for each topic. Additionally, it discusses time and space complexity concepts.

Uploaded by

stylish725035
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

DSA Short Notes with Answers (Excluding Stack & Tree)

1. QUICK SORT

Definition: Quick Sort is a divide-and-conquer algorithm that selects a pivot and partitions the array.

Algorithm (Brief):

1. Choose pivot element.

2. Partition array such that elements < pivot on left and > pivot on right.

3. Recursively apply to subarrays.

Time Complexity:

Best & Average: O(n log n)

Worst: O(n^2)

2. MERGE SORT

Definition: Merge Sort divides the array into halves and merges them in sorted order.

Algorithm (Steps):

- Divide array into halves

- Recursively sort both halves

- Merge sorted halves

Time Complexity: O(n log n) in all cases

3. HASHING

Definition: Hashing maps keys to values using a hash function.

Collision Resolution Techniques:

- Linear Probing: Check next slot

- Quadratic Probing: Use quadratic gap

- Chaining: Use linked list at each index


4. QUEUE & CIRCULAR QUEUE

Queue: FIFO (First In First Out) data structure.

Operations: Enqueue, Dequeue

Circular Queue: Last index is connected to first. Prevents unused space.

Front and Rear are updated in circular manner using modulo operator.

5. LINKED LIST

Types:

- Singly Linked List: One pointer (next)

- Doubly Linked List: Two pointers (next and prev)

- Circular Linked List: Last node points to first

Basic Operations:

- Insertion (at beginning, middle, end)

- Deletion

- Traversal

6. SEARCHING TECHNIQUES

Linear Search:

- Search one by one

- Time: O(n)

Binary Search:

- Only for sorted arrays

- Divide array into halves each time

- Time: O(log n)
7. TIME & SPACE COMPLEXITY

Time Complexity:

- Measures time taken vs input size.

Common: O(1), O(n), O(log n), O(n^2)

Space Complexity:

- Memory used by algorithm.

- Includes input, output, temp variables.

8. APPLICATIONS OF DATA STRUCTURES

Array: Static data, indexing

Linked List: Dynamic memory allocation

Stack: Expression parsing, backtracking

Queue: Scheduling, OS buffers

Tree: Database indexing, hierarchy

Graph: Networking, maps

Hashing: Database lookups, caching

You might also like