C++ Linked List Sort by Age

[Snaksa]

Hi guys! I'm new to this Forum and this is my first topic.I'm learning C++ for around 5 months just for fun - this is something like a hobby to me. Everything was going good since I started learning Linked Lists. Finally I found a good source to learn how to do them. I know how to add a node and delete a node from the beginning and from the end of the List. Now I want to sort the List by Age. I tried everything but there must be a very little mistake that I can't find. I hope you can help me. Here is my code:

#include <iostream>
using namespace std;

struct Node
  {
    char name[20];
    int age;
    double height;
    Node *next;     
  };
  Node *start_ptr = NULL;

void add_node_at_end ()
  {
  Node *temp, *temp2; // Temporary pointers
  // Reserve space for new node and fill it with data
  temp = new Node;
  cout << "Please enter the name of the person: ";
  cin >> temp->name;
  cout << "Please enter the age of the person : ";
  cin >> temp->age;
  cout << "Please enter the height of the person : ";
  cin >> temp->height;
  cout << endl;
  temp->next = NULL;
  // Set up link to this node
  if (start_ptr == NULL)
     start_ptr = temp;
  else
    {
      temp2 = start_ptr; // We know this is not NULL - list not empty!  
      while (temp2->next != NULL)
        temp2 = temp2->next; // Move to next link in chain
      temp2->next = temp;
    }
  } 
  
void delete_start_node()
  {
    Node *temp;
    temp = start_ptr;
    start_ptr = start_ptr->next;
    delete temp;
  } 
  
void delete_end_node()
  {
    Node *temp1, *temp2;
    if (start_ptr == NULL)
      cout << "The list is empty!" << endl;
      else
        {
          temp1 = start_ptr;
          if (temp1->next == NULL)
            {  
              delete temp1;
              start_ptr = NULL;
            }
            else
              {
                while (temp1->next != NULL)
                  {
                    temp2 = temp1;
                    temp1 = temp1->next;
                  }
                delete temp1;
                temp2->next = NULL;
              }
            }
  }   
  
void sort_age()
  {
    Node *temp1, *temp2; 
    temp1 = start_ptr;
    while(temp1 != NULL)
      {
        temp2 = temp1->next;
        if(temp1->age > temp2->age)
          {
            Node *help = temp1;
            temp1 = temp2;
            temp2 = help;            
          }  
        temp1 = temp1->next;                
      }            
  }  

void print_node()
  {
    Node *temp;
    temp = start_ptr;
    if(temp == NULL) cout << "Empty List!" << endl;
    while(temp != NULL)
      {
        if(temp == NULL) cout << "Empty List!" << endl;
        cout << "Name   : " << temp->name << endl;
        cout << "Age    : " << temp->age << endl;
        cout << "Height : " << temp->height << endl;
        cout << endl;  
        temp = temp->next; 
      }           
  } 

int main()
{
    int n;
    cout << "n= ";
    cin >> n;
    for(int i = 0; i <= n-1; i++)
      {
        add_node_at_end();      
      }
    print_node();
    cout << "---------------------------------------------" << endl;
    sort_age();
    print_node();  
    system("pause");
    return 0;
}

P.S
I made for() loop in the sort function but it still doesn't work :/

void sort_age()
  {
    Node *temp1, *temp2; 
    for(temp1 = start_ptr; temp1->next != NULL; temp1 = temp1->next) 
      {
	for(temp2 = temp1->next; temp2->next != NULL; temp2 = temp2->next)
          {
            if(temp1->age > temp2->age)
              {
                Node *help = temp1;
                temp1 = temp2;
                temp2 = help;            
              }                
          }  
      }              
  }

[D80DSL3A]

What happens when sort_age() is called? I'm guessing that the list is unchanged.
This is because the assignments made in the function apply only to the local variables temp1 and temp2. You are changing which nodes these point to but not which nodes point to which others in the list. You will need to change the values of next for the nodes being swapped, as well as the next for the node preceding these two.

Consider this, where prev, A, B and C are nodes in the list such that:
prev->A->B->C and we wish to swap the order of nodes A and B to produce:
prev->B->A->C.

You need to assign prev->next = B; then A->next = C; then B->next = A; all without losing any of the pointers in the process (ie. by using a temp* to hold a value).

Also, your sort_age() makes only one pass through the list so even if it worked as desired you would only get the nodes to 'bubble' one place along.
As with the regular bubble sort multiple passes must be made to complete the sort.

Hope this helps. I have a function for swapping adjacent nodes in a linked list class of my own. I can post it if the above hints aren't enough and you would like to see it.

[writetonsharma]

by the time i looked at your old for loop, you wrote a new one...!! ;-)

anyway... the logic has some problems.. for example, in the new one, you are changing the pointers but the next is not updated correctly...

I think you need to make a new logic.. don't try to do sorting in the same list.. make a new list and take out pointer from the old one and put in the new one.. keep the new one sorted at all times. To start with, dont look for speed, just try to be correct. So, its going to be O(n^2) in the beginning.

something like this:

loop till there are nodes in old list
  pick first node
  loop till the end of new list
    if its the first node, put in head
    else see where you can put the node in the new list. keep it sorted.
    remove the node from the old list
    update the next pointer in the new list and other things.

something like this..

Edit: the indentation.

[Snaksa]

Thanks for the answer. But I have a little problem. I couldn't find a tutorial with two linked lists in one program and I don't know how to define them. Should I make a new structure? Or I just need to use variables with different names?
Please give me a hint. :)

[SIK]

try to not swap nodes around, instead just swap the contents (data) of the nodes.

create a function/method like:

void swap_node_data(Node * n1, Node * n2)
{
   char tmpName[20];
   strcpy(tmpName, n1->name);
   strcpy(n1->name, n2->name);
   strcpy(n2->name, tmpName);

   int tmpAge = n1->age;
   n1->age = n2->age;
   n2->age = tmpAge;

   double tmpHeight = n1->height;
   n1->height = n2->height;
   n2->height = tmpHeight;
}

you may want to consider using the stl swap method within your method to avoid the temporary variables used for swapping.

you should then call to this method swap_node_data within your sort_age method.

[D80DSL3A]

Reassigning the links is the most efficient way. You're making just a few pointer assignments instead of copying the entire data payload around. I don't know why SIK recommends against it. He didn't say. It is a bit tricky though.

I don't know of any good tutorials. Setting up 2 lists can be done by declaring and using another pointer like start_ptr. Maybe Node* start_ptr2 ?

Any of the 3 methods offered above should work. Take your pick.

[writetonsharma]

yes, as fun2code said... take just another variable and keep adding to it.. in the end, old head (start_ptr) will have nothing and you get a new sorted list in start_ptr2;
swapping data can be slow when the nodes are big.. lets say you are saving big streams..

[Snaksa]

Thanks for the answers guys. SIK's method worked. But I still find difficulty to make a new list. fun2code, can you show me your code please? writetonsharma, I saw your advice but I still can't write the code. Here is the code that I did:

void sort_age()
  {
        Node *temp1, *start_ptr2 = NULL;
        temp1 = start_ptr;
        while(temp1->next != NULL)
          {
            while(start_ptr2->next != NULL)
              {
                if(start_ptr2 == NULL) 
                  {
                    start_ptr2 = temp1; 
                    start_ptr2->next = NULL;
                  }
                else
                  {
                    if(temp1->age > start_ptr2->age)
                      {
                        start_ptr2 = temp1;
                        delete temp1;            
                      }           
                  }
              }     
          }   
  }

[D80DSL3A]

On reading writetonsharma's 2nd post I think his would be the best method.
Here's my function for swapping adjacent nodes, which could be used to support a bubble sort, but I think that would be an overcomplicated solution now.

The function takes a pointer to the Node preceding the pair to be swapped. If the pair is start_ptr and start_ptr->next then pass NULL as the value for prev.
Substitute 'start_ptr' for 'head' in my code:

void swap_adjacent(Node* prev)// prev->A->B->C
{
    if(prev)
    {
        if(prev->next && prev->next->next)
        {
            Node* temp = prev->next;// temp points to A
            prev->next = temp->next;// prev->next points to B
            temp->next = prev->next->next;// A->C
            prev->next->next = temp;// B->A
        }// result: prev->B->A->C
    }
    else if(head && head->next)// swap head with head->next
    {
        Node* temp = head->next;
        head->next = temp->next;
        temp->next = head;
        head = temp;
    }
}

I'll be attempting to implement writetonsharmas algorithm too, but I haven't the time right now. I'll post back with it later.
Perhaps writetonsharma will beat me to it?

Line 19 in your code looks like trouble. No Nodes should be deleted. We just want to change how they're linked together.

[Snaksa]

Thanks for the help fun2code! Your example confused me a little, but I'm looking forward to see the implement of writeonsharma's algorithm. :)

P.S And just one more little question. Can you tell me in which variable my list is stored? In start_ptr, right? Sorry for the silly question but I got very confused...

[writetonsharma]

Very nice start..!!

let me try to edit the code for you...

void sort_age()
{
    Node *temp1, *start_ptr2 = NULL;
    temp1 = start_ptr;
    while(temp1->next != NULL)
    {
		if(start_ptr2 == NULL) 
		{
			start_ptr = temp1;
			temp1 = temp1->next;		//temp1 will move forward.
			start_ptr2 = start_ptr; 
			start_ptr2->next = NULL;
			
			continue;
        }

		//take the first node from the old list, detach it and place it at a correct place in the new list
		start_ptr = temp1;
		temp1 = temp1->next;
		start_ptr->next = NULL;			//the first node is an independent node now. will be placed in the new one

		Node* temp2 = start_ptr2;		//dont move start_ptr2 otherwise we will loose the head of new list
        while(temp2->age < start_ptr->age)
        {
			temp2 = temp2->next;
			if(temp2 == NULL)
				break;

		}

		//here start_ptr's age is less then temp2's age.
		//three cases - either it needs to be put at the beginning, middle or end.
		if(temp2 == start_ptr2)
		{
			//first node
			start_ptr->next = temp2;
			start_ptr2 = start_ptr;
		}
		else if(temp2 == NULL)
		{
			//last node
			temp2->next = start_ptr;
		}
		else
		{
			//some where in the middle.. do it yourself????


		}       
	}
}

I have not debugged the code.. just wrote it.. see how much it works.. but it will give you an idea, what needs to be done.. try to go from here..

[cire]

Ordinarily, I wouldn't do this, but the following is an implementation of a merge sort algorithm (which is generally the "goto" sort for linked lists,) but, whether or not you grasp what the mergesort is doing, I think you could benefit from looking at the style of the implementation, in particular the way a Node* is passed to and from different functions.

I also inserted some output into the mergesort function that should be removed, but I thought it might be instructional for you to see.

For further information on the sort algorithm:
http://en.wikipedia.org/wiki/Merge_sort

#include <iostream>
using namespace std;

struct Node
  {
    char name[20];
    int age;
    double height;
    Node *next;     
  };
  Node *start_ptr = NULL;

// list: the list to be sorted.
// less_than: a pointer to a function which compares two nodes.
// returns: a pointer to the sorted list.
Node* mergesort(Node* list, bool(*less_than)(Node*, Node*)) ;

// the function we're using to compare two nodes.
bool age_is_less( Node* a, Node* b )
{
    return a->age < b->age ;
}

// list: The list to be appended to.
// add_me: the list or item to be appended.
void append(Node*& list, Node*add_me)
{
    if ( list == 0 )
        list = add_me ;
    else
    {
        Node * current = list ;

        while ( current->next )
            current = current->next ;

        current->next = add_me ;
    }
}

// list: The list
// returns: number of items in list.
unsigned length(Node* list)
{
    if ( !list )
        return 0 ;

    unsigned i=1 ;
    while ( (list = list->next) )
        ++i ;

    return i ;
}

// list: The list.
// nth: the number of node we're looking for.
// returns:  a pointer to the nth node in list.
Node* nth_node( Node* list, unsigned nth )
{
    Node* current = list ;
    unsigned i=0;
    while ( i++ < nth )
        current = current->next;
    return current ;
}


// list_a: one of the (sorted) lists to be merged
// list_b: one of the (sorted) lists to be merged.
// less_than: the comparison function for determing the order of Nodes.
// returns: a list consisting of the elements of both list_a and list_b in
//      the order determined by less_than.
// This function is really an implementation detail of mergesort.
Node* merge(Node* list_a, Node* list_b, bool(*less_than)(Node*,Node*)) ;

std::ostream& operator<<(std::ostream& os, const Node* list)
{
    os << "{ " ;
    const Node* current = list ;
    while ( current )
    {
        os << current->age << ' ' ;
        current = current->next ;
    }
    return os << "}" ;
}

Node* mergesort(Node* list, bool(*less_than)(Node*, Node*))
{
    std::cout << "mergesort entered: " << list << '\n' ;

    if ( !list || !list->next )
        return list ;

    unsigned len = length(list) ;

    Node* left_list = list ;
    Node* nth = nth_node(left_list, (len/2)-1) ;
    Node* right_list = nth->next ;
    nth->next = 0 ;

    std::cout << "\tsplit: " << left_list << " + " << right_list << '\n' ;

    left_list = mergesort(left_list, less_than) ;
    std::cout << '\n' ;
    right_list = mergesort(right_list, less_than) ;
    std::cout << '\n' ;

    std::cout << "\tsorted: " << left_list << " + " << right_list << '\n' ;
    
    return merge(left_list, right_list, less_than) ;
}

Node* merge( Node* list_a, Node* list_b, bool (*less_than)(Node*,Node*) )
{
    Node* result=0 ;

    while ( list_a || list_b )
    {
        if ( list_a && list_b )
        {
            if ( less_than(list_a, list_b) )
            {
                Node * next = list_a->next ;
                list_a->next = 0 ;
                append(result, list_a) ;
                list_a = next ;
            }
            else
            {
                Node* next = list_b->next ;
                list_b->next = 0 ;
                append(result, list_b) ;
                list_b = next ;
            }
        }
        else if ( list_a )
        {
            Node* next = list_a->next ;
            append(result,list_a) ;
            list_a = 0 ;
        }
        else
        {
            Node* next = list_b->next ;
            append(result, list_b) ;
            list_b = 0 ;
        }
    }

    return result ;
}

void add_node_at_end ()
  {
  Node *temp, *temp2; // Temporary pointers
  // Reserve space for new node and fill it with data
  temp = new Node;
  cout << "Please enter the name of the person: ";
  cin >> temp->name;
  cout << "Please enter the age of the person : ";
  cin >> temp->age;
  cout << "Please enter the height of the person : ";
  cin >> temp->height;
  cout << endl;
  temp->next = NULL;
  // Set up link to this node
  if (start_ptr == NULL)
     start_ptr = temp;
  else
    {
      temp2 = start_ptr; // We know this is not NULL - list not empty!  
      while (temp2->next != NULL)
        temp2 = temp2->next; // Move to next link in chain
      temp2->next = temp;
    }
  } 
  
void delete_start_node()
  {
    Node *temp;
    temp = start_ptr;
    start_ptr = start_ptr->next;
    delete temp;
  } 
  
void delete_end_node()
  {
    Node *temp1, *temp2;
    if (start_ptr == NULL)
      cout << "The list is empty!" << endl;
      else
        {
          temp1 = start_ptr;
          if (temp1->next == NULL)
            {  
              delete temp1;
              start_ptr = NULL;
            }
            else
              {
                while (temp1->next != NULL)
                  {
                    temp2 = temp1;
                    temp1 = temp1->next;
                  }
                delete temp1;
                temp2->next = NULL;
              }
            }
  }   
  
void sort_age()
  {
      start_ptr = mergesort(start_ptr, age_is_less) ;
  }  

void print_node()
  {
    Node *temp;
    temp = start_ptr;
    if(temp == NULL) cout << "Empty List!" << endl;
    while(temp != NULL)
      {
        if(temp == NULL) cout << "Empty List!" << endl;
        cout << "Name   : " << temp->name << endl;
        cout << "Age    : " << temp->age << endl;
        cout << "Height : " << temp->height << endl;
        cout << endl;  
        temp = temp->next; 
      }           
  } 





int main()
{
    int n;
    cout << "n= ";
    cin >> n;
    for(int i = 0; i <= n-1; i++)
      {
        add_node_at_end();      
      }
    print_node();
    cout << "---------------------------------------------" << endl;
    sort_age();
    print_node();  
    system("pause");
    return 0;
}

[D80DSL3A]

Here's my implementation of writetonsharma's sort algorithm, as I understand it.

I developed and tested it in my own list class, where I found it works, but I've adapted it to your methods. This adaptation is untested so I hope it still works.

I am using your original code for everything except the sort_age() function and another function
Node* remove_next(Node* prev)which removes a Node from the list and returns a pointer to that Node. It is used as a "helper" function inside sort_age() to split up the tasks somewhat. This function takes a pointer to the Node preceding the one to be removed.

#include <iostream>
using namespace std;

struct Node
  {
    char name[20];
    int age;
    double height;
    Node *next;     
  };
  Node *start_ptr = NULL;

void add_node_at_end ()
  {
  Node *temp, *temp2; // Temporary pointers
  // Reserve space for new node and fill it with data
  temp = new Node;
  cout << "Please enter the name of the person: ";
  cin >> temp->name;
  cout << "Please enter the age of the person : ";
  cin >> temp->age;
  cout << "Please enter the height of the person : ";
  cin >> temp->height;
  cout << endl;
  temp->next = NULL;
  // Set up link to this node
  if (start_ptr == NULL)
     start_ptr = temp;
  else
    {
      temp2 = start_ptr; // We know this is not NULL - list not empty!  
      while (temp2->next != NULL)
        temp2 = temp2->next; // Move to next link in chain
      temp2->next = temp;
    }
  } 

void delete_start_node()
  {
    Node *temp;
    temp = start_ptr;
    start_ptr = start_ptr->next;
    delete temp;
  } 
  
void delete_end_node()
  {
    Node *temp1, *temp2;
    if (start_ptr == NULL)
      cout << "The list is empty!" << endl;
      else
        {
          temp1 = start_ptr;
          if (temp1->next == NULL)
            {  
              delete temp1;
              start_ptr = NULL;
            }
            else
              {
                while (temp1->next != NULL)
                  {
                    temp2 = temp1;
                    temp1 = temp1->next;
                  }
                delete temp1;
                temp2->next = NULL;
              }
            }
  } 

void print_node()
  {
    Node *temp;
    temp = start_ptr;
    if(temp == NULL) cout << "Empty List!" << endl;
    while(temp != NULL)
      {
        if(temp == NULL) cout << "Empty List!" << endl;
        cout << "Name   : " << temp->name << endl;
        cout << "Age    : " << temp->age << endl;
        cout << "Height : " << temp->height << endl;
        cout << endl;  
        temp = temp->next; 
      }           
  } 

// the "helper" function used in sort_age()
Node* remove_next(Node* prev)// pass NULL if start_ptr is the Node to be removed
{
    if(prev)
    {
        if( prev->next )// ensure prev isn't pointing to the last Node in the list
        {
            Node* temp = prev->next;// temp will be removed
            prev->next = temp->next;// link across temp
            return temp;
        }
    }
    else if(start_ptr)// ensure list not empty
    {
        Node* temp = start_ptr;// start_ptr will be removed
        start_ptr = start_ptr->next;
        return temp;
    }

    return NULL;// if called on empty list, or if prev->next is NULL
}

void sort_age()// sort by age in ascending order
{
    Node* start_ptr2 = NULL;// head of sorted list

    while(start_ptr)// repeat until no nodes left in unsorted list
    {
        // pointers for iterating through the unsorted list
        Node* prev = NULL;// always previous to the current node considered (below)
        Node* curr = start_ptr;// start at beginning of list
        Node* prevMax = NULL;// pointer to node before the node with the highest age
        int max = start_ptr->age;// 1st node holds max age to start

        while(curr)// iterate through the list
        {
            if(curr->age > max )// new highest age found
            {
                max = curr->age;// save new max age
                prevMax = prev;// save pointer to node before the max
            }
            prev = curr;// advance iterators
            curr = curr->next;
        }
        
        // Node with the highest age found this pass through the list.
        Node* xferNode = remove_next(prevMax);// obtain node to be moved into sorted list
        if( xferNode )// check that it's not NULL
        {
            xferNode->next = start_ptr2;// add to beginning of sorted list
            start_ptr2 = xferNode;
        }
    }
    start_ptr = start_ptr2;// list now sorted. Reassign start_ptr to point to it.
}

int main()
{
    int n;
    cout << "n= ";
    cin >> n;
    for(int i = 0; i <= n-1; i++)
      {
        add_node_at_end();      
      }
    print_node();
    cout << "---------------------------------------------" << endl;
    sort_age();
    print_node();  
    system("pause");
    return 0;
}

EDIT: I forgot to answer your question:

Can you tell me in which variable my list is stored? In start_ptr, right?

The list isn't "stored in" start_ptr itself. The list exists as Nodes in memory. start_ptr merely points to the first Node in the list of Nodes. From there each Nodes next member points to the next Node, until next = NULL which marks the end of the list.

[Snaksa]

Thank you very much for the help guys :)