Scribd
Upload
6 views6 pages

Activity1 Singly Linked List

The document provides a C implementation of basic operations for a singly linked list, including node creation, insertion, deletion, searching, and displaying elements. It defines a Node structure and functions to manipulate the list, demonstrating these operations in a sample demonstration function. The program concludes with memory cleanup to prevent leaks.

Uploaded by

iniademola21
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
6 views6 pages

Activity1 Singly Linked List

The document provides a C implementation of basic operations for a singly linked list, including node creation, insertion, deletion, searching, and displaying elements. It defines a Node structure and functions to manipulate the list, demonstrating these operations in a sample demonstration function. The program concludes with memory cleanup to prevent leaks.

Uploaded by

iniademola21
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 6

// =============================================================================

// ACTIVITY 1: SINGLY LINKED LIST - BASIC OPERATIONS


// Introduction to Data Structures in C
// =============================================================================

#include <stdio.h>
#include <stdlib.h>

// =============================================================================
// NODE STRUCTURE AND CREATION
// =============================================================================

// Define the structure for a node in a singly linked list


// Each node contains:
// - data: the integer value stored in the node
// - next: a pointer to the next node in the list
typedef struct Node {
int data;
struct Node* next;
} Node;

// Function to create a new node


// Parameters: data - the integer value to store in the node
// Returns: pointer to the newly created node, or NULL if memory allocation fails
Node* create_node(int data) {
// Allocate memory for a new node
Node* new_node = (Node*)malloc(sizeof(Node));

// Check if memory allocation was successful


if (new_node == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}

// Initialize the node's data and set next pointer to NULL


new_node->data = data;
new_node->next = NULL;
return new_node;
}

// =============================================================================
// INSERTION OPERATIONS
// =============================================================================

// Insert a new node at the beginning of the list


// Parameters: head - pointer to the current first node, data - value to insert
// Returns: pointer to the new head of the list
Node* insert_at_beginning(Node* head, int data) {
Node* new_node = create_node(data);
if (new_node == NULL) return head; // Return original head if creation failed

// Make the new node point to the current head


new_node->next = head;
printf("Inserted %d at the beginning\n", data);

// Return the new node as it becomes the new head


return new_node;
}
// Insert a new node at the end of the list
// Parameters: head - pointer to the current first node, data - value to insert
// Returns: pointer to the head of the list (unchanged unless list was empty)
Node* insert_at_end(Node* head, int data) {
Node* new_node = create_node(data);
if (new_node == NULL) return head;

// If the list is empty, the new node becomes the head


if (head == NULL) {
printf("Inserted %d as first element\n", data);
return new_node;
}

// Traverse to the end of the list


Node* current = head;
while (current->next != NULL) {
current = current->next;
}

// Link the last node to the new node


current->next = new_node;
printf("Inserted %d at the end\n", data);
return head;
}

// Insert a new node at a specific position (0-indexed)


// Parameters: head - pointer to current head, data - value to insert, position -
where to insert
// Returns: pointer to the head of the list
Node* insert_at_position(Node* head, int data, int position) {
// Check for invalid position
if (position < 0) {
printf("Invalid position!\n");
return head;
}

// If inserting at position 0, use insert_at_beginning


if (position == 0) {
return insert_at_beginning(head, data);
}

Node* new_node = create_node(data);


if (new_node == NULL) return head;

// Traverse to the node just before the insertion position


Node* current = head;
for (int i = 0; i < position - 1 && current != NULL; i++) {
current = current->next;
}

// Check if position is beyond the list length


if (current == NULL) {
printf("Position %d is out of bounds!\n", position);
free(new_node); // Don't forget to free the unused node
return head;
}

// Insert the new node between current and current->next


new_node->next = current->next;
current->next = new_node;
printf("Inserted %d at position %d\n", data, position);
return head;
}

// =============================================================================
// DELETION OPERATIONS
// =============================================================================

// Delete the first occurrence of a specific value


// Parameters: head - pointer to current head, data - value to delete
// Returns: pointer to the head of the list (may change if first node is deleted)
Node* delete_by_value(Node* head, int data) {
if (head == NULL) {
printf("List is empty - cannot delete %d\n", data);
return head;
}

// Special case: delete the first node


if (head->data == data) {
Node* temp = head;
head = head->next; // Update head to the next node
free(temp); // Free the deleted node's memory
printf("Deleted %d from the beginning\n", data);
return head;
}

// Search for the node to delete


Node* current = head;
while (current->next != NULL && current->next->data != data) {
current = current->next;
}

// Check if the element was found


if (current->next == NULL) {
printf("Element %d not found in the list\n", data);
return head;
}

// Delete the found node


Node* temp = current->next;
current->next = temp->next; // Skip over the node to be deleted
free(temp); // Free the deleted node's memory
printf("Deleted %d from the list\n", data);
return head;
}

// Delete a node at a specific position (0-indexed)


// Parameters: head - pointer to current head, position - position to delete from
// Returns: pointer to the head of the list
Node* delete_at_position(Node* head, int position) {
if (head == NULL) {
printf("List is empty - cannot delete at position %d\n", position);
return head;
}

if (position < 0) {
printf("Invalid position!\n");
return head;
}

// Special case: delete the first node (position 0)


if (position == 0) {
Node* temp = head;
head = head->next;
printf("Deleted element at position 0 (value: %d)\n", temp->data);
free(temp);
return head;
}

// Traverse to the node just before the deletion position


Node* current = head;
for (int i = 0; i < position - 1 && current->next != NULL; i++) {
current = current->next;
}

// Check if position is beyond the list length


if (current->next == NULL) {
printf("Position %d is out of bounds!\n", position);
return head;
}

// Delete the node at the specified position


Node* temp = current->next;
current->next = temp->next;
printf("Deleted element at position %d (value: %d)\n", position, temp->data);
free(temp);
return head;
}

// =============================================================================
// UTILITY OPERATIONS
// =============================================================================

// Search for an element in the list and return its position


// Parameters: head - pointer to the first node, data - value to search for
// Returns: position of the element (0-indexed), or -1 if not found
int search_element(Node* head, int data) {
Node* current = head;
int position = 0;

// Traverse the list and check each node


while (current != NULL) {
if (current->data == data) {
printf("Element %d found at position %d\n", data, position);
return position;
}
current = current->next;
position++;
}

// Element not found


printf("Element %d not found in the list\n", data);
return -1;
}

// Display all elements in the list


// Parameters: head - pointer to the first node
void display_list(Node* head) {
if (head == NULL) {
printf("List is empty\n");
return;
}

printf("List contents: ");


Node* current = head;
while (current != NULL) {
printf("%d", current->data);
if (current->next != NULL) {
printf(" -> ");
}
current = current->next;
}
printf(" -> NULL\n");
}

// Count the number of nodes in the list


// Parameters: head - pointer to the first node
// Returns: number of nodes in the list
int get_list_length(Node* head) {
int count = 0;
Node* current = head;

// Traverse the entire list and count nodes


while (current != NULL) {
count++;
current = current->next;
}
return count;
}

// Free all memory allocated for the list


// Parameters: head - pointer to the first node
// Note: This prevents memory leaks by deallocating all nodes
void free_list(Node* head) {
Node* current = head;
while (current != NULL) {
Node* temp = current;
current = current->next;
free(temp); // Free each node's memory
}
printf("Entire list memory freed\n");
}

// =============================================================================
// DEMONSTRATION FUNCTION
// =============================================================================

// Function to demonstrate all basic operations of a singly linked list


void singly_linked_list_demo() {
printf("\n=== SINGLY LINKED LIST DEMONSTRATION ===\n");
Node* head = NULL; // Start with an empty list

// Demonstrate insertion operations


printf("\n--- Insertion Operations ---\n");
head = insert_at_beginning(head, 10);
head = insert_at_beginning(head, 5);
head = insert_at_end(head, 20);
head = insert_at_end(head, 30);
display_list(head);

// Insert at specific positions


head = insert_at_position(head, 15, 2);
head = insert_at_position(head, 25, 4);
display_list(head);
printf("List length: %d\n", get_list_length(head));

// Demonstrate search operations


printf("\n--- Search Operations ---\n");
search_element(head, 15);
search_element(head, 100); // This won't be found

// Demonstrate deletion operations


printf("\n--- Deletion Operations ---\n");
head = delete_by_value(head, 15);
display_list(head);
head = delete_at_position(head, 0); // Delete first element
display_list(head);
head = delete_at_position(head, 2); // Delete middle element
display_list(head);

printf("Final list length: %d\n", get_list_length(head));

// Clean up memory
free_list(head);
}

// =============================================================================
// MAIN FUNCTION FOR TESTING
// =============================================================================

int main() {

printf("===========================================================================
==\n");
printf("ACTIVITY 1: SINGLY LINKED LIST - BASIC OPERATIONS\n");

printf("===========================================================================
==\n");

singly_linked_list_demo();

printf("\nProgram completed successfully!\n");


return 0;
}

You might also like