Data Structure and Algorithms Study Notes

Introduction to Data Structures

• Data Structure: A specific way of organizing and managing data for efficient access and modification.

• Primitive Data Structures: Fundamental types supported by programming languages ($int$, $real$, $char$, $Boolean$).

• Non-Primitive Data Structures: Created using primitive types; categorized into linear and non-linear forms.

• Linear Data Structure: Elements arranged sequentially (e.g., Arrays, Stacks, Queues, Linked Lists).

• Non-Linear Data Structure: Represents hierarchical relationships (e.g., Trees, Graphs).

• Basic Operations: Creating, Destroying, Insertion, Deletion, Traversal, Searching, Sorting, Merging, Updating, and Accessing.

Pointers and Memory Management

• Pointer: A variable storing the memory address of another variable. Declared using the $*$ operator (e.g., $int *pa$).

• Operators:

  • Address-of (&): Retrieves memory address of a variable.

  • Dereferencing ($*$): Accesses the value stored at the address a pointer holds.

• Pointer Arithmetic: Supports increment ($ptr++$), decrement ($ptr--$), adding an integer, and subtracting two pointers belonging to the same array.

• Static Memory Allocation: Memory space fixed at compile time; size cannot change during execution.

• Dynamic Memory Allocation (DMA): Memory allocated at run time from the heap.

  • $malloc(size)$: Allocates a single block of uninitialized memory.

  • $calloc(n, size)$: Allocates multiple blocks initialized to zero.

  • $realloc(ptr, new\_size)$: Resizes previously allocated memory.

  • $free(ptr)$: Deallocates memory to prevent leaks.

• Common Issues:

  • Dangling Pointer: Points to a memory location that has already been freed.

  • Memory Leak: Happens when allocated memory is never released by $free()$.

Recursion

• Definition: A function calling itself to solve reduced versions of a problem.

• Components:

  • Base Case: The stopping condition to prevent infinite recursion.

  • Recursive Case: The part where the function calls itself.

• Types:

  • Direct Recursion: Function calls itself directly.

  • Indirect Recursion: Function A calls B, and B calls A.

  • Variations: Linear, Tail, Head, Tree, and Nested recursion.

• Examples: Factorial ($n! = n \times (n-1)!$), Fibonacci series, and Greatest Common Divisor (GCD).

• Tower of Hanoi: A recursive puzzle where the minimum moves for $n$ disks is $2^n - 1$.

File Management System

• File: A collection of related data stored on disk, accessed via a pointer of type $FILE$.

• Standard Functions:

  • $fopen()$ and $fclose()$: Open and close file streams.

  • Formatting: $fscanf()$ and $fprintf()$.

  • Character I/O: $getc()$, $putc()$, and $ungetc()$.

  • Integer I/O: $getw()$ and $putw()$.

• Error Handling:

  • $feof()$: Checks if the end-of-file has been reached.

  • $ferror()$: Detects errors during file operations.

Searching and Sorting

• Searching:

  • Linear Search: Sequential check from start to end; works on unsorted data.

  • Binary Search: Divide-and-conquer method for sorted arrays; compares key with middle element.

• Sorting:

  • Bubble Sort: Swaps adjacent elements if in the wrong order.

  • Selection Sort: Repeatedly picks the smallest element and swaps it into position.

  • Insertion Sort: Inserts elements into their proper place individually.

  • Quick Sort: Uses a pivot to partition the array.

  • Merge Sort: Recursively divides arrays in half and merges them back in order.

Stacks and Queues

• Stack: Last In First Out (LIFO) structure. Operations: $Push$ (insert at Top) and $Pop$ (delete from Top).

• Expressions:

  • Infix: $A + B$

  • Prefix: $+ AB$ (Polish notation)

  • Postfix: $AB +$ (Reverse Polish notation)

• Queue: First In First Out (FIFO) structure. Insertion happens at the $Rear$; deletion at the $Front$.

• Queue Types:

  • Simple Queue: Standard linear structure.

  • Circular Queue: Last position connects to the first, enabling memory reuse.

  • Priority Queue: Service based on assigned priority values.

  • Deque (Double Ended Queue): Insertion and deletion allowed at both ends.

Linked Lists

• Linked List: A linear data structure of nodes stored at non-contiguous memory locations.

• Node Structure: Comprised of a Data field and a Link (pointer) to the next node.

• Types:

  • Singly Linked List: One direction via a next pointer.

  • Doubly Linked List: Two pointers (previous and next) allow bidirectional traversal.

  • Circular Linked List: The last node links back to the head.

• Empty List: Represented by a head pointer set to $NULL$.

Trees

• Tree: A hierarchical structure with a root node and children nodes.

• Terminologies:

  • Degree: Number of subtrees associated with a node.

  • Leaf Node: A terminal node with degree zero.

  • Level/Height: Root is at level 0; height is the maximum level in the tree.

• Binary Tree: Each node has a maximum of two children (Left and Right subtrees).

• Traversal Techniques:

  • Preorder: Root \rightarrow Left \rightarrow Right.

  • Inorder: Left \rightarrow Root \rightarrow Right.

  • Postorder: Left \rightarrow Right \rightarrow Root.