Singly Linked List

It is the normally utilized connected rundown in projects. In the event that we are discussing the connected show, it implies it is a separately connected rundown.

The separately connected rundown is an information structure that contains two sections, i.e., one is the information part, and the other one is the location part, which contains the location of the following or the replacement hub. The location part in a hub is otherwise called a pointer.

Assume we have three hubs, and the locations of these three hubs are 100, 200 and 300 separately. The portrayal of three hubs as a connected rundown is appeared in the underneath figure:

We can see in the above figure that there are three unique hubs having address 100, 200 and 300 individually. The principal hub contains the location of the following hub, i.e., 200, the subsequent hub contains the location of the last hub, i.e., 300, and the third hub contains the NULL incentive in its location part as it doesn't highlight any hub.

The pointer that holds the location of the underlying hub is known as a head pointer. The connected rundown, which is appeared in the above outline, is referred to as an independently connected rundown as it contains just a solitary connection.

In this rundown, just forward crossing is conceivable; we can't navigate the regressive way as it has just one connection in the rundown. Representation of the node in a singly linked list

struct node { 
    int data;
	struct node *next; 
}

Singly linked list or One way chain

Separately connected rundown can be characterized as the assortment of requested arrangement of components. The quantity of components may shift as indicated by need of the program.

A hub in the independently connected rundown comprise of two sections: information part and connection part.

Information some portion of the hub stores real data that will be addressed by the hub while the connection a piece of the hub stores the location of its nearby replacement.

One way chain or separately connected rundown can be crossed distinctly one way. As such, we can say that every hub contains just next pointer, hence we can not cross the rundown the opposite way.

Consider a model where the imprints acquired by the understudy in three subjects are put away in a connected rundown as demonstrated in the figure.

Operations on Singly Linked List

There are various operations which can be performed on singly linked list. A list of all such operations is given below.

1. Creation: Initializes the list with a node.
2. Insertion: Adds nodes at specific positions (beginning, end, or custom position).
3. Deletion: Removes nodes from the list.
4. Traversal & Display: Iterates over nodes to perform actions like printing data.

1. Creation of a Singly Linked List

Creating a singly linked list involves:

• Declaring the structure for a node, which contains the data and the pointer to the next node.
• Initializing the head pointer, which points to the first node in the list.

Example:

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

// Defining the structure for a node
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int value) {
	// Allocate memory
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); 
    newNode->data = value;  // Set the data of the node
    newNode->next = NULL;   // The next pointer points to NULL (last node)
    return newNode;
}

int main() {
    // Example of creating a single node
    struct Node* head = createNode(10);
    printf("Node created with value: %d\n", head->data);
    return 0;
}

In this example:

• We created a function createNode() to allocate memory for a node and initialize it with a value.
• The next pointer of the node is set to NULL because this is a new, single node (it has no other nodes linked to it).

2. Insertion in a Singly Linked List

Insertion refers to adding new nodes to the list. We can insert a node at three possible positions:

• At the beginning: Insert the node before the head node.
• At the end: Insert the node after the last node.
• At a specific position: Insert the node at a specific index.

Insertion at the Beginning:

To insert a new node at the beginning:

• Create a new node.
• Set the next pointer of the new node to the current head.
• Update the head to point to the new node.

Example:

void insertAtBeginning(struct Node** head, int value) {
    struct Node* newNode = createNode(value);  // Create a new node
    newNode->next = *head;  // Link new node to the current head
    *head = newNode;  // Update head to point to the new node
}

Insertion at the End:

To insert a new node at the end:

• Create a new node.
• Traverse the list to find the last node (where next is NULL).
• Set the next pointer of the last node to point to the new node.

Example:

void insertAtEnd(struct Node* head, int value) {
    struct Node* newNode = createNode(value);  // Create a new node
    struct Node* temp = head;
    
    // Traverse to the last node
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;  // Link the last node to the new node
}

Insertion at a Specific Position:

To insert at a specific position:

• Traverse the list to reach the node before the specified position.
• Create the new node and adjust the next pointers.

Example:

void insertAtPosition(struct Node* head, int position, int value) {
    struct Node* newNode = createNode(value); // Create a new node
    struct Node* temp = head;
    
    // Traverse to the node before the specified position
    for (int i = 1; i < position; i++) {
        if (temp != NULL)
            temp = temp->next;
    }
    
    // Insert the new node
    newNode->next = temp->next;
    temp->next = newNode;
}

3. Deletion in a Singly Linked List

Deletion refers to removing a node from the list. We can delete a node from three positions:

• At the beginning: Remove the first node (head node).
• At the end: Remove the last node.
• At a specific position: Remove the node at a specific index.

Deletion at the Beginning:

To delete the first node:

• Update the head to point to the second node (head = head->next).
• Free the memory of the old head node.

Example:

void deleteAtBeginning(struct Node** head) {
    if (*head != NULL) {
        struct Node* temp = *head;  // Store the current head
        *head = (*head)->next;  // Update the head to the next node
        free(temp);  // Free the memory of the old head
    }
}

Deletion at the End:

To delete the last node:

• Traverse the list to find the second-last node.
• Set the next pointer of the second-last node to NULL.
• Free the memory of the last node.

Example:

void deleteAtEnd(struct Node* head) {
    if (head == NULL) return;  // If the list is empty, return
    
    struct Node* temp = head;
    while (temp->next != NULL && temp->next->next != NULL) {
        temp = temp->next;  // Traverse until the second-last node
    }
    
    free(temp->next);  // Free the last node
    temp->next = NULL;  // Set the second-last node's next to NULL
}

Deletion at a Specific Position:

To delete a node at a specific position:

• Traverse to the node just before the node to be deleted.
• Set the next pointer of the previous node to the next node of the node to be deleted.
• Free the memory of the deleted node.

Example:

void deleteAtPosition(struct Node* head, int position) {
    if (head == NULL) return;  // If the list is empty, return
    
    struct Node* temp = head;
    
    // Traverse to the node just before the specified position
    for (int i = 1; i < position - 1; i++) {
        temp = temp->next;
    }
    
    struct Node* deleteNode = temp->next;  // Node to be deleted
    temp->next = temp->next->next;  // Skip the node to be deleted
    free(deleteNode);  // Free the memory of the deleted node
}

4. Traversing the Singly Linked List

Traversing means visiting each node of the list one by one and performing an operation, such as printing the node’s data.

Example:

void traverse(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);  // Print the node's data
        temp = temp->next;  // Move to the next node
    }
    printf("NULL\n");  // Indicating the end of the list
}

5. Displaying the Singly Linked List

Displaying the list simply means traversing through each node and printing the value stored in each node.

Example:

void display(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);  // Print node data
        temp = temp->next;  // Move to the next node
    }
    printf("\n");  // End of list
}

Time and Space Complexity of Singly Linked List

The time and space complexity of a singly linked list depends on the operations being performed.

Time Complexity

Space Complexity

Singly Linked List in C Programming

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

// Node structure
struct Node {
    int data;
    struct Node* next;
};

// Global head pointer
struct Node* head = NULL;

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Insert at head
void insertAtHead(int data) {
    struct Node* newNode = createNode(data);
    newNode->next = head;
    head = newNode;
}

// Insert at tail
void insertAtTail(int data) {
    struct Node* newNode = createNode(data);
    if (head == NULL) {
        head = newNode;
        return;
    }
    struct Node* temp = head;
    while (temp->next != NULL)
        temp = temp->next;
    temp->next = newNode;
}

// Insert at specific position (0-based index)
void insertAtPosition(int index, int data) {
    if (index == 0) {
        insertAtHead(data);
        return;
    }
    struct Node* newNode = createNode(data);
    struct Node* temp = head;
    for (int i = 0; i < index - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("Invalid position!\n");
        return;
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

// Delete at head
void deleteAtHead() {
    if (head == NULL) {
        printf("List is empty!\n");
        return;
    }
    struct Node* temp = head;
    head = head->next;
    free(temp);
}

// Delete at tail
void deleteAtTail() {
    if (head == NULL) {
        printf("List is empty!\n");
        return;
    }
    if (head->next == NULL) {
        free(head);
        head = NULL;
        return;
    }
    struct Node* temp = head;
    while (temp->next->next != NULL)
        temp = temp->next;
    free(temp->next);
    temp->next = NULL;
}

// Delete at specific position (0-based index)
void deleteAtPosition(int index) {
    if (index == 0) {
        deleteAtHead();
        return;
    }
    struct Node* temp = head;
    for (int i = 0; i < index - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    if (temp == NULL || temp->next == NULL) {
        printf("Invalid position!\n");
        return;
    }
    struct Node* nodeToDelete = temp->next;
    temp->next = nodeToDelete->next;
    free(nodeToDelete);
}

// Search by value
int search(int value) {
    struct Node* temp = head;
    int index = 0;
    while (temp != NULL) {
        if (temp->data == value)
            return index;
        temp = temp->next;
        index++;
    }
    return -1;  // Not found
}

// Access by index
int get(int index) {
    struct Node* temp = head;
    for (int i = 0; temp != NULL; i++) {
        if (i == index)
            return temp->data;
        temp = temp->next;
    }
    printf("Invalid index!\n");
    return -1;
}

// Display the list
void display() {
    struct Node* temp = head;
    printf("Linked List: ");
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// Main function
int main() {
    insertAtHead(10);
    insertAtTail(20);
    insertAtTail(30);
    insertAtPosition(1, 15);
    display();

    printf("Value at index 2: %d\n", get(2));
    printf("Index of value 20: %d\n", search(20));

    deleteAtHead();
    deleteAtTail();
    deleteAtPosition(1);
    display();

    return 0;
}

Output

Linked List: 10 -> 15 -> 20 -> 30 -> NULL
Value at index 2: 20
Index of value 20: 2
Linked List: 15 -> NULL

Understanding the operations of a singly linked list is crucial for building efficient data structures in programming.

By practicing creation, insertion, deletion, and traversal, you’ll be well-prepared to handle more advanced data manipulation tasks.

With the detailed examples provided, you can now confidently implement singly linked lists in your own applications.