ASSIGNMENT_DOCUMENTATION.md

Data Structures Assignment 1

Computer Science - First Year

---

Table of Contents

1. Primitive Type Declaration
2. Linear Static Structure (Array)
3. Linear Dynamic Structure (Linked List)
4. Non-Linear Structure (Binary Tree)
5. Data Structures and Algorithms Relationship

---

1. Primitive Type Declaration

File: primitive_type.c

Classification

Primitive Data Type - These are the basic building blocks of all data structures. They are built into the C language and store single values.

Memory Characteristics

• Contiguous Memory: Yes, each primitive variable occupies a fixed, continuous block of memory
• Size: Fixed size (int = 4 bytes, float = 4 bytes, char = 1 byte)
• Storage: Stored directly in memory (usually on the stack)

Real-World Applications

• Student ID numbers - stored as integers
• Product prices - stored as floats
• Grade letters - stored as characters
• Temperature readings - stored as floats
• Age of a person - stored as integers

How It Works

Primitive types are the simplest form of data storage. When you declare int val = 42, the computer allocates 4 bytes of memory and stores the number 42 directly in those bytes.

---

2. Linear Static Structure - Array

File: linear_static_array.c

Classification

Linear Static Data Structure

• Linear: Elements are arranged in a sequential order (one after another)
• Static: Size is fixed at compile time and cannot change during program execution

Memory Characteristics

• Contiguous Memory: YES - All elements are stored in consecutive memory locations
• Memory Layout: If arr[0] is at address 1000, then arr[1] is at 1004, arr[2] at 1008, etc.
• Access Speed: Very fast - O(1) time complexity for accessing any element

Real-World Applications

1. Student ID List - Fixed number of students in a classroom
2. Days of the Week - Always 7 days
3. Monthly Sales Data - 12 months in a year
4. Exam Scores - Fixed number of students taking an exam
5. Seat Numbers in a Theater - Fixed number of seats

Advantages

• Fast access to any element using index
• Simple to use and understand
• Memory efficient (no extra space for pointers)
• Good cache performance due to contiguous memory

Disadvantages

• Fixed size - cannot grow or shrink
• Insertion and deletion are expensive (need to shift elements)
• Memory waste if not all slots are used

---

3. Linear Dynamic Structure - Singly Linked List

File: linear_dynamic_linked_list.c

Classification

Linear Dynamic Data Structure

• Linear: Elements are arranged in a sequence (node1 → node2 → node3)
• Dynamic: Size can change during program execution (can add/remove nodes anytime)

Memory Characteristics

• Non-Contiguous Memory: YES - Nodes can be scattered anywhere in memory
• Memory Layout: Nodes are connected through pointers, not physical location
• Access Speed: Slower - O(n) time complexity for accessing elements
• Extra Memory: Each node needs extra space for the pointer (address of next node)

Real-World Applications

1. Browser History (Undo/Redo) - Can go back and forward
2. Music Playlist - Add or remove songs dynamically
3. Image Viewer - Navigate through photos (next/previous)
4. Train Carriages - Each carriage linked to the next
5. To-Do List Apps - Add or remove tasks anytime

Advantages

• Dynamic size - can grow or shrink as needed
• Easy insertion and deletion (just change pointers)
• No memory waste - uses exactly what's needed
• No need to declare size upfront

Disadvantages

• Slower access - must traverse from the beginning
• Extra memory for pointers
• No random access to elements
• More complex to implement than arrays

How It Works

Each node contains:

1. Data - The actual value (100, 200, 300)
2. Next pointer - Address of the next node

Memory layout example:

Node1 (at address 2000): data=100, next=5040
Node2 (at address 5040): data=200, next=7200
Node3 (at address 7200): data=300, next=NULL

---

4. Non-Linear Structure - Binary Tree

File: nonlinear_binary_tree.c

Classification

Non-Linear Data Structure

• Non-Linear: Elements are arranged in a hierarchy (parent-child relationship)
• Binary: Each node can have at most 2 children (left and right)

Memory Characteristics

• Non-Contiguous Memory: YES - Nodes are scattered in memory
• Memory Layout: Nodes connected through two pointers (left and right)
• Access Speed: Medium - O(log n) for balanced trees
• Extra Memory: Each node needs space for two pointers

Real-World Applications

1. File System Folders - Folders inside folders (hierarchy)
2. Organization Chart - CEO → Managers → Employees
3. Family Tree - Parents, children, grandchildren
4. Decision Trees - Yes/No questions leading to outcomes
5. HTML DOM Structure - Nested HTML elements

Advantages

• Efficient searching in balanced trees
• Represents hierarchical relationships naturally
• Multiple ways to traverse (inorder, preorder, postorder)
• Good for sorted data storage

Disadvantages

• More complex to implement
• Extra memory for two pointers per node
• Can become unbalanced (performance degrades)
• More difficult to understand for beginners

How It Works

Tree structure:

       50 (root)
      /  \
    30    70
  (left) (right)

Each node contains:

1. Data - The actual value
2. Left pointer - Address of left child
3. Right pointer - Address of right child

---

5. Data Structures and Algorithms Working Together

What Are Data Structures?

Data structures are ways to organize and store data in a computer's memory. Think of them as different types of containers:

• Arrays are like numbered boxes in a row
• Linked Lists are like train carriages connected together
• Trees are like family trees with branches

What Are Algorithms?

Algorithms are step-by-step instructions to solve a problem or perform a task. Think of them as recipes:

• Searching - Finding a specific item
• Sorting - Arranging items in order
• Inserting - Adding a new item
• Deleting - Removing an item

How They Work Together

1. Speed (Time Complexity)

Different data structures make algorithms faster or slower:

Example: Finding a student's grade

• Array: If you know the position, access is instant (O(1))
• Linked List: Must check each student one by one (O(n))
• Binary Search Tree: Can eliminate half the data each step (O(log n))

Real-World Analogy:

• Array = Finding a book on a numbered shelf (instant if you know the number)
• Linked List = Following a treasure map from clue to clue
• Tree = Playing "20 Questions" to narrow down the answer

2. Memory (Space Complexity)

Different data structures use different amounts of memory:

Example: Storing 100 student IDs

• Array: 100 × 4 bytes = 400 bytes (just the data)
• Linked List: 100 × (4 bytes data + 8 bytes pointer) = 1200 bytes
• Binary Tree: 100 × (4 bytes data + 16 bytes for 2 pointers) = 2000 bytes

Trade-off:

• Arrays use less memory but are rigid
• Linked lists use more memory but are flexible
• Trees use the most memory but enable fast searching

3. Choosing the Right Combination

Scenario 1: Student Grade List (Fixed Class Size)

• Data Structure: Array
• Why: Fixed number of students, need fast access
• Algorithm: Direct access by index
• Trade-off: Fast access, but can't easily add more students

Scenario 2: Browser Undo History

• Data Structure: Linked List
• Why: Unknown number of actions, frequent additions/deletions
• Algorithm: Insert at beginning, remove from beginning
• Trade-off: Flexible size, but slower to access middle items

Scenario 3: File System Search

• Data Structure: Binary Tree
• Why: Hierarchical structure, need fast searching
• Algorithm: Binary search
• Trade-off: Fast searching, but more complex to maintain

Key Principles

1. There's No Perfect Data Structure

   • Arrays are fast but inflexible
   • Linked Lists are flexible but slower
   • Trees are powerful but complex

2. Speed vs Memory Trade-off

   • More memory → Faster operations (e.g., hash tables)
   • Less memory → Slower operations (e.g., compressed data)

3. Choose Based on Your Needs

   • Lots of searching? → Use arrays or trees
   • Lots of inserting/deleting? → Use linked lists
   • Fixed size data? → Use arrays
   • Unknown size? → Use linked lists or trees

Simple Example: Managing a To-Do List

Using Array:

• Add task: Must shift all items → Slow
• Remove task: Must shift all items → Slow
• Access task: Direct access → Fast

Using Linked List:

• Add task: Just create new node → Fast
• Remove task: Just change pointers → Fast
• Access task: Must traverse list → Slow

Best Choice: Linked List (because to-do lists change frequently)

---

Summary Table

Feature	Array	Linked List	Binary Tree
Type	Linear Static	Linear Dynamic	Non-Linear
Memory	Contiguous	Non-Contiguous	Non-Contiguous
Size	Fixed	Flexible	Flexible
Access Speed	O(1) Fast	O(n) Slow	O(log n) Medium
Insert/Delete	O(n) Slow	O(1) Fast	O(log n) Medium
Memory Usage	Low	Medium	High
Use Case	Fixed-size data	Changing data	Hierarchical data

---

How to Compile and Run

Primitive Type:

gcc primitive_type.c -o primitive_type
./primitive_type

Linear Static Array:

gcc linear_static_array.c -o linear_static_array
./linear_static_array

Linear Dynamic Linked List:

gcc linear_dynamic_linked_list.c -o linear_dynamic_linked_list
./linear_dynamic_linked_list

Non-Linear Binary Tree:

gcc nonlinear_binary_tree.c -o nonlinear_binary_tree
./nonlinear_binary_tree

---

Key Takeaways for First-Year Students

1. Primitive types are the building blocks - they store single values
2. Arrays are great when you know the size and need fast access
3. Linked Lists are perfect when the size changes frequently
4. Trees are ideal for hierarchical data and efficient searching
5. Contiguous memory (arrays) is faster but less flexible
6. Non-contiguous memory (lists, trees) is flexible but uses more space
7. Data structures and algorithms must work together - the right structure makes algorithms faster

Remember: There's no "best" data structure - only the best one for your specific problem!

Good luck with your assignment! 🎓