Skip to main content

Linked List using C++ part5


Linked List using C++ part5

In this tutorial, you will learn
1. Code of adding a node in middle of an ordered linked list.
2. Code for deleting a node in the middle of linked list.

What is the code for adding a node in any location in ordered linked list?

If you have read the previous tutorial, you already know that an ordered linked list is one in which data is arranged in ascending order. So when you add data in such a list, it must not distort the ascending order of list. Hence, you cannot add data anywhere in the list. Given below is the code for inserting node in linked list.

  1. void insert_order (int val)
  2. {
  3. if(checkempty())
  4. {
  5. InsertAtStart(val);
  6. return;
  7. }
  8. Node *new_node;
  9. new_node= new Node;
  10. new_node->data=val;
  11. Node *prev, *cur;
  12. prev=NULL;
  13. cur=head;
  14. if(val<head->data)
  15. {
  16. new_node->next=head;
  17. head=new_node;
  18. cout<<"\tNumber Inserted: "<<val<<endl;
  19. return;
  20. }
  21. else
  22. {while(cur!=NULL && val>cur->data)
  23. {
  24. prev=cur;
  25. cur=cur->next;
  26. }
  27. new_node->next=cur;
  28. prev->next=new_node;
  29. }
  30. }

In the above code, first it is checked if linked list is empty and if it is empty, simple insert at beginning would work. If it is not empty then we simply make a node and give it values like simple insertion. Now, if the element to be inserted is less than first element then we add it at start. Now, if this is also not true then we traverse the function and find a place for it. Note the conditions of while loop. curr!=Null is written first then second condition. If we wrote the second condition first then even when it pointed to null, the program would try to access data of curr. So curr!=NULL should always be written first.

What is the code for deleting a node in ordered linked list?

  1. void delete_order(int val)
  2. {
  3. Node *cur;
  4. cur=head;
  5. if (checkempty())
  6. {
  7. cout<<"Already empty"<<endl;
  8. }
  9. else if(head->data==val)
  10. {
  11. head=head->next;
  12. delete cur;
  13. cur=NULL;
  14. return;
  15. }
  16. else {while(cur->next!=NULL)
  17. {
  18. if(cur->next->data==val)
  19. {
  20. Node *d;
  21. d=cur->next;
  22. cur->next=cur->next->next;
  23. cout<<"\tNumber Deleted: "<<val<<endl;
  24. delete d;
  25. return;
  26. }
  27. cur=cur->next;
  28. }
  29. }
  30. cout<<" Number not found in the LIST\n";
  31.  
  32. }

Given above is the code for deleting a node in linked list . First you check whether the linked list is empty or not. If it is then deletion is not possible and if first element is to be deleted then We simply make a pointer and make it point to first element and then we make head point to second node and then deleting first node. If this is not the first element then we simply make a pointer and make it traverse till the node we want to remove and simply change to next pointer of node which is behind the node we want to delete to the node next to the node we want to delete and simply delete the node we want to delete.

Note : In next tutorial , copy constructor which has been deliberately delayed so that you would understand the basic concepts will be discussed and other than the copy constructor other functions would also be discussed .

Output:
output

Tags

Note: Due to the size or complexity of this submission, the author has submitted it as a .zip file to shorten your download time. After downloading it, you will need a program like Winzip to decompress it.

Virus note: All files are scanned once-a-day by SourceCodester.com for viruses, but new viruses come out every day, so no prevention program can catch 100% of them.

FOR YOUR OWN SAFETY, PLEASE:

1. Re-scan downloaded files using your personal virus checker before using it.
2. NEVER, EVER run compiled files (.exe's, .ocx's, .dll's etc.)--only run source code.

Add new comment

CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.