Programming and Data Structures

510 Programming and Data Structures

t - >next=rear: N ow the pointer t holds the ex-last node of the linked list. The address of the new

inserted end node is assigned to the link field of node through pointer t.

rear->next=NULL: The rear pointer holds the address of the last node and its link field is assigned

a N U L L value.

Insertion of a N ode at a G iven Position

Insertion of a node can be done at a specific position in the linked list. The following figure and

program explain the insertion of a node at the specific position in the linked list. Suppose we want

to insert a node at the third position, then observe Fig. 14.21.

(a) Formed linked list

r “

^Header

! J

00

, ”

X

~^i 5

3

9

(b) Linked list after insertion

Fig. 14.21 Insertion at a specified position

The methodology of solving a problem is the same as illustrated above, even when the insertion is

before or after a specified node. Hence, no separate illustration is required.

14.21 Write a program to insert an element at a particular position.

# include <stdio.h>

# include cconio.h>

# include cmalloc.h>

struct num

{

int num;

struct num *next;

} *header,*first,*rear;

int count;

main ()

{

void atpo(int);

void form ( v o id );

void show (v oid);

Linear Data Structure 511

int p;

c lr s c r();

printf ("\n Operation creation

form () ;

show () ;

printf (”\n Enter position (upto %d ) number (After) count );

scanf ("%d",&p1;

atp o (--p );

show () ;

>

void form ( void )

{

struct num *node;

printf ( ”\n Enter number : ”);

i f (header— NULL)

{

first*(stru c t num*)malloc(sizeof(struct num));

scanf ( a%d”/&first->num);

f ir s t - >next«header;

header«first;

rear= first;

>

while (1)

{

node*(struct num*) malloc(sizeof(struct num));

scanf ( ”%d”, &node->num);

i f (node->num«*0) break;

node- >nextbNULL;

rear- >next«node;

rear*node;

>

}

void atpo(int k)

{

struct num *nw/*su/*pr;

int c *l;

while (header 1*NULL)

{

C + +;

header=header->next;

512 Programming and Data Structures

i f (k»4t:1) p r-firs t;

if (ct-k) pr-header;

if (c -«(k + l)) subheader;

}

nw= (struct num*) m alloc(sizeof(struct num));

printf ("\n Enter a element : ■);

scanf ("%d", &nw->num);

pr->next«nw;

nw->next-su;

header-first;

}

void show()

{

printf ( ”\n Linked li s t elements are : ”);

while (headerI-NULL)

{

printf (" %d ", header- >num);

count++;

header-header->next;

}

header-first;

}

Operation creation:

Enter number 1 2 3 4 5 0

Linked list elements are: 1 2 3 4 5

Enter position (upto 5 )number (After):3

Enter a element: 8

Linked list elements are: 1 2 8 3 4 5

Explanation In the above program the operation, creation and display of linked nodes is similar

to that explained in the last programs. Here, we are going to discuss insertion at a particular position

carried out by a function ato p ( - - p ) . The position number is specified by the user, after reducing

the value by one it is passed to function atop (). The variable k, formal argument of p, gets this

value. Another variable c is declared in the body of ato p (). The variable c is incremented and

successive nodes of the linked list are accessed by the statement header=header - >next.