DSA – Data Structures and Algorithm

Chapter 6: Circular Linked Lists Welcome to Chapter 6! In this chapter, we will explore Circular Linked Lists, a variation of linked lists where the last node in the list points back to the first node, forming a circular structure. This type of linked list is particularly useful in scenarios where you need a continuous loop through your data. What is a Circular Linked List? A Circular Linked List is a type of linked list in which the last node points back to the first node instead of having a NULL pointer. This circular structure allows you to traverse the list from any node and return to the starting node without having to check for the end. Here’s a graphical representation of a circular linked list: [Data | Next] -> [Data | Next] -> [Data | Next] -+ ^ | | | +——————————————-+ In this diagram, you can see that the next pointer of the last node points back to the first node, creating a loop. Why Use Circular Linked Lists? Circular linked lists are useful for scenarios that require a continuous loop or when you need to repeatedly cycle through the elements. Some applications include: Round-Robin Scheduling: In operating systems, circular linked lists can be used to manage tasks in a round-robin fashion. Circular Buffers: They are used in scenarios where you have a fixed-size buffer and need to overwrite old data when the buffer is full. Navigation Systems: For continuous navigation without end, like in a continuous data feed. Just like how Emancipation Edutech Private Limited might use circular linked lists to cycle through learning modules or resources efficiently, these structures can simplify repetitive tasks. Building a Circular Linked List To implement a circular linked list, we start by defining the node structure: #include <stdio.h> #include <stdlib.h> // Define a node structure struct Node { int data; struct Node* next; }; Creating a Node Creating a node is similar to singly linked lists, but with an additional step to handle the circular nature: struct Node* createNode(int value) { struct Node* newNode = (struct Node*) malloc(sizeof(struct Node)); newNode->data = value; newNode->next = newNode; // Point to itself initially return newNode; } Inserting Elements in a Circular Linked List Here’s how you can insert nodes into a circular linked list: At the Beginning: void insertAtBeginning(struct Node** head, int value) { struct Node* newNode = createNode(value); if (*head == NULL) { *head = newNode; newNode->next = *head; return; } struct Node* temp = *head; while (temp->next != *head) { temp = temp->next; } newNode->next = *head; temp->next = newNode; *head = newNode; } This function inserts a new node at the start of the circular list and adjusts the next pointers to maintain the circular structure. At the End: void insertAtEnd(struct Node** head, int value) { struct Node* newNode = createNode(value); if (*head == NULL) { *head = newNode; newNode->next = *head; return; } struct Node* temp = *head; while (temp->next != *head) { temp = temp->next; } temp->next = newNode; newNode->next = *head; } This function adds a new node to the end of the circular list by traversing to the last node and updating pointers. Inserting After a Given Node: void insertAfter(struct Node* prevNode, int value) { if (prevNode == NULL) { printf("The given previous node cannot be NULL"); return; } struct Node* newNode = createNode(value); newNode->next = prevNode->next; prevNode->next = newNode; } This function inserts a new node after a given node, adjusting the next pointers accordingly. Traversing a Circular Linked List Traversal in a circular linked list involves starting from the head and continuing until you return to the head: void traverse(struct Node* head) { if (head == NULL) return; struct Node* temp = head; do { printf("%d -> ", temp->data); temp = temp->next; } while (temp != head); printf("(back to head)\n"); } This function loops through the list and prints each node’s data until it returns to the head. Example: Creating and Traversing a Circular Linked List Here’s a sample program to create a circular linked list and traverse it: int main() { struct Node* head = NULL; // Inserting nodes insertAtEnd(&head, 10); insertAtEnd(&head, 20); insertAtBeginning(&head, 5); insertAtEnd(&head, 30); insertAfter(head->next, 15); // Insert 15 after the node with data 10 // Traverse the list traverse(head); return 0; } Output: 5 -> 10 -> 15 -> 20 -> 30 -> (back to head) Deleting Nodes in a Circular Linked List Deleting nodes in a circular linked list involves similar steps as in singly linked lists but requires updating the next pointers to maintain the circular structure: Deleting the First Node: void deleteFirstNode(struct Node** head) { if (*head == NULL) return; struct Node* temp = *head; if ((*head)->next == *head) { free(*head); *head = NULL; return; } struct Node* last = *head; while (last->next != *head) { last = last->next; } last->next = (*head)->next; *head = (*head)->next; free(temp); } Deleting the Last Node: void deleteLastNode(struct Node** head) { if (*head == NULL) return; struct Node* temp = *head; if ((*head)->next == *head) { free(*head); *head = NULL; return; } struct Node* prev = NULL; while (temp->next != *head) { prev = temp; temp = temp->next; } prev->next = *head; free(temp); } Deleting a Node by Value: void deleteNodeByValue(struct Node** head, int value) { if (*head == NULL) return; struct Node* temp = *head; struct Node* prev = NULL; do { if (temp->data == value) { if (prev == NULL) { // Node to be deleted is the head deleteFirstNode(head); return; } else { prev->next = temp->next; free(temp); return; } } prev = temp; temp = temp->next; } while (temp != *head); } Advantages and Disadvantages of Circular Linked Lists Advantages: Circular Traversal: Easily traverse through the list without needing to check for the end. Efficient for Round-Robin Scheduling: Ideal for scenarios where cyclic behavior is required. Disadvantages: Complexity: Slightly more complex to manage compared to singly linked lists. Potential for Infinite Loops: If not handled carefully, circular traversal can lead to infinite loops. Wrapping Up Chapter 6

Chapter 4: Linked Lists Welcome to Chapter 4! Now that you’ve become familiar with pointers and dynamic memory allocation, it’s time to explore how pointers unlock one of the most fundamental and powerful data structures: Linked Lists. If you’ve ever worked with arrays and found their fixed size to be limiting, you’re going to love linked lists. They provide flexibility, allowing you to dynamically manage data, making them perfect for scenarios where you don’t know the size of the data in advance. What is a Linked List? A Linked List is a linear data structure where each element (commonly called a node) points to the next element in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, each node contains: Here’s a simple graphical representation of a linked list: Each node points to the next, and the last node points to NULL, which signifies the end of the list. Why Use Linked Lists? Linked lists are dynamic, meaning you can add or remove elements from them without worrying about fixed size or shifting elements (as with arrays). Some reasons to use linked lists include: Linked lists, like those used in the backend of platforms like Emancipation Edutech Private Limited, efficiently handle data structures that grow dynamically, such as managing student records or tracking progress across multiple courses. Types of Linked Lists There are several variations of linked lists, each suited to different tasks: For now, we’ll focus on Singly Linked Lists, as they form the foundation for understanding more complex linked lists. Building a Singly Linked List To create a linked list, we first need to define the node structure. In C/C++, this is usually done using struct: Each node will have two fields: Creating a Node We’ll use dynamic memory allocation (malloc) to create nodes dynamically at runtime: This function allocates memory for a new node, initializes its data field, and sets the next pointer to NULL. Inserting Elements in a Linked List Now that we have a node, let’s learn how to insert it into a linked list. There are three common ways to insert nodes: Traversing a Linked List After inserting elements, you’ll want to traverse the list to access or display the data: This function loops through the list, printing each node’s data until it reaches the end (where next is NULL). Example: Creating and Traversing a Linked List Here’s an example of creating a linked list and printing its contents: Output: In this example, we created a list with four nodes and then printed it. Deleting Nodes in a Linked List Removing nodes from a linked list is just as important as adding them. There are three common ways to delete nodes: Advantages of Linked Lists Linked lists offer several advantages over arrays, making them suitable for situations where dynamic memory management is essential: Disadvantages of Linked Lists Linked lists also come with a few drawbacks: Wrapping Up Chapter 4 In this chapter, you’ve learned all about Singly Linked Lists, from creating and inserting nodes to deleting and traversing through them. Linked lists are the backbone of many advanced data structures, and mastering them opens up a world of possibilities in dynamic data management. Key takeaways: Keep practicing by implementing different types of linked lists, and if you ever need more resources, feel free to check out digilearn.cloud for interactive coding exercises. Next up: Stacks and Queues

Chapter 5: Doubly Linked Lists Welcome to Chapter 5! In this chapter, we’ll explore the Doubly Linked List—a more versatile type of linked list compared to the singly linked list. If you think of singly linked lists as one-way streets, doubly linked lists are like multi-lane roads with traffic flowing in both directions. This added flexibility can be particularly useful in various applications where bidirectional traversal is required. What is a Doubly Linked List? A Doubly Linked List is a type of linked list where each node has two pointers: Here’s a graphical representation: Each node contains a data field, a next pointer, and a prev pointer. The prev pointer of the first node is NULL, and the next pointer of the last node is NULL. Why Use Doubly Linked Lists? Doubly linked lists provide several advantages over singly linked lists: Doubly linked lists are used in applications such as navigation systems, where moving in both directions is necessary, similar to handling user interactions in educational platforms like Emancipation Edutech Private Limited. Building a Doubly Linked List To implement a doubly linked list, we start by defining the node structure: Each node now includes an additional pointer to the previous node. Creating a Node Here’s how you can create a new node: This function initializes a new node with the given value and sets both the next and prev pointers to NULL. Inserting Elements in a Doubly Linked List Here’s how you can insert nodes into a doubly linked list: Traversing a Doubly Linked List Traversal in a doubly linked list can be done in both directions: Example: Creating and Traversing a Doubly Linked List Here’s a sample program to create a doubly linked list and traverse it: Output: Deleting Nodes in a Doubly Linked List Deleting nodes in a doubly linked list is straightforward because you have pointers to both the next and previous nodes: Advantages and Disadvantages of Doubly Linked Lists Advantages: Disadvantages: Wrapping Up Chapter 5 In this chapter, we delved into Doubly Linked Lists—an enhanced version of singly linked lists that allows bidirectional traversal and simplifies node deletion. Mastering doubly linked lists will give you greater flexibility in handling dynamic data. Key takeaways: As always, if you want to see more examples or practice with interactive exercises, visit digilearn.cloud. And remember, **Emancipation