================================================================================
         DATA STRUCTURES AND ALGORITHMS (C)
         PRACTICAL LAB SESSION 2: Linked Lists
         State University of Zanzibar (SUZA)
================================================================================

OBJECTIVES:
- Create and manipulate singly linked lists
- Perform insertion, deletion, and traversal operations
- Implement advanced linked list algorithms
- Work with doubly and circular linked lists

================================================================================
PART A: SINGLY LINKED LIST BASICS
================================================================================

Structure:
   struct Node {
       int data;
       struct Node *next;
   };

1. Create and Display:
   Create a linked list by reading n values from user.
   Display all elements.
   void display(struct Node *head);

2. Insert at Beginning:
   struct Node* insertBegin(struct Node *head, int value);
   Test: List [10,20,30], insert 5 -> [5,10,20,30]

3. Insert at End:
   struct Node* insertEnd(struct Node *head, int value);
   Test: List [10,20,30], insert 40 -> [10,20,30,40]

4. Insert at Position:
   struct Node* insertAt(struct Node *head, int value, int pos);
   Test: List [10,20,30], insert 15 at position 1 -> [10,15,20,30]

5. Delete from Beginning:
   struct Node* deleteBegin(struct Node *head);

6. Delete from End:
   struct Node* deleteEnd(struct Node *head);

7. Count Nodes:
   int countNodes(struct Node *head);
   Test: [10,20,30,40] -> 4

8. Search:
   int search(struct Node *head, int key);
   Return position (0-based) or -1 if not found.
   Test: [10,20,30,40] key=30 -> 2

================================================================================
PART B: ADVANCED SINGLY LINKED LIST
================================================================================

9. Reverse Linked List:
   struct Node* reverse(struct Node *head);
   Test: [1,2,3,4,5] -> [5,4,3,2,1]

10. Find Middle Element:
    int findMiddle(struct Node *head);
    Use slow/fast pointer technique.
    Test: [1,2,3,4,5] -> 3

11. Detect Cycle:
    int hasCycle(struct Node *head);
    Use Floyd's cycle detection (tortoise and hare).
    Return 1 if cycle exists, 0 otherwise.

12. Merge Two Sorted Lists:
    struct Node* mergeSorted(struct Node *a, struct Node *b);
    Test: [1,3,5] + [2,4,6] -> [1,2,3,4,5,6]

13. Remove Duplicates from Sorted List:
    void removeDuplicates(struct Node *head);
    Test: [1,1,2,3,3,4] -> [1,2,3,4]

14. Find Nth Node from End:
    int nthFromEnd(struct Node *head, int n);
    Test: [10,20,30,40,50] n=2 -> 40

================================================================================
PART C: DOUBLY & CIRCULAR LINKED LISTS
================================================================================

Doubly Linked List Structure:
   struct DNode {
       int data;
       struct DNode *prev, *next;
   };

15. Doubly Linked List - Insert & Display:
    Create a doubly linked list. Insert at beginning and end.
    Display forward and backward.
    void displayForward(struct DNode *head);
    void displayBackward(struct DNode *tail);

16. Doubly Linked List - Delete:
    Delete a node with given value from doubly linked list.
    struct DNode* deleteNode(struct DNode *head, int value);

17. Circular Linked List - Create & Display:
    Create a circular linked list. Display all elements.
    void displayCircular(struct Node *last);

18. Circular Linked List - Insert:
    Insert at beginning and end of circular linked list.
    struct Node* insertBeginCircular(struct Node *last, int value);
    struct Node* insertEndCircular(struct Node *last, int value);

================================================================================
PART D: EXTRA PRACTICE (LeetCode / HackerRank Style)
================================================================================

19. [Easy] Reverse Linked List (LeetCode 206)
    Reverse a singly linked list iteratively and recursively.
    struct Node* reverseIterative(struct Node *head);
    struct Node* reverseRecursive(struct Node *head);

20. [Easy] Merge Two Sorted Lists (LeetCode 21)
    Merge two sorted lists into one sorted list.
    struct Node* mergeTwoLists(struct Node *l1, struct Node *l2);

21. [Easy] Linked List Cycle (LeetCode 141)
    Determine if linked list has a cycle.
    int hasCycle(struct Node *head);

22. [Medium] Remove Nth Node From End (LeetCode 19)
    Remove the nth node from end of list.
    struct Node* removeNthFromEnd(struct Node *head, int n);
    Test: [1,2,3,4,5] n=2 -> [1,2,3,5]

23. [Medium] Palindrome Linked List (LeetCode 234)
    Check if linked list is a palindrome.
    int isPalindrome(struct Node *head);
    Test: [1,2,2,1] -> 1 (true)

24. [Medium] Add Two Numbers (LeetCode 2)
    Two numbers represented as linked lists (reverse order). Return sum.
    Test: [2,4,3] + [5,6,4] -> [7,0,8] (342 + 465 = 807)

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