• 02-19-2010
Fatima Rizwan
I have made a linked list with the following functions.
Code:

```class node { public:         int data;                        node* next; }; class linkedList: public node {         node* head; public: linkedList() void insertEnd( int data)                      // Inserts the node at end void insertStart(int data)                      // Inserts the node at start void search(int l)                                  // Searches the data in nodes void deleteAnode(int l)                        // Delete any node (expect first or last) void deleteSNode()                            //  Delete start node  void deleteENode()                            //  Delete end node```
Now i want to make a function like which inserts a node in between two nodes.
So I have to take the nodes data , between which i want to add a new node?

Would it be like this ?
Code:

```void insertAnywhere( int previous, int next, int new) { }```
Or is there a better way kindly tell.
• 02-19-2010
Dino
Since you have a singly-linked, forward-only linked list, and you want to insert a new node (C) between two existing nodes (A and B), it will be a waste of time to pass the second link (B) in the parm list.

Check A.next for NULL. If NULL, set A.next to C and you are done.

However, if A.next is not NULL, then set C.next to the value in A.next, then you can set A.next to C.

EDIT: Actually, that's too much checking, and I assume you are using NULL for a placeholder. This can be done blindly with the following logic:
1) set C.next to the value from A.next
2) set A.next to C.
• 02-19-2010
Fatima Rizwan
Code:

```void Sort()         {         node* first;         node* second;         node* temp;                 first=head;                                 while(first->next!=NULL)                 {                         second=first->next;                         while(second->next!=NULL)                         {                                                 if(first->data < second->data)                                 {                                         temp = new node;                                         temp->data=first->data;                                         first->data=second->data;                                         second->data=temp->data;                                         delete temp;                                 }                         second=second->next;                         }                                         first=first->next;                 }         }```
This is the sorting function for the singly linked list , but it does not sort the list . Plus i want to know if there is another better way?
• 02-19-2010
Dino
A better way is to rearrange the list, rather than allocate new and delete throughout the loop.
• 02-19-2010
Fatima Rizwan
how ??
• 02-19-2010
Dino
By swapping pointers using temp, but temp is statically allocated in your sort function. You'll need to carry three pointers: previous, current and next.
• 02-20-2010
iMalc
Use Insertion Sort:

Use two lists. Take an item out of your unsorted list, and "insert" it into your new sorted list, by moving along the list to the right position before inserting it.
Repeat until your first list is empty, then your second list contains the sorted data.
Now swap the second list with your original one (actually just copy the head pointer across) and you're done.

This is the simplest method of sorting a singly-linked-list.