Data Structures and Algorithms PCCST303 KTU 2024 scheme- Dr Binu V P

  🔄 What is a Circular Linked List? A Circular Linked List (CLL) is a variation of a linked list where the last node points back to the first node , forming a circular loop . 🧠 Key Points: There is no NULL at the end . It can be singly or doubly circular. In singly circular , each node has a pointer to the next node only. In doubly circular , each node has pointers to both next and previous nodes . For this lesson, we’ll focus on Singly Circular Linked List . 🎯 Applications of Circular Linked List Circular queues Round-robin schedulers (e.g., CPU scheduling) Multiplayer games where turn rotation is needed Continuous loop playback of media 📘 Structure of a Node (Singly Circular) struct Node { int data; struct Node * next ; }; In a CLL: If there is only one node , its next points to itself . In general, the last node's next points to the first node . ✅ Basic Operations in Circular Linked List Insertion at the end I...

  🧹 Garbage Collection and Compaction 1. What is Garbage Collection? Garbage Collection is the process of identifying and reclaiming memory that is no longer in use by any program. After a process releases memory (explicitly or automatically), that memory becomes "garbage" if not reclaimed. Garbage collection frees up this memory so that it can be used for new allocations . Key idea : Automatically clean unused memory blocks . ✨ Example: Suppose memory blocks are: Block Address           Size           Used/Free 1000           200           Used 1200           150           Free 1350           300           Used 1650           100           Free 1750    ...

  Tree Data Structure What is a Tree? A tree is a non-linear data structure made up of nodes connected by edges . It is used to represent hierarchical relationships (like file systems, family trees, organization charts). A tree starts with a special node called the root , and every node (except the root) has exactly one parent . Nodes can have zero or more children . Definition: A tree is a collection of nodes where: One node is designated as the root . Every other node is connected by a directed edge from exactly one other node (its parent ). There are no cycles (it is an acyclic structure). Basic Terms in Trees Pic Courtesy: Geeksforgeeks Term Description Node A basic unit containing data and links to other nodes. Root The topmost node (starting point) of the tree. Parent A node that has a child node. Child A node that descends from another node (parent). Leaf Node A node with no children. Edge A link between a parent and a child. Subtree A s...

  🌳 What is a Binary Tree? A binary tree is a special type of tree where each node has at most two children : Left child Right child ✅ It is hierarchical and recursive in nature. 🔥 Types of Binary Trees There are several special types of binary trees based on structure: 1. Full Binary Tree Every node has 0 or 2 children . (No node with only 1 child) 2. Perfect Binary Tree It is a full binary tree where all leaf nodes are at the same level . 3. Complete Binary Tree All levels are completely filled except possibly the last level , which is filled from left to right . 4. Balanced Binary Tree The height difference between left and right subtree for every node is at most 1 . Examples: AVL Tree , Red-Black Tree . 5. Degenerate (or Skewed) Tree Every parent has only one child . Two types: Left-skewed tree (only left child) Right-skewed tree (only right child) 🔵 Summary Table Type of Tree Key Characteristics Full Binary Tree    ...

  Different Methods to Represent a Tree There are three major ways to represent a tree in programming: Method Description Best Used For 1. Parent Array Representation Store parent of each node in an array. Simple, static trees. 2. Linked Representation (Nodes and Pointers) Each node has pointers to its children. Dynamic trees, flexible structure. 3. Adjacency List Representation Represent tree as a graph. Each node points to a list of children. Trees with many children per node. 1. Parent Array Representation Idea : Maintain an array parent[i] where each index i represents a node, and parent[i] gives the index of its parent node. Root has a parent marked -1 . Example Node      A B C D E F Index           0 1 2 3 4 5 Parent Array      -1 0 0 1 1 2 A is the root (parent = -1) B and C are children of A D and E are children of B F is child of C ✅ Advantage : Simple and memory efficient. ❌ Disad...

  Binary Tree Representations There are two main ways to represent a binary tree: Method Description 1. Array Representation Tree is stored as an array (indexing rules are used). 2. Linked Representation Each node has pointers to its left and right child. 1. 📦 Array Representation of Binary Tree In this method: The tree is stored in a one-dimensional array . Each node's position depends on the index of its parent. ✅ Index Rules: If a node is stored at index i : Left Child → stored at index 2i + 1 Right Child → stored at index 2i + 2 Parent → stored at index (i - 1)/2 (integer division) ✏️ Example Let's consider this binary tree: A / \ B C / \ / D E F Store in array (level order): Index 0 1 2 3 4 5 Value A B C D E F Thus: A at index 0 B at index 1 → left child of A C at index 2 → right child of A D at index 3 → left child of B E at index 4 → right child of B F at index 5 → ...