// =============================================================================
// ACTIVITY 3: DOUBLY LINKED LISTS IMPLEMENTATION
// Introduction to Data Structures in C
// =============================================================================
#include <stdio.h>
#include <stdlib.h>
// Node structure for doubly linked list
// Each node has data and pointers to both next and previous nodes
typedef struct DoublyNode {
int data;
struct DoublyNode* next; // Pointer to next node
struct DoublyNode* prev; // Pointer to previous node
} DoublyNode;
// =============================================================================
// CORE FUNCTIONS
// =============================================================================
/**
* Create a new doubly linked node
* @param data: The integer value to store in the node
* @return: Pointer to the newly created node, or NULL if allocation fails
*/
DoublyNode* create_doubly_node(int data) {
DoublyNode* new_node = (DoublyNode*)malloc(sizeof(DoublyNode));
if (new_node == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}
new_node->data = data;
new_node->next = NULL;
new_node->prev = NULL;
return new_node;
}
/**
* Insert at the beginning of doubly linked list
* @param head: Current head of the list
* @param data: Data to insert
* @return: New head of the list
*/
DoublyNode* doubly_insert_beginning(DoublyNode* head, int data) {
DoublyNode* new_node = create_doubly_node(data);
if (new_node == NULL) return head;
// If list is not empty, update the current head's prev pointer
if (head != NULL) {
head->prev = new_node;
}
// New node becomes the head
new_node->next = head;
printf("Inserted %d at the beginning of doubly linked list\n", data);
return new_node; // New head
}
/**
* Insert at the end of doubly linked list
* @param head: Current head of the list
* @param data: Data to insert
* @return: Head of the list (unchanged unless list was empty)
*/
DoublyNode* doubly_insert_end(DoublyNode* head, int data) {
DoublyNode* new_node = create_doubly_node(data);
if (new_node == NULL) return head;
// If list is empty, new node becomes the head
if (head == NULL) {
printf("Inserted %d as first element in doubly linked list\n", data);
return new_node;
}
// Traverse to the end of the list
DoublyNode* current = head;
while (current->next != NULL) {
current = current->next;
}
// Link the new node
current->next = new_node;
new_node->prev = current;
printf("Inserted %d at the end of doubly linked list\n", data);
return head;
}
/**
* Delete a node by value from doubly linked list
* @param head: Current head of the list
* @param data: Value to delete
* @return: New head of the list
*/
DoublyNode* doubly_delete_value(DoublyNode* head, int data) {
if (head == NULL) {
printf("Doubly linked list is empty\n");
return head;
}
DoublyNode* current = head;
// Find the node to delete
while (current != NULL && current->data != data) {
current = current->next;
}
if (current == NULL) {
printf("Element %d not found in doubly linked list\n", data);
return head;
}
// Update the previous node's next pointer
if (current->prev != NULL) {
current->prev->next = current->next;
} else {
// Deleting head node - update head
head = current->next;
}
// Update the next node's prev pointer
if (current->next != NULL) {
current->next->prev = current->prev;
}
free(current);
printf("Deleted %d from doubly linked list\n", data);
return head;
}
// =============================================================================
// DISPLAY FUNCTIONS
// =============================================================================
/**
* Display doubly linked list in forward direction
* @param head: Head of the list
*/
void display_doubly_forward(DoublyNode* head) {
if (head == NULL) {
printf("Doubly linked list is empty\n");
return;
}
printf("Forward traversal: NULL <- ");
DoublyNode* current = head;
while (current != NULL) {
printf("%d", current->data);
if (current->next != NULL) {
printf(" <-> ");
}
current = current->next;
}
printf(" -> NULL\n");
}
/**
* Display doubly linked list in backward direction
* @param head: Head of the list
*/
void display_doubly_backward(DoublyNode* head) {
if (head == NULL) {
printf("Doubly linked list is empty\n");
return;
}
// First, traverse to the end of the list
DoublyNode* current = head;
while (current->next != NULL) {
current = current->next;
}
// Now traverse backwards using prev pointers
printf("Backward traversal: NULL <- ");
while (current != NULL) {
printf("%d", current->data);
if (current->prev != NULL) {
printf(" <-> ");
}
current = current->prev;
}
printf(" -> NULL\n");
}
/**
* Free all memory used by the doubly linked list
* @param head: Head of the list
*/
void free_doubly_list(DoublyNode* head) {
DoublyNode* current = head;
while (current != NULL) {
DoublyNode* temp = current;
current = current->next;
free(temp);
}
printf("Doubly linked list memory freed\n");
}
// =============================================================================
// DEMONSTRATION FUNCTION
// =============================================================================
/**
* Demonstrates all doubly linked list operations
*/
void doubly_linked_list_demo() {
printf("\n=== DOUBLY LINKED LIST DEMONSTRATION ===\n");
DoublyNode* head = NULL;
// Insert operations
printf("\n--- Insertion Operations ---\n");
head = doubly_insert_beginning(head, 20);
head = doubly_insert_beginning(head, 10);
head = doubly_insert_end(head, 30);
head = doubly_insert_end(head, 40);
// Display in both directions
printf("\n--- Display Operations ---\n");
display_doubly_forward(head);
display_doubly_backward(head);
// Delete operations
printf("\n--- Deletion Operations ---\n");
head = doubly_delete_value(head, 20);
display_doubly_forward(head);
head = doubly_delete_value(head, 10); // Delete head
display_doubly_forward(head);
// Clean up memory
free_doubly_list(head);
}
// =============================================================================
// MAIN FUNCTION FOR STANDALONE TESTING
// =============================================================================
int main() {
printf("=== DOUBLY LINKED LIST IMPLEMENTATION ===\n");
doubly_linked_list_demo();
return 0;
}
