DS Menu

Single Linked List

A singly linked list is a type of data structure that is used to store a collection of elements called nodes. Each node contains a data item and a reference (address) to the next node in the sequence. The list is singly linked because each node points only to the next node in the sequence, not to the preceding one. The first node is referred to as the "head," and the last node, which has a NULL reference.

Structure of a Node

C code


struct Node {
    int data; // The data part
    struct Node* next; // Pointer to the next node
};

Basic Operations of singly linked list

Here are the basic operations that can be performed on a singly linked list:

1. Insertion at the beginning

Algorithm


1. Allocate memory for the new node.
2. Assign the data to the new node.
3. Make the 'next' of the new node point to the current head node.
4. Update the head node to be the new node.

Pseudo code

function insert_at_beginning(value)
    new_node = new Node
    new_node.data = value
    new_node.next = start
    start = new_node
end function

2. Insertion At the end

Algorithm


1. Allocate memory for the new node.
2. Assign the data to the new node and make its 'next' NULL.
3. If the list is empty, make the new node the head.
4. Else, traverse to the last node and update its 'next' to the new node.

Pseudo code

function insert_at_end(value)
    new_node = new Node
    new_node.data = value
    new_node.next = NULL
    if start is NULL
        start = new_node
    else
        temp = start
        while temp.next is not NULL
            temp = temp.next
        end while
        temp.next = new_node
    end if
end function

3. Insertion at the position

Algorithm


1. Allocate memory for the new node.
2. Assign the data to the new node and make its 'next' NULL.
3. If the list is empty or if position is 1, make the new node the head.
4. Else, traverse to the given position node 
5. position node 'next' is update to the new node and new node 'next' is update to position node.

Pseudo code

function insert_at_position(value, position)
    new_node = new Node
    new_node.data = value
    new_node.next = NULL
    if position == 1
        new_node.next = start
        start = new_node
    else
        temp = start
        for i = 1 to position
            temp = temp.next
        end for
        new_node.next = temp.next
        temp.next = new_node
    end if
end function

4) Deletion from the beginning

Algorithm


1. Check if the list is empty; if so, return.
2. Update the head to point to the second node in the list.
3. Free the memory of the first node.

Pseudo code

function delete_from_beginning()
    if start is NULL
        return "List is empty"
    else
        temp = start
        start = start.next
        delete temp
    end if
end function

5) Deletion from the end

Algorithm


1. Check if the list is empty; if so, return.
2. Traverse the list to find the last node and its previous node.
3. Set the next pointer of the second-to-last node to NULL.
4. Free the memory of the last node.

Pseudo code

function delete_from_end()
    if start is NULL
        return "List is empty"
    else if start.next is NULL
        delete start
        start = NULL
    else
        temp = start
        while temp.next.next is not NULL
            temp = temp.next
        end while
        delete temp.next
        temp.next = NULL
    end if
end function

6) Deletion at the position

Algorithm


1. Check if the list is empty or if the position is invalid; if so, return.
2. Traverse the list to find the node at the desired position and its previous node.
3. Update the next pointer of the previous node to skip the node at the desired position.
4. Free the memory of the node at the desired position.

Pseudo code

function delete_from_position(position)
    if start is NULL
        return "List is empty"
    else if position == 1
        temp = start
        start = start.next
        delete temp
    else
        temp = start
        for i = 1 to position-2
            temp = temp.next
        end for
        delete_node = temp.next
        temp.next = temp.next.next
        delete delete_node
    end if
end function

7) Traversal

Algorithm


1. Start from the head node.
2. Visit each node and perform the desired action (e.g., print the node's data).
3. Move to the next node.
4. Continue until reaching a node with a next pointer set to NULL.

Pseudo code

function traverse()
    temp = start
    while temp is not NULL
        print(temp.data)
        temp = temp.next
    end while
end function

8) Searching

Algorithm


1. Start from the head node.
2. Check the data at each node.
3. If a node with the given data is found, return it.
4. If no such node is found by the time the end of the list is reached, return NULL.

Pseudo code

function search(value)
    temp = start
    position = 1
    while temp is not NULL
        if temp.data == value
            return "Element found at position " + position
        end if
        temp = temp.next
        position += 1
    end while
    return "Element not found"
end function

Drawback of Single Linked List

No Random Access: Direct access to individual elements is not possible; one has to iterate from the head node to access a particular node.
Forward Navigation Only: You can only traverse in one direction, from the head of the list to the end.

C Program to implement Single Linked List

Algorithm


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

struct node{
    int data;
    struct node*next;
}*head=NULL;

int count()
{
    struct node *temp;
    int i=1;
    temp=head;
    while(temp->next!=NULL)
    {
        temp=temp->next;
        i++;
    }
    return(i);
}

struct node *create(int value)
{
    struct node *temp;
    temp=(struct node*)malloc(sizeof(struct node));
    temp->data=value;
    temp->next=NULL;
    return temp;
}
void insert_begin(int value)
{
    struct node *newnode;
    newnode=create(value);
    if(head==NULL)
    {
        head=newnode;
    }
    else
    {
        newnode->next=head;
        head=newnode;
    }
}

void insert_end(int value)
{
    struct node *newnode, *temp;
    newnode=create(value);
    if(head==NULL)
    {
        head=newnode;
    }
    else
    {
        temp=head;
        while(temp->next!=NULL)
        {
            temp=temp->next;
        }
        temp->next=newnode;
    }
}

void insert_pos(int value,int pos)
{
    struct node *newnode, *temp1,*temp2;
    int i,c=1;
    newnode=create(value);
    i=count();
    if(pos==1)
        insert_begin(value);
    else if(pos>i+1)
    {
        printf("insertion is not posible");
        return;
    }
    else
    {
        temp1=head;
        while(c<=pos-1 && temp1!=NULL)
        {
            temp2=temp1;
            temp1=temp1->next;
            c++;
        }
        newnode->next=temp2->next;
        temp2->next=newnode;
    }
}

void delete_begin()
{
    struct node *temp;
    if(head==NULL)
    {
        printf("deletion is not possible");
    }
    else
    {
        temp=head;
        head=head->next;
        free(temp);
    }
}
void delete_end()
{
    struct node *temp1,*temp2;
    if(head==NULL)
    {
        printf("deletion is not possible");
    }
    else
    {
        temp1=head;
        while(temp1->next!=NULL)
        {
            temp2=temp1;
            temp1=temp1->next;
        }
        temp2->next=NULL;
        free(temp1);
    }
}
void delete_pos(int pos)
{
    struct node *temp1,*temp2;
    int i,c=1;
    i=count();
    if(pos==1)
        delete_begin();
    else if(pos>i)
    {
        printf("Deletion is not posible");
        return;
    }
    else
    {
        temp1=head;
        while(c<=pos && temp1->next!=NULL)
        {
            temp2=temp1;
            temp1=temp1->next;
            c++;
        }
        temp2->next=temp1->next;
        free(temp1);
    }
}
void display()
{
    struct node *temp;
    if(head==NULL)
    {
        printf("list is empty");
    }
    else
    {
        temp=head;
        while(temp->next!=NULL)
        {
            printf("%d-> ",temp->data);
            temp=temp->next;
        }
        printf("%d",temp->data);
    }
}

void main()
{
    int ch,pos,value;
    do
    {
        printf("\n1.insert begin\n2.insert end\n3.insert position\n4.delete begin\n5.delete end\n6.delete position\n7.display\n8.exit\n");
        printf("enter your choice:");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1: printf("enter the value:");
                scanf("%d",&value);
                insert_begin(value);
                break;
        case 2: printf("enter value:");
                scanf("%d",&value);
                insert_end(value);
                break;
        case 3: printf("enter value:");
                scanf("%d",&value);
                printf("enter position you want to insert: ");
                scanf("%d",&pos);
                insert_pos(value,pos);
                break;
        case 4: delete_begin();
                break;
        case 5: delete_end();
                break;
        case 6: printf("enter position you want to delete: ");
                scanf("%d",&pos);
                delete_pos(pos);
                break;
        case 7: display();
                break;
        case 8:break;
        default: printf("\nyour choice is wrong!.. ");
        }
    }while(ch!=8);
}

Next Topic :Stacks using Array