Page 35 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes This recursive version also uses a strategy of inserting a node in an existing list to create the list.
An insert function is used to create the list. The insert function takes a pointer to an existing list

as the first parameter, and a data value with which the new node is to be created as the second
parameter. It creates the new node by using the data value, then appends it to the end of the list.

It then returns a pointer to the first node of the list. Initially, the list is empty, so the pointer to the

starting node is NULL. Therefore, when insert is called the first time, the new node created by
the insert function becomes the start node. Subsequently, the insert function traverses the list by
recursively calling itself. The recursion terminates when it creates a new node with the supplied
data value and appends it to the end of the list.

2.4 Deleting the Specified Node in Singly Linked List

To delete a node, first we determine the node number to be deleted (this is based on the assumption
that the nodes of the list are numbered serially from 1 to n). The list is then traversed to get a
pointer to the node whose number is given, as well as a pointer to a node that appears before the

node to be deleted. Then the link field of the node that appears before the node to be deleted is
made to point to the node that appears after the node to be deleted, and the node to be deleted is
freed. Figures 2.1 and 2.2 show the list before and after deletion, respectively.

Lab Exercise Program

# include <stdio.h>
# include <stdlib.h>
struct node *delet ( struct node *, int );
int length ( struct node * );
struct node
{
int data;
struct node *link;
};
struct node *insert(struct node *p, int n)
{
struct node *temp;
if(p==NULL)
{
p=(struct node *)malloc(sizeof(struct node));
if(p==NULL)
{
printf(“Error\n”);
exit(0);
}
p-> data = n;
p-> link = NULL;
}

30 LOVELY PROFESSIONAL UNIVERSITY