FOR FREE YEAR SOLVED

In computer science data structure, a linked list is a linear collection of data. The order of the data is not described by their placement in memory as an array. In the case of a linked list, one element points to the next element. The user-defined data type (structure) is used to define the ‘node’ in which the elements and addresses are stored.

Each node contains two parts:

# Data Part

# Address Part

And the node can be represented as:

Here the program is written to insert an element into an existing list at any given position.

Let the existing list by:

Now, suppose the new node is to be inserted at the first position. First, the new node will be created, pointed by a pointer ‘p’ with the new data as:

Now, this node will be added at the beginning of the list. For that, the new node ‘p’ will be pointing to the first node of the list (currently pointed by ‘head’) and ‘head’ will then point to ‘p’. The list after inserting will be:

Similarly, if the new node is to be inserted at the middle position then first the position is to be taken where the new node is to be inserted. Let the position be 4, which means in the case of this program, the new node is to be inserted between the elements ‘3’ and ‘5’. For inserting at that position two pointers are to be taken which will be pointing to the previous and next node of the required position.

Now the new node has been created with a new data pointed by ‘p’:

This node will be inserted into the list at the particular position if the node pointed by the pointer ‘ptr’ will point to the new node ‘p’ and ‘p’ points to the node pointed by the pointer ‘ptr1’.

The third case of this program is to insert an element at the last position of the linked list. For inserting a node at last first a pointer is to be pointed at the last node of the current list.

Now, a new node is to be created pointed by a pointer ‘p’.

Now, for inserting the node ‘p’, the address part of the node ‘ptr’ should store the address of ‘p’. The list after inserting the element at the last position is:

INPUT:  The number of elements to create the list and the elements which are to be inserted.
OUTPUT:   a) The list after creating it.
	       b) The linked list after inserting an element at any position of the list.
PROCESS:
Step 1: Define a structure named ‘node’ which has two parts−
•	The data part of integer type.
•	The ‘next’ (points to it’s next node i.e. the address of the next node) part which is a structure (node) type pointer.

Step 2: Create a function “void createlist()”
 Step 2.1: Take the number of  elements from user in an ‘integer’ type variable ‘n’
 Step 2.2: For i=0 to (n-1) repeat  Step 2.3 to Step 2.7
 Step 2.3: Take the element which is to be inserted in an integer type variable  ‘x’.
 Step 2.4: Create a new node in ‘p’(a ‘node’ type pointer) by using ‘malloc’ function.                    
Set data[p] <- x
	          Set next[p] <- Null
 Step 2.5: If (head1 = Null) then
                     		Set head1 <- p
	           [End of ‘If’ ]
 Step 2.6: Else   
            		Set next[ptr] <- p
	            [End of ‘Else’] 

 Step 2.7: Set ptr <- p

                [End of  Step 2.2 ‘For’ loop]
[End of  the function “void createlist( )”]   

Step 3: Create a function “void displaylist()”
 Step 3.1: Set p <-head1
 Step 3.2: While(p≠Null) then repeat  Step 3.3 and Step 3.4
 Step 3.3: Print  data[p]
 Step 3.4: Set p<-next[p]	
[End of  Step 3.2 ‘While’ loop]
[End of  the function “void displaylist( )”]

Step 4: Create a function “void insertanyposition()”
 Step 4.1: Set ptr<-head1
 Step 4.2: If (head1=Null) then
			Print   "List does not exist" and  return
		[End of  ‘If’]
 Step 4.3: While(ptr≠Null) then repeat Step 4.4 to Step 4.5
 Step 4.4:  Set n<-n+1
 Step 4.5: Set  ptr<-next[ptr]
	[End of  Step 4.3 ‘While’ loop]
 Step 4.6: Take the position from the user in an integer type variable ‘pos’ at which position the element will be inserted.
 Step 4.7: If (pos=1) then
a)	Take the element in an integer  type variable ‘x’ to insert  into the list.
b)	Create a new node in ‘p’ (a ‘node’ type pointer) by using  ‘malloc’ function.
Set  data[p] <-x
Set  next[p] <-Null
c)	Set  next[p] <-head1
d)	Set  head1<-p
		                      [End of ‘If’]
 Step 4.8: Else if (pos=n+1) then
a)	Set  ptr<-head1
b)	While (next[ptr]≠ Null) then repeat
				Set  ptr<-next[ptr]
c)	Take the element in an integer  type variable ‘x’ to insert  into the list.
d)	Create a new node in ‘p’ (a ‘node’ type pointer) by using  ‘malloc’ function.
Set  data[p] <-x
Set  next[p] <-Null.
e)	Set  next[ptr] <-p
		[End of ‘Else if’]
 Step 4.9: Else
a)	Set  ptr<-head1
b)	While(pos>c) then repeat
				Set  c<-c+1
				Set  ptr1<-ptr
				Set  ptr<-next[ptr]
			[End of  ‘While’]
c)	Take the element in an integer  type variable ‘x’ to insert  into the list.
d)	Create a new node in ‘p’ (a ‘node’ type pointer) by using  ‘malloc’ function.
Set  data[p] <-x
Set  next[p] <-ptr
e)	Set  next[ptr1] <-p
		[End of ‘Else’]
Step 4.10: Print the list after inserting the element.
[End of  the function “void insertanyposition( )”]

Step 5: Create a function “void main()”
[Creating the program as a ‘menu driven’ program]
 Step 5.1: Print the menu to take input from user.
 Step 5.2: Do from Step 5.3 to Step 5.6
 Step 5.3: Take an input in an ‘integer’ type variable ‘ch’.
 Step 5.4: Switch(ch) follow Step 5.5
 Step 5.5: Call the functions ‘1. createlist()’ , ‘ 2. displaylist()’, ‘3.insertanyposition()’,  ‘4. exit’   depending on the input ‘ch’.
[End of  the function ‘Switch’]
 Step 5.6: While (1) go to Step 5.2
[End of  Step 5.2 ‘Do-while’ loop]
[End of the function “void  main( )”]

Step 6: Stop.