Linked List using C++ part5

Submitted by: 

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";
  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 .


Add new comment

Filtered HTML

  • Web page addresses and e-mail addresses turn into links automatically.
  • You may insert videos with [video:URL]
  • Allowed HTML tags: <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd> <table> <tr> <td> <th> <img> <h1> <h2> <h3> <iframe> [video]
  • You can enable syntax highlighting of source code with the following tags: <code>, <blockcode>, <asp>, <c>, <cpp>, <csharp>, <css>, <html4strict>, <java>, <javascript>, <mysql>, <php>, <python>, <sql>, <vb>, <vbnet>. The supported tag styles are: <foo>, [foo].
  • Lines and paragraphs break automatically.

Plain text

  • No HTML tags allowed.
  • Lines and paragraphs break automatically.
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.