Data Structure : Singly Linked list


Introduction to singly linked list

Singly linked list is a basic linked list type. Singly linked list is a collection of nodes linked together in a sequential way where each node of singly linked list contains a data field and an address field which contains the reference of the next node. Singly linked list can contain multiple data fields but should contain at least single address field pointing to its connected next node.
Singly linked list

To perform any operation on a linked list we must keep track/reference of the first node which may be referred by head pointer variable. In singly linked list address field of last node must contain a NULL value specifying end of the list.

Basic structure of a singly linked list

Each node of a singly linked list follows a common basic structure. In a node we can store more than one data fields but we need at least single address field to store the address of next connected node.
struct node {
    int data; //Data part
    struct node * next; //Address part
};

Advantages of Singly linked list

There are several points about singly linked list that makes it an important data structure.
  • Singly linked list is probably the most easiest data structure to implement.
  • Insertion and deletion of element can be done easily.
  • Insertion and deletion of elements doesn't requires movement of all elements when compared to an array.
  • Requires less memory when compared to doubly, circular or doubly circular linked list.
  • Can allocate or deallocate memory easily when required during its execution.
  • It is one of most efficient data structure to implement when traversing in one direction is required.

Disadvantages of Singly linked list

After seeing the advantages of singly linked list. Singly linked list also has some disadvantages over other data structures.
  • Id uses more memory when compared to an array.
  • Since elements are not stored sequentially hence requires more time to access each elements of list.
  • Traversing in reverse is not possible in case of Singly linked list when compared to Doubly linked list.
  • Requires O(n) time on appending a new node to end. Which is relatively very high when compared to array or other linked list.

Creation of a singly linked list

To create a new node or to allocate memory dynamically we use malloc() function. malloc() function returns NULL value if memory is not allocated else returns a newly allocated memory address.
void createSinglyLinkedList()
{
    struct node * head; //head pointer keeps the address of first node
    head = (struct node *)malloc(sizeof(struct node));
        
    /*
     * If memory is not allocated
     */
    if(head == NULL)
    {
        printf("Unable to allocate memory.");
    }
    else //If memory is allocated
    {
        printf("List created successfully");
    }
}
See detailed explanation with program how to create a singly linked list.

Traversal of a singly linked list

To traverse entire list, start from the head or starting node and in each step advance the position of head pointer to next pointing node till a NULL or empty node is reached.
void traverseList(struct node *head)
{
    struct node *temp = head; //head contains the address of first node

    while(temp != NULL)
    {
        printf("Data = %d\n", temp->data);

        /* Advances the position of temp pointer */
        temp = temp->next;
    }
}
See detailed explanation with program how to traverse a singly linked list.

Insertion of a new node at beginning of list

To insert a new node at the beginning of list first create a new node. Then connect the new node to the head node i.e. new node should point to the first node. After connecting new node to head node make sure that the head node now points to the newly created node.
void insertNodeAtBeginning(struct node *head)
{
    struct node * newNode;

    newNode = (struct node *)malloc(sizeof(struct node));

    if(newNode == NULL)
    {
        printf("Unable to allocate memory.");
    }
    else
    {
        newNode->data = 10; //Assign some data to the data part of the node
        newNode->next = head; //Links new node to the first node of list
        head = newNode; //new node is the head node now.
    
        printf("New node added successfully at the beginning of list.");
    }
}
See detailed explanation with program how to insert a new node at the beginning of singly linked list.

Insertion of new node at end of list

To insert a new node at the end of list first traverse to the last node. Then create a new node and connect with the last node. Make sure that the last node points to the newly created node and newly created node points to NULL.
void insertNodeAtEnd(struct node *head)
{
    struct node *newNode, *temp;

    /* 
     * Check if the list is empty
     */ 
    if(head == NULL)
    {
        printf("Can't add a node at the end of an empty list.");
    }
    else
    {
        temp = head;

        /* Traverses to last node of the list */
        while(temp->next != NULL)
        {
            temp = temp->next;
        }

        newNode = (struct node *)malloc(sizeof(struct node));

        /*
         * If memory is not allocated
         */
        if(newNode == NULL)
        {
            printf("Unable to allocate memory.");
        }
        else
        {
            newNode->data = 10; //Assign some data to newly create node.
            newNode->next = NULL; //Since new node is last node hence points to NULL
            temp->next = newNode; //The previous last node now points to newly created node

            printf("Node added successfully at the end of list.");
        }
    }
}
See detailed explanation with program how to insert a new node at the end of singly linked list.

Insertion at n position of the list

To insert a new node at nth position in the list. First traverse to n-1 position. Create a new node and make sure that the new node points to n+1th node and n-1th node points to the newly created node.
void insertNodeAtN(struct node *head)
{
    struct node *newNode, *temp;
    int count;

    if(head == NULL)
    {
        printf("Can't insert a new node in an empty list.");
    }
    else
    {
        temp = head;

        /*
         * Traverse to n-1 position
         */
        for(count=1; count<n-1 && temp!=NULL; count++)
        {
            temp = temp->next;
        }

        newNode = (struct node*)malloc(sizeof(struct node));

        /* 
         * If memory is not allocated
         */
        if(newNode == NULL)
        {
            printf("Unable to allocate memory.");
        }
        else
        {
            newNode->data = 10; //Assign some data to new node
            newNode->next = temp->next; //New node points to n+1 node
            temp->next = newNode; //n-1 node points to new node

            printf("Node added successfully at %d position", n);
        }
    }
}
See detailed explanation with program how to insert a new node at the n position in singly linked list.

Deletion from beginning of list

To delete node from the beginning of list, first copy the reference of first node to some temp variable. Then make sure that the head node now points to 2nd node of the list. Now clear the memory allocated by the 1st node i.e. temp node. To clear resources allocated in memory use free() function.
void deleteNodeFromBeginning(struct node *head)
{
    struct node * toDelete; 

    /*
     * Check if the list is empty
     */
    if(head == NULL)
    {
        printf("Unable to delete from an empty list.");
    }
    else
    {
        toDelete = head; //contains reference of 1st node
        head = head->next; //head now points to 2nd node
    
        free(toDelete); //clears all resources used by 1st node

        printf("Successfully deleted first node of list.");
    }
}
See detailed explanation with program how to delete node from beginning of a singly linked list.

Deletion from end of list

To delete a node from the end of list, first traverse to n-1th position then copy the reference of nth node. Make sure that the n-1th node points to NULL. Now delete the nth node from the list.
void deleteNodeFromEnd(struct node *head)
{
    struct node *lastNode, *secondLastNode;

    /* 
     * Check if the list is empty
     */
    if(head == NULL)
    {
        printf("Can't delete from an empty list.");
    }
    else
    {
        /* 
         * Traverses to the last node
         */
        lastNode = head;
        while(lastNode->next != NULL)
        {
            secondLastNode = lastNode; //contains address of n-1 node
            lastNode = lastNode->next; //contains address of last node i.e n node
        }
    
        /* 
         * If there is only single node in the list
         */ 
        if(lastNode == head)
        {
            head = NULL;
        }
        else
        {
            secondLastNode->next = NULL; //Makes second last node as last node
        }

        free(lastNode); //deletes the last node from memory

        printf("Successfully deleted last node from the list.");
    }
}
See detailed explanation with program how to delete node from end of a singly linked list.

Deletion from n position in list

To delete nth node from the list, first traverse to n-1th node and copy the reference of nth node to a temp variable. Make sure that the n-1th node now points to n+1th node. After that free all resources allocated by nth node.
void deleteNodeFromN(struct node *head)
{
    struct node *nNode, *temp;
    int count;

    /*
     * Check if the list is empty
     */
    if(head == NULL)
    {
        printf("Unable to delete from an empty list.");
    }
    else
    {
        temp = head;

        /* Traverse to n-1 node */
        for(count=1; count<n-1 && temp!=NULL; count++)
        {
            temp = temp->next;
        }

        /* Check if the given position n is valid */
        if(temp != NULL)
        {
            printf("Unable to delete at specified position.");
        }
        else
        {
            nNode = temp->next;
            temp->next = nNode->next; //n-1 node points to n+1 node

            free(nNode); //Clears all memory used by nth node
            printf("Successfully deleted node at %d position.", n);
        }
    }
}
See detailed explanation with program how to delete node from middle of a singly linked list.

Deletion of entire list

void deleteList(struct node *head)
{
    struct node *nextNode, *curNode;

    /*
     * Check if the list is empty
     */
    if(head == NULL)
    {
        printf("Can't delete list is already empty.");
    }
    else
    {
        curNode = head;
        while(curNode != NULL)
        {
            nextNode = curNode->next;
            free(curNode);
            curNode = nextNode;
        }

        head = NULL;

        printf("Successfully deleted all nodes of list.");
    }
}
See detailed explanation with program how to delete all nodes of a singly linked list.

Count total number of elements

To count total number of elements we just need to traverse entire list and increment value of count variable in each repetition.
void countList(struct node *head)
{
    struct node *temp;
    int count = 0;

    temp = head;

    /*
     * Traverses entire list and counts total number of nodes
     */
    while(temp != NULL)
    {
        count++; //Increments count
        temp = temp->next; //Moves to next node
    }

    printf("Total number of nodes = %d", count);
}
See detailed explanation with program how to count total number of nodes in a singly linked list.

Reverse entire list

void reverseList(struct node *head)
{
    struct node *previousNode, *curNode;

    /*
     * Checks if the list is empty
     */
    if(head == NULL)
    {
        printf("Unable to reverse an empty list.");
    }
    else
    {
        previousNode = head;
        curNode = head->next;
        head = head->next;
        previousNode->next = NULL; //First node becomes last node

        while(head != NULL)
        {
            head = head->next;
            curNode->next = previousNode;

            previousNode = curNode;
            curNode = head;
        }

        head = previousNode; //Last node becomes the head node

        printf("Entire list reversed successfully.");
    }
}
See detailed explanation with program how to reverse a singly linked list.


Any doubt or suggestion write here. I will try my best to help. Before posting your code you must escape it to view. To format your source code and use format highlighting, post your source code inside
< code >< pre > -- Your source code -- < /pre >< /code > (Remove spaces from pre and code tags).

No comments:

Post a Comment