Singly Linked List in Data Structure

A singly linked list is a linear data structure composed of a sequence of interconnected nodes. Unlike arrays, which have a fixed size and contiguous memory allocation, singly linked lists offer dynamic memory allocation, making them highly flexible for managing data that frequently grows or shrinks.

In this Data structure tutorial, you will explore what is a Singly Linked List, its representation, operations, advantages, disadvantages, and real-world applications to help you understand the concept thoroughly

What is a Singly Linked List?

A singly linked list is a linear data structure consisting of a sequence of nodes, where each node contains two components:

• Data: The value or payload stored in the node.
• Next Pointer: A reference to the next node in the sequence.

Unlike arrays, which store elements contiguously in memory, Singly linked lists use pointers to connect nodes, allowing for dynamic memory allocation. The list has a head (the first node) and ends with a node whose next pointer is null, indicating the end of the list.

Key Characteristics of Singly Linked Lists

• Dynamic Size: The list can grow or shrink as nodes are added or removed, unlike arrays with fixed sizes.
• Unidirectional Traversal: You can only traverse forward (from head to tail) due to the single next pointer.
• Non-Contiguous Memory: Nodes are scattered in memory, linked by pointers, which avoids the need for contiguous memory allocation.
• No Random Access: Unlike arrays, you cannot access elements by index in O(1) time; traversal is required.
• Memory Overhead: Each node requires additional memory for the next pointer.

Representation of Singly Linked List

Each node contains Data and a Next pointer. The Head points to the first node, and each subsequent node points to the next one. The last node points to NULL.

Head:The first node in a linked list is called the head. It is the entry point to the list and used as a reference point to traverse it.

Basic Operations on Singly Linked List

A Singly Linked List (SLL) supports several fundamental operations that allow us to manipulate data efficiently. These operations include traversal, insertion, deletion, searching, and updating.

1. Traversal

Traversal means visiting each node one by one starting from the head until the end of the list (NULL). It is used to display all elements or process data.

void traverse(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d → ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

2. Insertion

• Create a new node, point its next to the current head, and make it the new head.

struct Node* insertAtBeginning(struct Node* head, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = head;
    return newNode;
}

• Traverse to the last node and update its next pointer to the new node.

void insertAtEnd(struct Node* head, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    struct Node* temp = head;
    newNode->data = value;
    newNode->next = NULL;
    
    if (head == NULL) {
        head = newNode;
        return;
    }
    
    while (temp->next != NULL)
        temp = temp->next;
    temp->next = newNode;
}

• Traverse to the desired position and adjust pointers accordingly.

3. Deletion

• Move the head to the next node.

struct Node* deleteBeginning(struct Node* head) {
    if (head == NULL) return NULL;
    struct Node* temp = head;
    head = head->next;
    free(temp);
    return head;
}

• Traverse to the second-last node, make its next = NULL.

• Traverse to the previous node and adjust its next.

4. Searching

Traverse the list and check if a given key exists.

int search(struct Node* head, int key) {
    struct Node* temp = head;
    while (temp != NULL) {
        if (temp->data == key)
            return 1; // Found
        temp = temp->next;
    }
    return 0; // Not found
}

5. Updating

We can modify the value of an existing node without changing its links.

void update(struct Node* head, int oldValue, int newValue) {
    struct Node* temp = head;
    while (temp != NULL) {
        if (temp->data == oldValue) {
            temp->data = newValue;
            return;
        }
        temp = temp->next;
    }
}

Take our Datastructures skill challenge to evaluate yourself!

In less than 5 minutes, with our skill challenge, you can identify your knowledge gaps and strengths in a given skill.

GET FREE CHALLENGE