šŸ“š DSA Unit 2 - Premium Master Notes

Linked Lists ā€¢ Trees ā€¢ Hashing

Compiled & Formatted by Ankush Raj

ā­ CHAPTER 2.1 ā€” LINKED LISTS
šŸŒŸ 1. What is a Linked List? (Clear Explanation)

A Linked List is a dynamic data structure used to store a collection of elements. Unlike arrays, a linked list does not store elements in continuous memory locations.

Instead, it is made of several small parts called nodes.

šŸ”ø Each node contains:
ā€¢ Data ā€“ the actual value
ā€¢ Pointer (Reference) ā€“ the address of the next node

So nodes are connected through pointers, forming a chain.

Example (Imagine a chain):
[10 | next] ā†’ [20 | next] ā†’ [30 | next] ā†’ NULL
ā­ Why do we use Linked Lists?
āœ” The size can grow or shrink at runtime
āœ” No memory is wasted
āœ” Insertion and deletion are fast (no shifting like arrays)
ā­ Limitations
āœ˜ Searching is slow ā†’ O(n)
āœ˜ Extra memory for pointers
āœ˜ Cannot access elements directly by index
šŸŒŸ 2. Types of Linked Lists
šŸ”¹ 1) Singly Linked List (SLL)

Each node has one pointer which points to the next node.

[data | next] ā†’ [data | next] ā†’ NULL

Features:

ā€¢ Can move forward only
ā€¢ Simple and memory-efficient
šŸ”¹ 2) Doubly Linked List (DLL)

Each node has two pointers: one for the next node and one for the previous node.

NULL ā† [prev | data | next] ā†’ [prev | data | next] ā†’ NULL

Features:

ā€¢ Can move both forward and backward
ā€¢ Faster deletion but uses more memory
šŸ”¹ 3) Circular Linked List (CLL)

The last node points back to the first node.

A ā†’ B ā†’ C ā†’ A (again)

Uses:

ā€¢ Round-robin scheduling
ā€¢ Repeated processes
šŸŒŸ 3. Operations on Linked List
šŸ”µ Insertion

1. Insert at Beginning

New node ā†’ next = head
head = new node
Time: O(1)

2. Insert at End

Traverse to last node
last.next = new node
Time: O(n)

3. Insert After a Given Node

new.next = target.next
target.next = new
Time: O(1) (after finding target)
šŸ”µ Deletion

1. Delete First Node

head = head.next
Time: O(1)

2. Delete Last Node

Traverse to second-last node ā†’ next = NULL
Time: O(n)

3. Delete a Specific Value

Search + re-link pointers
Time: O(n)
šŸ”µ Searching

Visit nodes one-by-one until the element is found. Time: O(n)

šŸŒŸ 4. Stack using Linked List

A stack follows LIFO (Last In First Out). The head of the linked list works as the top of the stack.

Operations:

ā€¢ push() ā†’ insert at head
ā€¢ pop() ā†’ delete head
ā€¢ peek() ā†’ return head element

All operations: O(1)

šŸŒŸ 5. Queue using Linked List

A queue follows FIFO (First In First Out). Use two pointers:

ā€¢ front ā†’ first node
ā€¢ rear ā†’ last node

Operations:

ā€¢ enqueue() ā†’ insert at rear
ā€¢ dequeue() ā†’ delete from front

All operations: O(1)

ā­ CHAPTER 2.2 ā€” TREES
šŸŒŸ 1. What is a Tree?

A tree is a non-linear, hierarchical data structure consisting of nodes connected by edges.

Basic terms:

ā€¢ Root ā€“ topmost node
ā€¢ Parent ā€“ node above another
ā€¢ Child ā€“ node below another
ā€¢ Leaf ā€“ no children
ā€¢ Height ā€“ longest path from root to leaf

Trees are used to represent hierarchical structures like:

āœ” file systems
āœ” organization charts
āœ” decision structures
šŸŒŸ 2. Binary Tree

A Binary Tree is a tree in which each node has at most 2 children.

Types:

ā€¢ Full Binary Tree ā€“ each node has 0 or 2 children
ā€¢ Complete Binary Tree ā€“ every level is filled left to right
ā€¢ Perfect Binary Tree ā€“ all leaves at same level
šŸŒŸ 3. Binary Search Tree (BST)

A BST is a binary tree that follows a sorted structure:

Left child < Root < Right child

Operations:

ā€¢ Search ā†’ O(log n)
ā€¢ Insert ā†’ O(log n)
ā€¢ Delete ā†’ O(log n)
Deletion cases:
1. Node with no child

2. Node with one child

3. Node with two children ā†’ replace with inorder successor
šŸŒŸ 4. Tree Traversals
šŸ”¹ Depth-First Traversals

1) Inorder (Left ā†’ Root ā†’ Right)

Gives sorted output for BST

2) Preorder (Root ā†’ Left ā†’ Right)

Used for copying tree

3) Postorder (Left ā†’ Right ā†’ Root)

Used for deleting a tree
šŸ”¹ Breadth-First Traversal (Level-order)
ā€¢ Uses Queue
ā€¢ Visits level by level
šŸŒŸ 5. Balanced Search Trees

A balanced tree maintains height close to log n, so operations remain efficient.

Examples:

ā€¢ AVL Tree
ā€¢ Red-Black Tree
ā€¢ B-Tree
šŸŒŸ 6. Introduction to B-Tree

A B-tree is a multi-way search tree used in databases and file systems.

Features:

ā€¢ One node contains multiple keys
ā€¢ Children also multiple
ā€¢ Height remains low ā†’ fast disk access
šŸŒŸ 7. Heap and Heap Sort
šŸ”¹ Heap

A heap is a complete binary tree that satisfies:

ā€¢ Max-heap: parent ā‰„ children
ā€¢ Min-heap: parent ā‰¤ children

Root contains the largest or smallest value.

šŸ”¹ Heap Sort Steps
1. Build a max heap
2. Swap root with last element
3. Reduce heap size
4. Heapify remaining
5. Repeat
Time:
ā€¢ Build heap ā†’ O(n)
ā€¢ Heap sort ā†’ O(n log n)
ā­ CHAPTER 2.3 ā€” HASHING
šŸŒŸ 1. What is Hashing?

Hashing is a technique to store data using a hash function that converts a key ā†’ index.

index = hash(key)

This allows O(1) average search, insert, delete.

Used in:

āœ” databases
āœ” hash tables
āœ” compiler symbol tables
šŸŒŸ 2. Collision

A collision occurs when two keys get the same index.

šŸŒŸ 3. Collision Handling Methods
šŸ”¹ 1) Chaining
ā€¢ Each index stores a linked list
ā€¢ Simple and widely used
šŸ”¹ 2) Open Addressing

a) Linear Probing

Check next index: h(k) + i

b) Quadratic Probing

Use squares: h(k) + iĀ²

c) Double Hashing

Use second hash function: h1(k) + i*h2(k)
Most efficient among probing methods.
ā­ FINAL EXAM ONE-LINERS
āœ” SLL ā†’ forward only
āœ” DLL ā†’ backward + forward
āœ” Stack LL ā†’ head operations
āœ” Queue LL ā†’ front-rear
āœ” BST ā†’ left < root < right
āœ” Inorder ā†’ sorted BST
āœ” Heap ā†’ complete binary tree
āœ” Hashing ā†’ O(1) average
āœ” Chaining ā†’ linked list inside table
āœ” Double hashing ā†’ two hash functions