Singly Linked List

A Singly Linked List is a basic linked list, in which every element contains two fields. The first field contains data which hold useful information and the second field contains a reference to the next node. The pointer of last element contains a null value. When all nodes linked in the same direction, then it is called Single Linked List.

Singly Linked list

Singly Linked List Traversal

A singly linked list is traversed in only one direction, i.e. forward direction. The traverse is a process of print all elements one by one. For singly linked list traversal, first start at the head of the list and continue until we reach the node with null value. So, we need only one head reference to point to the first node of the list.

Algorithm

Step 1: SET PTR = START [Initialization]
Step 2: while PTR != NULL [Repeat 3 and 4]
Step 3: PTR DATA
Step 4: SET PTR = PTR NEXT
[END OF LOOP]
Step 5: EXIT

In the above algorithm, PTR is the address of the first node, we first initialize the PTR with the address of START and in a second step, we process the data in while loop till the last node which is equal to NULL.


Singly Linked List Searching

Search is the process of searching a particular element in linked list.

Algorithm

Step 1: SET PTR = START
Step 2: Repeat Step 3 while PTR != NULL
Step 3: IF VAL = PTR DATA
SET POS = PTR
Go To Step 5
ELSE
SET PTR = PTR NEXT
[END OF IF]
[END OF LOOP]
Step 4: SET POS = NULL
Step 5: EXIT

In the above algorithm, PTR is the address of the first node, we first initialize the PTR with the address of START and in a second step, we process the data in while loop till the last node which is equal to NULL. In the while loop, we compare every node data with the VAL, if it matches then assign to POS else set it to NULL.





Singly Linked List Insertion

Insertion is a process of inserting an element in an existing linked list either at the following position.

  • Insert at the first position
  • Insert at the last position
  • Insert into ordered list

Algorithm

Insert at the first position

Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 7
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL NEXT
Step 4: SET DATA = VAL
Step 5: SET NEW_NODE NEXT = START
Step 6: SET START = NEW_NODE
Step 7: EXIT

In the above algorithm, we first check the available memory. If no free memory, then print OVERFLOW, else we allocate free space for new node. Here, NEXT part is initialized with address of the first node and the START pointer hold the address of the new node.




Singly Linked List Program in C

#include <stdio.h>
#include <malloc.h>

struct node
{
    int value;
    struct node *next;
};
 
int create_node(int);
void insert_node_first();
void insert_node_last();
void insert_node_pos();
void delete();
void update();
void display_list();
typedef struct node snode;
snode *newnode, *ptr, *prev, *temp;
snode *first = NULL, *last = NULL;
 
 int main()
 {
    int chc;
    do
	{
        printf("\nChoice Options\n\t Enter 1 to insert node at first");
        printf("\nEnter 2 to insert node at last");
        printf("\nEnter 3 to insert node at position");
        printf("\nEnter 4 to delete node from any position");
        printf("\nEnter 5 to update node value");
        printf("\nEnter 6 to display list from beginning to end");
        printf("\nEnter 7 to exit\n");
        printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
        printf("\nEnter your choice - \n");
        scanf("%d", &chc);
 
        switch (chc)
        {
        case 1: 
            printf("\nInserting node at first position - \n");
            insert_node_first();
            break;
        case 2: 
            printf("\nInserting node at last position - \n");
            insert_node_last();
            break;
        case 3: 
            printf("\nInserting node at position - \n");
            insert_node_pos();
            break;
        case 4: 
            printf("\nDeleting node from any position - \n");
            delete();
            break;
        case 5: 
            printf("\nUpdating node value - \n");
            update();
            break;
        case 6: 
            printf("\nDisplaying List - \n");
            display_list();
            break;
        case 7:
	 		return 1;
	 		
		default:
	 			printf("\nPlease Enter Valid Choice:");
        }
    }while(1);
	return 0;
 }
 
/*
 * Create New Node
 */
int create_node(int val)
{
    newnode = (snode *)malloc(sizeof(snode));
    if (newnode == NULL)
    {
        printf("\nMemory Overflow");
        return 0;
    }
    else
    {
        newnode->value = val;
        newnode->next = NULL;
        return newnode;
    }
}
 
/*
 * Insert Node at First
 */
void insert_node_first()
{
    int val;
 
    printf("\nEnter the node value:");
    scanf("%d", &val);
    newnode = create_node(val);
    if (first == last && first == NULL)
    {
        first = last = newnode;
        first->next = NULL;
        last->next = NULL;
    }
    else
    {
        temp = first;
        first = newnode;
        first->next = temp;
    }
    printf("\n----NODE INSERTED----");    
}
 
/*
 * Insert Node at Last
 */
void insert_node_last()
{
    int val;
 
    printf("\nEnter the node value:");    
    scanf("%d", &val);
    newnode = create_node(val);
    if (first == last && last == NULL)
    {
        first = last = newnode;
        first->next = NULL;
        last->next = NULL;
    }
    else
    {
        last->next = newnode;
        last = newnode;
        last->next = NULL;
    }
 printf("\n----NODE INSERTED----");
}    
 
/*
 * Insert Node at position
 */
void insert_node_pos()
{
    int pos, val, cnt = 0, i;
 
    printf("\nEnter the node value:");
    scanf("%d", &val);
    newnode = create_node(val);
     printf("\nEnter the node position ");
    scanf("%d", &pos);
    ptr = first;
    while (ptr != NULL)
    {
        ptr = ptr->next;
        cnt++;
    }
    if (pos == 1)
    {
        if (first == last && first == NULL)
        {
            first = last = newnode;
            first->next = NULL;
            last->next = NULL;
        }
        else
        {
            temp = first;
            first = newnode;
            first->next = temp;
        }
        printf("\n---NODE INSERTED---");
    }
    else if (pos>1 && pos<=cnt)
    {
        ptr = first;
        for (i = 1;i < pos;i++)
        {
            prev = ptr;
            ptr = ptr->next;
        }
        prev->next = newnode;
        newnode->next = ptr;
        printf("\n----NODE INSERTED----");
    }
    else
    {
        printf("Position is not valid");
    }
}
 
/*
 * Delete Node
 */
void delete()
{
    int pos, cnt = 0, i;
 
    if (first == NULL)
    {
        printf("Empty List\n");
    }
    else
    {
        printf("\nEnter the node position to be deleted:");
        scanf(" %d", &pos);
        ptr = first;
        if (pos == 1)
        {
            first = ptr->next;
            printf("\nElement deleted");    
        }
        else 
        {
            while (ptr != NULL)
            {
                ptr = ptr->next;
                cnt = cnt + 1;
            }
            if (pos > 0 && pos <= cnt)    
            {
                ptr = first;
                for (i = 1;i < pos;i++)
                {
                    prev = ptr;
                    ptr = ptr->next;
                }
                prev->next = ptr->next;
            }
            else
            {
                printf("Position is not valid");
            }
        free(ptr);
        printf("\n---Element deleted----");
        }
    }
}
/*
 * Update node value
 */
void update()
{
    int old_value, new_value, flag = 0;
 
    if (first == NULL)
    {
        printf("Empty List\n");
    }
    else
    {
        printf("\nEnter the value to be updated:");
        scanf("%d", &old_value);
        printf("\nEnter the newvalue:");    
        scanf("%d", &new_value);
        for (ptr = first;ptr != NULL;ptr = ptr->next)
        {
            if (ptr->value == old_value)
            {
                ptr->value = new_value;
                flag = 1;
                break;
            }
        }
        if (flag == 1)
        {
            printf("\nUpdated Successfully");
        }
        else
        {
            printf("\nValue not found in List");
        }
    }    
}

/*
 * Display List
 */
void display_list()
{
    if (first == NULL)
    {
        printf("Empty List\n");
    }
    else
    {
        for (ptr = first;ptr != NULL;ptr = ptr->next)
        {    
            printf("%d\t", ptr->value);
        }
    }
}

Output of the above program


Choice Options
Enter 1 to insert node at first
Enter 2 to insert node at last
Enter 3 to insert node at position
Enter 4 to delete node from any position
Enter 5 to update node value
Enter 6 to display list from beginning to end
Enter 7 to exit

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Enter your choice - 
1

Inserting node at first position - 

Enter the node value:10

----NODE INSERTED----
Choice Options
	 Enter 1 to insert node at first
Enter 2 to insert node at last
Enter 3 to insert node at position
Enter 4 to delete node from any position
Enter 5 to update node value
Enter 6 to display list from beginning to end
Enter 7 to exit

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Enter your choice - 
1

Inserting node at first position - 

Enter the node value:20

----NODE INSERTED----
Choice Options
	 Enter 1 to insert node at first
Enter 2 to insert node at last
Enter 3 to insert node at position
Enter 4 to delete node from any position
Enter 5 to update node value
Enter 6 to display list from beginning to end
Enter 7 to exit

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Enter your choice - 
3

Inserting node at position - 

Enter the node value:40

Enter the node position 2

----NODE INSERTED----
Choice Options
	 Enter 1 to insert node at first
Enter 2 to insert node at last
Enter 3 to insert node at position
Enter 4 to delete node from any position
Enter 5 to update node value
Enter 6 to display list from beginning to end
Enter 7 to exit

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Enter your choice - 
6

Displaying List - 
20	40	10	
Choice Options
	 Enter 1 to insert node at first
Enter 2 to insert node at last
Enter 3 to insert node at position
Enter 4 to delete node from any position
Enter 5 to update node value
Enter 6 to display list from beginning to end
Enter 7 to exit

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Enter your choice - 
5

Updating node value - 

Enter the value to be updated:40

Enter the newvalue:50

Updated Successfully
Choice Options
	 Enter 1 to insert node at first
Enter 2 to insert node at last
Enter 3 to insert node at position
Enter 4 to delete node from any position
Enter 5 to update node value
Enter 6 to display list from beginning to end
Enter 7 to exit

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Enter your choice - 
6

Displaying List - 
20	50	10	
Choice Options
	 Enter 1 to insert node at first
Enter 2 to insert node at last
Enter 3 to insert node at position
Enter 4 to delete node from any position
Enter 5 to update node value
Enter 6 to display list from beginning to end
Enter 7 to exit

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~






Read more articles

PHP create image from text and save
How to Sort Table Data in PHP and MySQL
Google Street View API Example
Fibonacci Series Program in PHP
How to select/deselect all checkboxes using
Javascript
Php file based authentication
PHP FTP Connection and File Handling
Date Timestamp Formats in PHP

General Knowledge

listen
listen
listen
listen
listen
listen
listen
listen
listen


Learn Popular Language

listen
listen
listen
listen
listen