FOR FREE MATERIALS

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 delete an element from an existing list from any given position.

Let the existing list be:

Case 1:

The first case of this program is to delete an element from the first position of the list. The first position is always pointed by the pointer ‘head’. If the value of ‘head’ is replaced with the value the node pointed by the ‘head’ then the link of the first node will be de-touched from the rest of the nodes.

Therefore, the new list after deleting the first node the list will be:

Case 2:

The second case occurs if we want to delete an element from the middle position of the list. Let the position be ‘3’. Therefore, two pointers is to be taken pointing to the 2nd and the 3rd node of the list as:

Now, the address part of the node pointed by the pointer ‘ptr’ is replaced by the address part of the node pointed by ‘ptr1’. Therefore, the link of the 3rd node is de-touched.

After deleting the node, the list will be:

Case 3:

The last case is if we want to delete the last element from the list, we have to take one pointer and it should be pointed at the2nd last node of the list.

If we replace the address part of the node pointed by ‘ptr’ with ‘NULL’ then the link of the last node will be de-touched. Hence, the last node will be deleted.

After deleting the node the list will be:

INPUT:  The number of elements to create the list and the elements which are to be inserted and the position from which the data is to be deleted.
OUTPUT:  a) The list after creating it.
	        b) The linked list after deleting an element from 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 delfromanyposition()”
 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 and 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)	Set  ptr<-head1
  b)	Set  head1<-next[ptr]
  c)	Free(ptr)
		    [End of  “If”]
 Step 4.8: Else if(pos=n)
  a)	Ptr<-head1
  b)	While(next[next[ptr]]≠Null) then repeat
				Set  ptr<-next[ptr]
  c)	Set next[ptr] <- Null
		    [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” loop]
  c)	Set  next[ptr1] <-next[ptr]
  d)	Free(ptr)
		[End of  “Else”]
 Step 4.10: Print the list after deleting the element.
[End of the function “void delfromanyposition( )”]

 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. delfromanyposition()’,  ‘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.