Program to Create Singly Linked List .

More Detailed Step By Step Explanation

//Program by :- Pritesh A Taral
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
//-------------------------------------------------
struct node
{
int data;
struct node *next;
}*start=NULL;
//------------------------------------------------------------
void creat()
{
char ch;
 do
 {
  struct node *new_node,*current;
  new_node=(struct node *)malloc(sizeof(struct node));
  printf("nEnter the data : ");
  scanf("%d",&new_node->data);
  new_node->next=NULL;
  if(start==NULL)
  {
  start=new_node;
  current=new_node;
  }
  else
  {
  current->next=new_node;
  current=new_node;
  }
 printf("nDo you want to creat another : ");
 ch=getche();
 }while(ch!='n');
}
//------------------------------------------------------------------
void display()
{
struct node *new_node;
 printf("The Linked List : n");
 new_node=start;
 while(new_node!=NULL)
   {
   printf("%d--->",new_node->data);
   new_node=new_node->next;
   }
  printf("NULL");
}
//----------------------------------------------------
void main()
{
create();
display();
}
//----------------------------------------------------

Output :

Enter the data : 10
Do you want to creat another :  y
Enter the data : 20
Do you want to creat another : y
Enter the data : 30
Do you want to creat another : n
The Linked List :
10--->20--->30--->NULL

More Detailed Step By Step Explanation

Counting number of Nodes in Linked List :

We know the logic for traversing through the linked list in C Programming. [See Dry Run]

Function for counting the singly linked nodes is very similar to display(), Only difference is that instead of printing data we are incrementing length variable.

Two Ways of Counting the Number of Nodes :

We are counting the number of nodes using two ways - Using Non Recursion and Using Recursion.

Program : Way 1 [ Does not Returning Value]

void count()
{
    struct node *temp;
    int length = 0;
    temp = start;
    while(temp!=NULL)
    {
        length++;
        temp=temp->next;
    }
printf("nLength of Linked List : %d",length);
}

Program : Way 2 [Returning Value]

int count()
{
    struct node *temp = start;
    int length = 0;
    while(temp!=NULL)
    {
        length++;
        temp=temp->next;
    }
return(length);
}

Program : Way 3 [ Recursive Program to Count Number of Nodes in Linked List ]

int count(node *temp)
{
 if(temp == NULL)
     return(0);
 return(1 + count(temp->next));
}

Explanation of Recursive Function :

Consider the [this linked list] - Recursive function call for linked list is as follow -

Searching and Traversing for Data in Singly Linked List
Way 1 : This Function only tells that whether data is present or not

• This function return 1 if data found successfully.
• Returns 0 if data is not present

int search(int num)
{
int flag = 0;
struct node *temp;
temp = start;
  while(temp!=NULL)
  {
    if(temp->data == num)
       return(1); //Found
    temp = temp->next;
  }
if(flag == 0)
    return(0); // Not found
}

Way 2 : This Function Returns the node.

• If data or element is not present then return starting node
• Otherwise return the exact node.

struct node * search(int num)
{
int flag = 0;
struct node *temp;
temp = start;
  while(temp!=NULL)
  {
    if(temp->data == num)
       return(temp); //Found
    temp = temp->next;
  }
  if(flag == 0)
     return(start); // Not found
}

Delete First Node from Singly Linked List
Program :

void del_beg()
{
struct node *temp;
temp = start;
start = start->next;
free(temp);
printf("nThe Element deleted Successfully ");
}

Attention :
Step 1 : Store Current Start in Another Temporary Pointer

temp = start;

Step 2 : Move Start Pointer One position Ahead

start = start->next;

Step 3 : Delete temp i.e Previous Starting Node as we have Updated Version of Start Pointer

free(temp);

Linked-List : Insert Node at Middle Position in Singly Linked List

void insert_mid()
{
    int pos,i;
    struct node *new_node,*current,*temp,*temp1;
    new_node=(struct node *)malloc(sizeof(struct node));
    printf("nEnter the data : ");
    scanf("%d",&new_node->data);
    new_node->next=NULL;
    st :
    printf("nEnter the position : ");
    scanf("%d",&pos);
    if(pos>=(length()+1))
       {
       printf("nError : pos > length ");
       goto st;
       }
    if(start==NULL)
       {
       start=new_node;
       current=new_node;
       }
    else
       {
       temp = start;
             for(i=1;i< pos-1;i++)
             {
             temp = temp->next;
             }
       temp1=temp->next;
       temp->next = new_node;
       new_node->next=temp1;
       }
}

temp = start;
                for(i=1;i< pos-1;i++)
  {
  temp = temp->next;
  }

Step 2 :

temp1=temp->next;

Step 3 :

temp->next = new_node;

Step 4 :

new_node->next = temp1

Insert node at Last / End Position in Singly Linked List

Inserting node at start in the SLL (Steps):

1. Create New Node
2. Fill Data into “Data Field“
3. Make it’s “Pointer” or “Next Field” as NULL
4. Node is to be inserted at Last Position so we need to traverse SLL upto Last Node.
5. Make link between last node and newnode

void insert_at_end()
{
struct node *new_node,*current;
new_node=(struct node *)malloc(sizeof(struct node));
if(new_node == NULL)
   printf("nFailed to Allocate Memory");
 printf("nEnter the data : ");
 scanf("%d",&new_node->data);
 new_node->next=NULL;
 if(start==NULL)
 {
   start=new_node;
   current=new_node;
 }
 else
 {
   temp = start;
     while(temp->next!=NULL)
     {
     temp = temp->next;
     }
   temp->next = new_node;
 }
}

Diagram :

Attention :

1. If starting node is not available then “Start = NULL” then following part is executed

if(start==NULL)
       {
       start=new_node;
       current=new_node;
       }

2. If we have previously created First or starting node then “else part” will be executed to insert node at start
3. Traverse Upto Last Node., So that temp can keep track of Last node

else
       {
       temp = start;
   while(temp->next!=NULL)
  {
  temp = temp->next;
  }

4. Make Link between Newly Created node and Last node ( temp )

temp->next = new_node;

To pass Node Variable to Function Write it as -

void insert_at_end(struct node *temp)

Insert node at Start/First Position in Singly Linked List

Inserting node at start in the SLL (Steps):

1. Create New Node
2. Fill Data into “Data Field“
3. Make it’s “Pointer” or “Next Field” as NULL
4. Attach This newly Created node to Start
5. Make newnode as Starting node

void insert_at_beg()
{
struct node *new_node,*current;
new_node=(struct node *)malloc(sizeof(struct node));
 if(new_node == NULL)
    printf("nFailed to Allocate Memory");
 printf("nEnter the data : ");
 scanf("%d",&new_node->data);
 new_node->next=NULL;
   if(start==NULL)
   {
   start=new_node;
   current=new_node;
   }
   else
   {
   new_node->next=start;
   start=new_node;
   }
}

Diagram :

Attention :

1. If starting node is not available then “Start = NULL” then following part is executed

if(start==NULL)
       {
       start=new_node;
       current=new_node;
       }

2. If we have previously created First or starting node then “else part” will be executed to insert node at start

else
       {
       new_node->next=start;
       start=new_node;
       }

Some Terminology Of Linked List :

Consider the following node structure -

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

struct node *new_node,*current;

Summary of Different Linked List Terms :

struct node *new_node,*current;

*start = NULL;

start->next

start->data

start->next->data

current = start->next

start = start->next;

Explanation of Terms :

Consider the above linked list , we have initial conditions -

1. “start” node is pointing to First Node [ data = 1 ]
2. “current” node is pointing to Second Node [ data = 3 ]

with respect to the above linked list , data will be -

current = start->next

int num = start->data

int num = start->next->data

temp = current->next

int num = current->data

int num = current->next->data

Display Singly Linked List from First to Last

In the last chapter we have learn’t about traversing the linked list. In this chapter we will be printing the content of the linked list from start to last.

Steps for Displaying the Linked List :

1. In order to write the program for display, We must create a linked list using create(). Then and then only we can traverse through the linked list.
2. Traversal Starts from Very First node. We cannot modify the address stored inside global variable “start” thus we have to declare one temporary variable -“temp” of type node.
3. In order to traverse from start to end you should assign Address of Starting node in Pointer variable i.e temp

struct node *temp;  //Declare temp
temp = start;       //Assign Starting Address to temp

Now we are checking the value of pointer (i.e temp). If the temp is NULL then we can say that last node is reached.

while(temp!=NULL)
    {
    printf("%d",temp->data);
    temp=temp->next;
    }

See below dry run to understand the complete code and consider the linked list shown in the above figure -

Complete Display Function :

void display()
{
    struct node *temp;
    temp=start;
    while(temp!=NULL)
    {
    printf("%d",temp->data);
    temp=temp->next;
    }
}

Traversing through Singly Linked List (SLL) :

In the previous chapter we have learnt about the Creation of Singly Linked List. In this chapter, we will see how to traverse through Singly Linked List using C Programming.

1. Introduction :

Consider the Singly Linked list node structure. Traversing linked list means visiting each and every node of the Singly linked list. Following steps are involved while traversing the singly linked list -

1. Firstly move to the first node
2. Fetch the data from the node and perform the operations such as arithmetic operation or any operation depending on data type.
3. After performing operation, advance pointer to next node and perform all above steps on Visited node.

2. Node Structure and Program Declaration :

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

and the function definition for traversing linked list is -

struct node *temp = start; //Move to First Node
do {
    // Do Your Operation
    // Statement ...1
    // Statement ...2
    // Statement ...3
    // Statement ...n
    temp = temp->next; //Move Pointer to Next Node
}while(temp!=NULL);

3. Explanation of Traversing Linked List :

We know that, In order to traverse linked list, We need to visit first node and then visiting nodes one by one until the last node is reached.

temp = start; //Move to First Node
do {
    // Do Your Operation
    // Statement ...1
    // Statement ...2
    // Statement ...3
    // Statement ...n
    temp = temp->next; //Move Pointer to Next Node
}while(temp!=NULL);

Explanation :

Initially

temp = start;

1. Store Address of Starting node into “temp” , Print data stored in the node “temp“. ## Refer : Different Syntax and Terms in Linked List
2. Once Data stored in the temp is printed, move pointer to the next location so that “temp” will contain address of 2nd node.

[box]

Special Note :

In Singly Linked List Program , do not change start index un-necessarily because we must have something that can store address of Head node

[/box]