Singly Linked List - Operations

 

📚 What is a Singly Linked List?

  • A Singly Linked List is a collection of nodes.

  • Each node has two parts:

    • Data: holds the value.

    • Next Pointer: points to the next node in the list.

  • The last node points to NULL, indicating the end of the list.

✅ Singly linked list allows dynamic memory allocation (no fixed size like arrays) and easy insertion and deletion at any position.


Basic Structure

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

  • head points to the first node of the linked list.

  • If head is NULL, the list is empty.


📚 Singly Linked List - Detailed Algorithms

Each node contains:

  • data (value)

  • next (pointer to the next node)

Initially:

  • head = NULL (list is empty)

1. Creation (Insert at End)

Algorithm:

Step 1: Create a new node (newNode) with given data
Step 2: Set newNode->next = NULL
Step 3: If head == NULL (list empty)
            Set head = newNode
        Else
            Initialize temp = head
            While temp->next != NULL
                temp = temp->next  (Move temp to next node)
            End While
            Set temp->next = newNode

Pointer adjustments:

  • New node created

  • Traversing till the last node

  • Last node's next pointer is made to point to new node

2. Insertion at Beginning

Algorithm:

Step 1: Create a new node (newNode) with given data
Step 2: Set newNode->next = head
Step 3: Set head = newNode

Pointer adjustments:

  • New node's next points to current head

  • Head is updated to the new node

3. Insertion at a Specific Position

Algorithm:


Step 1: Create a new node (newNode) with given data
Step 2: If position == 1
            Set newNode->next = head
            Set head = newNode
            RETURN
Step 3: Initialize temp = head
Step 4: Repeat (position - 2) times
            If temp == NULL
                Position is invalid, RETURN
            temp = temp->next
Step 5: Set newNode->next = temp->next
Step 6: Set temp->next = newNode

Pointer adjustments:

  • Traverse till node at (position - 1)

  • Insert new node after it by adjusting two pointers.

4. Deletion at Beginning

Algorithm:

Step 1: If head == NULL
            List is empty, RETURN
Step 2: Create temp = head
Step 3: Set head = head->next
Step 4: Free temp

Pointer adjustments:

  • Move head to next node

  • Free original head node

5. Deletion at End

Algorithm:

Step 1: If head == NULL
            List is empty, RETURN
Step 2: If head->next == NULL
            Only one node present
            Free head
            Set head = NULL
            RETURN
Step 3: Initialize temp = head
Step 4: While temp->next->next != NULL
            temp = temp->next
Step 5: Free temp->next
Step 6: Set temp->next = NULL

Pointer adjustments:

  • Traverse to the second last node

  • Free last node

  • Set second last node's next to NULL

6. Deletion at Specific Position

Algorithm:

Step 1: If head == NULL
            List is empty, RETURN
Step 2: If position == 1
            Create temp = head
            Set head = head->next
            Free temp
            RETURN
Step 3: Initialize temp = head
Step 4: Repeat (position - 2) times
            If temp == NULL
                Position invalid, RETURN
            temp = temp->next
Step 5: If temp->next == NULL
            Position invalid, RETURN
Step 6: Create deleteNode = temp->next
Step 7: Set temp->next = deleteNode->next
Step 8: Free deleteNode

Pointer adjustments:

  • Traverse to node before the one to delete

  • Adjust next pointers to skip the node

  • Free deleted node

7. Traversal (Display Linked List)

Algorithm:

Step 1: If head == NULL
            Print "List is empty", RETURN
Step 2: Initialize temp = head
Step 3: While temp != NULL
            Print temp->data
            temp = temp->next

Pointer adjustments:

  • Move temp one by one and print data

Example




C Program: Singly Linked List (Insertion,deletion, Traversal)

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

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

// Head pointer
struct Node* head = NULL;

// Function to create and insert a node at the end
void insertAtEnd(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (head == NULL) {
        head = newNode;
    } else {
        struct Node* temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// Function to insert at beginning
void insertAtBeginning(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = head;
    head = newNode;
}

// Function to insert at a given position
void insertAtPosition(int value, int position) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (position == 1) {
        newNode->next = head;
        head = newNode;
        return;
    }

    struct Node* temp = head;
    for (int i = 1; i < position - 1; i++) {
        if (temp == NULL) {
            printf("Invalid position!\n");
            return;
        }
        temp = temp->next;
    }

    newNode->next = temp->next;
    temp->next = newNode;
}

// Function to delete at beginning
void deleteAtBeginning() {
    if (head == NULL) {
        printf("List is empty!\n");
        return;
    }

    struct Node* temp = head;
    head = head->next;
    free(temp);
}

// Function to delete at end
void deleteAtEnd() {
    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;
}

// Function to delete at a given position
void deleteAtPosition(int position) {
    if (head == NULL) {
        printf("List is empty!\n");
        return;
    }

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

    struct Node* temp = head;
    for (int i = 1; i < position - 1; i++) {
        if (temp == NULL) {
            printf("Invalid position!\n");
            return;
        }
        temp = temp->next;
    }

    if (temp->next == NULL) {
        printf("Invalid position!\n");
        return;
    }

    struct Node* deleteNode = temp->next;
    temp->next = deleteNode->next;
    free(deleteNode);
}

// Function to display the list
void display() {
    if (head == NULL) {
        printf("List is empty!\n");
        return;
    }

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

// Main function
int main() {
    int choice, value, position;

    while (1) {
        printf("\n--- Singly Linked List Operations ---\n");
        printf("1. Insert at End\n");
        printf("2. Insert at Beginning\n");
        printf("3. Insert at Position\n");
        printf("4. Delete at Beginning\n");
        printf("5. Delete at End\n");
        printf("6. Delete at Position\n");
        printf("7. Display List\n");
        printf("8. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter value to insert at end: ");
                scanf("%d", &value);
                insertAtEnd(value);
                break;
            case 2:
                printf("Enter value to insert at beginning: ");
                scanf("%d", &value);
                insertAtBeginning(value);
                break;
            case 3:
                printf("Enter value to insert: ");
                scanf("%d", &value);
                printf("Enter position: ");
                scanf("%d", &position);
                insertAtPosition(value, position);
                break;
            case 4:
                deleteAtBeginning();
                break;
            case 5:
                deleteAtEnd();
                break;
            case 6:
                printf("Enter position to delete: ");
                scanf("%d", &position);
                deleteAtPosition(position);
                break;
            case 7:
                display();
                break;
            case 8:
                printf("Exiting...\n");
                exit(0);
            default:
                printf("Invalid Choice! Try again.\n");
        }
    }

    return 0;
}


Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more