================================================================================
                    DATA STRUCTURES AND ALGORITHMS
                    HOMEWORK 2: ADVANCED LINKED LISTS
                    State University of Zanzibar (SUZA)
================================================================================

STUDENT INFORMATION:
-------------------
Name: ________________________________    Reg. No: ____________________
Date Assigned: _____________              Due Date: ___________________

================================================================================
INSTRUCTIONS:
- Write your solutions in C programming language
- This homework focuses on doubly and circular linked lists
- Submit source code and handwritten algorithm traces
- Code must be your own work - plagiarism will result in zero marks

================================================================================

QUESTION 1: Music Playlist Manager (Doubly Linked List)           [25 marks]
--------------------------------------------------------------------------------
Create a doubly linked list to manage a music playlist. Each song node contains:
- Song ID (integer, auto-generated starting from 1)
- Song title (string, 100 characters)
- Artist name (string, 50 characters)
- Duration in seconds (integer)

Implement these features:
a) Add a song at the end of playlist
b) Add a song at a specific position
c) Remove a song by its ID
d) Play next song (move forward in list)
e) Play previous song (move backward in list)
f) Display playlist forward (first to last)
g) Display playlist backward (last to first)
h) Calculate total playlist duration

Your program should maintain a "current song" pointer that tracks which song
is currently "playing".

TEST SCENARIO:
1. Add songs: "Bohemian Rhapsody" (354s), "Stairway to Heaven" (482s),
   "Hotel California" (390s), "Comfortably Numb" (382s)
2. Move to song 2
3. Play next (should be song 3)
4. Play previous twice (should be song 1)
5. Remove song 2
6. Display playlist forward and backward

HANDWRITTEN WORK:
- Draw the doubly linked list after adding 4 songs
- Show all pointer updates when removing the middle song


QUESTION 2: Round Robin Process Scheduler (Circular Linked List)  [20 marks]
--------------------------------------------------------------------------------
Simulate a CPU process scheduler using a circular linked list. Each process node:
- Process ID (integer)
- Process name (string, 20 characters)
- Burst time remaining (integer, in milliseconds)

The scheduler works as follows:
- Each process gets a time quantum of 100ms
- After using its quantum, move to the next process
- When a process completes (burst time = 0), remove it from the list
- Continue until all processes complete

Implement:
a) Add a new process to the scheduler
b) Execute one round (give current process its quantum, reduce burst time)
c) Display all processes in the circular queue
d) Run until completion (show each step)

TEST WITH THESE PROCESSES:
| Process ID | Name    | Burst Time |
|------------|---------|------------|
| 1          | Chrome  | 250 ms     |
| 2          | VSCode  | 150 ms     |
| 3          | Spotify | 100 ms     |
| 4          | Terminal| 200 ms     |

Show the execution order and when each process completes.

HANDWRITTEN WORK:
- Draw the circular list with all 4 processes
- Create a table showing the state after each round of execution


QUESTION 3: Merge Two Sorted Lists                                [15 marks]
--------------------------------------------------------------------------------
Write a function that takes two sorted singly linked lists and merges them
into a single sorted list. The function should:
- NOT create new nodes (rearrange existing nodes only)
- Handle lists of different lengths
- Handle empty lists

Function signature:
```c
struct node* merge_sorted(struct node* list1, struct node* list2);
```

TEST CASES:
1. List1: 1 -> 3 -> 5 -> 7    List2: 2 -> 4 -> 6 -> 8
   Result: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

2. List1: 1 -> 5 -> 10        List2: 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> 9
   Result: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

3. List1: empty               List2: 1 -> 2 -> 3
   Result: 1 -> 2 -> 3

HANDWRITTEN WORK:
- Trace through the merge algorithm for Test Case 1
- Show pointer changes at each step


QUESTION 4: Comparison Analysis                                    [10 marks]
--------------------------------------------------------------------------------
Complete this comparison table (handwritten):

| Operation              | Singly LL | Doubly LL | Circular LL |
|------------------------|-----------|-----------|-------------|
| Insert at beginning    |           |           |             |
| Insert at end          |           |           |             |
| Delete from beginning  |           |           |             |
| Delete from end        |           |           |             |
| Search for element     |           |           |             |
| Traverse backward      |           |           |             |
| Memory per node        |           |           |             |

Fill in:
- Time complexity (Big O notation)
- For memory: express in terms of data size 'd' and pointer size 'p'

Answer these questions:
a) When would you choose a circular list over a singly linked list?
b) What is the main disadvantage of a doubly linked list?
c) Can you have a doubly circular linked list? Draw an example with 3 nodes.

================================================================================
SUBMISSION REQUIREMENTS:
[ ] All source code files (.c) with proper comments
[ ] Handwritten analysis and algorithm traces
[ ] Output screenshots showing test cases
[ ] File naming: RegNo_HW2_AdvancedLL.c

GRADING:
- Question 1 (Playlist): 25 marks
- Question 2 (Scheduler): 20 marks
- Question 3 (Merge): 15 marks
- Question 4 (Analysis): 10 marks
- Code quality and comments: 10 marks
- Handwritten work quality: 20 marks

TOTAL: 100 marks
================================================================================