1. 3 singly linked list insertion 2

singly linked list insertion 2

1. DATA STRUCTURES Dr. P. Subathra Professor Dept. of Information Technology KAMARAJ College of Engineering & Technology

2. CS8 391 – DATA STRUCTURES ONLINE CLASSES – CLASS NO. 3 18.08.2020 (04:00 PM – 05:00 PM)

3. UNIT 1 SINGLY LINKED LIST

4. INSERT AFTER AN ELEMENT

5. INSERT AFTER AN ELEMENT Algorithm : STEP 1 : Dynamically generate a new node. STEP 2 : Get the value in the node’s data field. STEP 3 : Check if the list is empty, if so display a message and return. Traverse the list until the specified node is reached or End of List is reached . If element is found, insert the new element after the current node Else if end of list is reached, display a message of ELEMENT NOT FOUND and return

6. Initial List Insert 8 after 6 INSERT AFTER AN ELEMENT

7. Initial List Insert 8 after 6 Final List INSERT AFTER AN ELEMENT

8. ALGORITHM STEP 1 : Dynamically generate a new node . STEP 2 : Get the value in the node’s data field . CODE & ILLUSTRATION INSERT AFTER AN ELEMENT

9. ALGORITHM STEP 3: i. Check if the list is empty, if so, display a message and return CODE & ILLUSTRATION INSERT AFTER AN ELEMENT if (head==NULL) { p rinft (“Empty List”); return(); //optional } NULL head

10. ALGORITHM STEP 3 : Else traverse the list until the specified node is reached or End of List is reached . a. If element is found, insert the new element after the current node b. Else if end of list is reached, display a message of ELEMENT NOT FOUND and return CODE & ILLUSTRATION INSERT AFTER AN ELEMENT else { node * current = head; while (current  data ! = searchElement || current next !=NULL ) { current = current  next; } }

11. ALGORITHM & CODE STEP 3 : Else traverse the list until the specified node is reached or End of List is reached . a. If element is found, insert the new element after the current node b. Else if end of list is reached, display a message of ELEMENT NOT FOUND and return ILLUSTRATION INSERT AFTER AN ELEMENT else { node * current = head; while (current  data ! = searchElement || current next !=NULL ) { current = current  next; } if ( current  data == element) { tempnext =current->next; currentnext =temp; } else p rintf (“Element not found”); }

12. Initial List Insert 8 after 6 Final List INSERT AFTER AN ELEMENT

13. INSERT BEFORE AN ELEMENT

14. INSERT BEFORE AN ELEMENT Algorithm : STEP 1 : Dynamically create a new node STEP 2 : Get the value in the data field of the new node .   STEP 3 : Check if the list is empty, if so display a message and return. Check if the node is available as the first node Perform Insert First operation Traverse the list until the specified node is reached or End of List is reached . While traversing, keep track of the previous node also .   If element is found, insert the new element after the previous node Else if end of list is reached, display a message of ELEMENT NOT FOUND and return

15. ALGORITHM STEP 1 : Dynamically generate a new node . STEP 2 : Get the value in the node’s data field . CODE & ILLUSTRATION INSERT BEFORE AN ELEMENT

16. ALGORITHM STEP 3: i. Check if the list is empty, if so, display a message and return CODE & ILLUSTRATION INSERT BEFORE AN ELEMENT if (head==NULL) { p rinft (“Empty List”); return(); // } NULL head

17. ALGORITHM & CODE STEP 3: ii. Else check if the node is available as the first node a. Perform Insert First operation ( eg ) Insert after 7 ILLUSTRATION INSERT BEFORE AN ELEMENT e lse if (head-> data==element) { temp->next=head; head=temp; } NULL NULL NULL

18. ALGORITHM & CODE STEP 3: iii. Else Traverse the list until the specified node is reached or End of List is reached. While traversing, keep track of the previous node also.   ILLUSTRATION INSERT BEFORE AN ELEMENT else { node * previous=head; node * current = head-> next; while (current->data! = element || current->next!=NULL) { current= current-> next; previous = previous->next; } }

19. ALGORITHM & CODE STEP 3 : iii. a . If element is found, insert the new element after the previous node b. Else if end of list is reached, display a message of ELEMENT NOT FOUND ILLUSTRATION INSERT BEFORE AN ELEMENT else { node * previous=head; node * current = head-> next; while (current->data! = element || current->next!=NULL) { current= current-> next; previous = previous->next; } if(current-> data==element) { temp->next= prev ->next; prev ->next = temp; } else p rintf (“Element not found”); }

20. ALGORITHM & CODE STEP 3 : iii. a . If element is found, insert the new element after the previous node b. Else if end of list is reached, display a message of ELEMENT NOT FOUND ILLUSTRATION INSERT BEFORE AN ELEMENT else { node * previous=head; node * current = head-> next; while (current->data! = element || current->next!=NULL) { current= current-> next; previous = previous->next; } if(current-> data==element) { temp->next= prev ->next; prev ->next = temp; } else p rintf (“Element not found”); }

21. INSERT BEFORE AN ELEMENT

22. INSERT AT A POSITION

23. INSERT AT A POSITION Algorithm : STEP 1 : Dynamically create a new node . STEP 2 : Read the new value into the element field of the new node . STEP 3: Let k= POSITION Check if the list is empty, if so display a message and return. Check if k==1 (First Position) Perform Insert First operation Traverse the list until the specified (k -1) th node is reached or End of List is reached   If (k -1) is available in the list, then, insert the new element after the (k -1) th node Copy the (k-1) th nodes next field value into the next field of the new node. Make the (k-1) th node to point to this new node. Else if end of list is reached, display a message of ELEMENT NOT FOUND and return

24. ALGORITHM STEP 1 : Dynamically generate a new node . STEP 2 : Get the value in the node’s data field . CODE & ILLUSTRATION INSERT AT A POSITION

25. ALGORITHM STEP 3: i. Check if the list is empty, if so, display a message and return CODE & ILLUSTRATION if (head==NULL) { p rinft (“Empty List”); return(); // } NULL head INSERT AT A POSITION

26. ALGORITHM & CODE STEP 3: ii. Check if k==1 (First Position) a. Perform Insert First operation ILLUSTRATION e lse if (k== 1) { temp->next=head; head=temp; } NULL NULL NULL INSERT AT A POSITION

27. ALGORITHM & CODE STEP 3: iii. Traverse the list until the specified (k -1) th node is reached or End of List is reached  ( eg ) Let Position = 3   ILLUSTRATION INSERT BEFORE AN ELEMENT else { count =1; k = position; current = head; while (count <=(k-1) || current->next!=NULL) { current= current-> next; count++; } }

28. ALGORITHM & CODE STEP 3: iii. Traverse the list until the specified (k -1) th node is reached or End of List is reached  ( eg ) Let Position = 3   ILLUSTRATION INSERT BEFORE AN ELEMENT else { count =1; k = position; current = head; while (count <=(k-1) || current->next!=NULL) { current= current-> next; count++; } temp->next = current-> next; current-> next = temp }

29. ALGORITHM & CODE STEP 3: iii. Traverse the list until the specified (k -1) th node is reached or End of List is reached  ( eg ) Let Position = 3   ILLUSTRATION INSERT BEFORE AN ELEMENT else { count =1; k = position; current = head; while (count <=(k-1) || current->next!=NULL) { current= current-> next; count++; } } NULL

30. ALGORITHM & CODE STEP 3: iii. Traverse the list until the specified (k -1) th node is reached or End of List is reached  ( eg ) Let Position = 3   ILLUSTRATION INSERT BEFORE AN ELEMENT else { count =1; k = position; current = head; while (count <=(k-1) || current->next!=NULL) { current= current-> next; count++; } temp->next = current-> next; current-> next = temp } NULL NULL NULL NULL NULL

31. END OF INSERTION OPERATIONS