Friday, 8 December 2017

Creating a node for Single Linked List:

Creating a singly linked list starts with creating a node. Sufficient memory has to be allocated for creating a node. The information is stored in the memory, allocated by using
the malloc() function. The function getnode(), is used for creating a node, after allocating memory for the structure of type node, the information for the item (i.e., data) has to be read from the user, set next field to NULL and finally returns the address of the node. The below figure illustrates the creation of a node for single linked list.
node* getnode()
{
node* newnode;
newnode = (node *) malloc(sizeof(node)); 
printf("\n Enter data: ");
scanf("%d", &newnode -> data); 
newnode -> next = NULL;
return newnode;
}

Creating a Singly Linked List with ‘n’ number of nodes:
The following steps are to be followed to create 'n' number of nodes:
a. Get the new node using getnode().
newnode = getnode();
b. If the list is empty, assign new node as start.
start = newnode;
c. If the list is not empty, follow the steps given below:
The next field of the new node is made to point the first node (i.e. start node) in the list by assigning the address of the first node.
The start pointer is made to point the new node by assigning the address of the new node. Repeat the above steps 'n' times

Insertion of a Node:
One of the most primitive operations that can be done in a singly linked list is the insertion of a node. Memory is to be allocated for the new node (in a similar way that is done
while creating a list) before reading the data. The new node will contain empty data field and empty next field. The data field of the new node is then stored with the information read
from the user. The next field of the new node is assigned to NULL. The new node can then be inserted at three different places namely:
a. Inserting a node at the beginning.
b. Inserting a node at the end.
c. Inserting a node at intermediate position.

Inserting a node at the beginning:
The following steps are to be followed to insert a new node at the beginning of the list:
a. Get the new node using getnode().
newnode = getnode();
b. If the list is empty then start = newnode.
c. If the list is not empty, follow the steps given below:
newnode -> next = start;
start = newnode;
The function insert_at_beg(), is used for inserting a node at the beginning
void insert_at_beg()
{
node *newnode; 
newnode = getnode();
if(start == NULL)
{
start = newnode;
}
else
{
newnode -> next = start; 
start = newnode;
}
}

Inserting a node at the end:
The following steps are followed to insert a new node at the end of the list:
a. Get the new node using getnode()
newnode = getnode();
b. If the list is empty then start = newnode.
c. If the list is not empty follow the steps given below: 
temp= start;
while(temp -> next != NULL) 
temp = temp ->next;
temp -> next = newnode;
The function insert_at_end(), is used for inserting a node at the end.
void insert_at_end()
{
node *newnode,
*temp; newnode =getnode(); 
if(start ==NULL)
{
start = newnode;
}
else
{
temp = start;
while(temp -> next !=NULL) 
temp = temp-> next;
temp -> next = newnode;
}
}

Inserting a node at intermediate position:
The following steps are followed, to insert a new node in an intermediate position in the list:
a. Get the new node using getnode(). newnode = getnode();
b. Ensure that the specified position is in between first node and last node. If not, specified position is invalid. This is done by countnode() function.
c. Store the starting address (which is in start pointer) in temp and prev pointers.
Then traverse the temp pointer upto the specified position followed by prev pointer.
d. After reaching the specified position, follow the steps given below:
prev -> next = newnode;
newnode -> next = temp;

The function insert_at_mid(), is used for inserting a node in the intermediate position.
void insert_at_mid()
{
node *newnode, *temp, *prev; 
int pos, nodectr, ctr = 1;
newnode = getnode();
printf("\n Enter the position: ");
scanf("%d", &pos);
nodectr = countnode(start);
if(pos > 1 && pos < nodectr)
{
temp = prev = start;
while(ctr < pos)
{
prev = temp;
temp = temp -> next;
ctr++;
}
prev -> next = newnode;
newnode -> next = temp;
}
else
{
printf("position %d is not a middle position", pos);
}
}


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput