504 Programming and Data Structures
a) Creation of node: Before insertion, the node is created. Using m alloc () function memory
space is booked for the node.
b) Assignment of data: Once the node is created, data values are assigned to members.
c) Adjusting pointers: The insertion operation changes the sequence. Hence, according to the
sequence, the address of the next element is assigned to the inserted node. The address of the
current node (inserted) is assigned to the previous node.
The node can be inserted in the following positions in the list.
a) Insertion of the node at the starting: The created node is inserted before the first element.
After insertion, the newly inserted element will be the first element of the linked list. In this
insertion only the contents of the successive node's pointer are changed.
b) Insertion at the end of the list: A new element is appended at the end of the list. This operation
is easy as compared to other two (a) and (c) operations. In this insertion only the contents of
the previous node's pointer are changed.
c) Insertion at the given position in the list: In this operation, the user has to enter the position
number. The given position is counted and the element is inserted. In this insertion contents of
both the previous and next node's pointers are altered.
Insertion of the Node at the Starting
Inserting an element at the beginning involves updating links between link fields of two pointers.
After insertion of new node, the previously existing nodes are shifted ahead. Fig. 14.19(a) and
14.9 (b) illustrate the operation of insertion of a node.
Header
5 &
Node 1
8 &
3
X
Node 2
Node 3
9
&
Header
(a) Before insertion
► A
&
b
&
8 & 3
X
9
Node 1 Node 2
Node 2
Node 3
(b) After insertion
Fig. 14.19 Insertion at the beginning
The new node, which is to be inserted, is formed and the arrow indicates the position where it will
be inserted.
Linear Data Structure 505
After insertion, the new node will be the first node and its link field points to the second element,
which was previously the first element.
14.19 Write a program to insert an element at the beginning.
# include <stdio.h>
# include <conio.h>
# include <malloc.h>
struct num
{
int num;
struct num *next;
} *head er,*first,*rear;
main ()
{
void atbeg(void);
void form ( vo id);
void show (void);
clrscr () ;
printf ("
Operation creation : " );
form ();
show () ;
atbeg();
printf ("
The elements after insertion : " );
show () ;
atbeg();
show () ;
atbeg();
show () ;
}
void form ( void )
{
struct num *node;
printf ("
Enter number : ");
i f (header=*NULL)
{
first*(stru c t num*)malloc(sizeof(struct num));
scanf ( "%d", &first->num);
first->next=header;
he a de r= first;
r e a r = f ir s t ;
}
506 Programming and Data Structures
while (1)
{
nodes(struct num*) m alloc(sizeof(struct num));
scanf ("%d", fcnode->num);
i f (node->nums«0) break;
node- >next *NULL;
rear- >next=node;
rear=node;
>
}
void atbegO
{
struct num *node,*t;
nodes(struct num*) m alloc(sizeof(struct num));
printf ( Nn Insert an element at starting : ■);
scanf ("%d”,&node->num);
t= f irs t ;
header=node;
header->next=t;
first=header;
>
void show()
{
printf ("
Linked lis t elements are : ”);
while (header!=NULL)
{
printf (" %d ”, header->num);
header=header->next;
}
}
OUTPUT:
Operation creation:
Enter number. 12 3 4 0
Linked list elements are: 12 3 4
Insert an element at starting: 5
The elements after insertion:
Linked list elements are: 5 1 2 3 4
Insert an element at starting: 9
Linked list elements are: 9 5 1 2 3 4
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.