insertion sort of a linked list of strings.

[tkauffman2]

Hello guys,
What I need to do is sort my linked list alphabetically by last name as I enter it into my list. I have it where you can enter into the list by the command:
insert<>first name<>last name<>phone number<>email and it enters into the list.
but I have no idea how to enter it alphabetically. Thank you :D

Header:

//addr_list.h
//Kauffman,Tyler
//tkauffman

#ifndef ADDR_LIST_H
#define ADDR_LIST_H

class Addr_list
{
    public:
        Addr_list();
        ~Addr_list();
        void insert(string fname,string lname,string phnum,string email);
        void remove(string fname,string lname);
        void print();
    private:	
	  class Address
          {
	       public:
		    Address (string fname, string lname, string phnum, string email, Address *next)
		    {m_fname=fname, m_lname=lname, m_phnum=phnum, m_email=email,m_next=next;}
		    string m_fname,m_lname,m_phnum,m_email;
		    Address *m_next;
		    
    };
    Address *m_head;
};

#endif 

main:

//abook.cpp
//Kauffman,Tyler
//tkauffman

#include <iostream>
#include <string>
#include<algorithm>

using namespace std;
#include "addr_list.h"
int main()
{
    string insert = "insert";
    int i;
    string command;
    string fname,lname,phnum,email;
	Addr_list *list = new Addr_list;	
	
        while (cin>>command)
        {
		if(command == "insert")
		{
		cin >> fname>>lname>>phnum>>email;
		
		list -> insert (fname,lname,phnum,email);
		list -> print();
		
		}
		if (command == "remove")
		{
		//cout << "remove was called " <<endl;	
		list ->remove(fname,lname);	
		}
		else if (command != "insert"&& command != "remove")
		{
		cerr<< "Wrong"<<endl;
		}
	}

}

program:

//addr_list.cpp
//Kauffman,Tyler
//tkauffman

#include <iostream>
using namespace std;
#include "addr_list.h"

Addr_list::Addr_list()
{
    m_head = NULL;
}
Addr_list::~Addr_list()
{
    Address *ptr = m_head;
    while (ptr != NULL)
    {
       Address *temp;
    
        temp = ptr;
        ptr = ptr->m_next;
        delete temp;
    }
}

void Addr_list::insert(string fname, string lname,string phnum, string email)
{
  m_head = new Address(fname,lname,phnum,email, m_head);
 // cout << fname<<" " << lname << " "<< phnum<<" "<< email<<endl;
}
void Addr_list::remove(string fname, string lname)
{
	//cout<<"remove function was called " << endl;
}
// iterate through all the Nodes in the list and print each Node
void Addr_list::print()
{
       Address *ptr = m_head; 
       cout << ptr->m_fname<<ptr -> m_lname<<":"<<ptr->m_phnum<<","<<ptr->m_email<<endl;
       ptr = ptr->m_next;
    

}

[onur]

I think by "enter it alphabetically" you mean the list is sorted alphabetically (last name first, then first name)

If you would internally use a vector from the standard library instead of your own singly linked list, you could use some sort algorithm.

Sorting with singly linked lists doesn't make sense in my opinion.

I see at least three options:
* replace your singly linked list with a standard container like vector or deque which can be sorted
* replace your singly linked list with a standard container like set (the key should reflect the sort criteria) which is always sorted
* copy your singly linked list to a standard container, sort this container and copy it back.

For containers see: http://www.cplusplus.com/reference/stl/
For sorting algorithms see: http://www.cplusplus.com/reference/algorithm/

[tkauffman2]

My assignment is to just sort the linked list , I think its in the main insert function. I would also learn to do it the harder way before I use the advanced easy way .. :D thanks

[D80DSL3A]

It looks like you have this set up to work as a stack.
Clever idea passing head in the Address constructor for use as next.
That won't work if you need to insert the new Address somewhere other than before the existing list head.

I just worked a similar exercise myself except I implemented my ordered list as a template class (so it could work with any object, not just an Address object).

I found it necessary to overload the < (comparison) operator in the target class to make the insert() work. How are you with operator overloading?
I coincidentally chose a target class to try out this ordered list on which uses names for the ordering!

bool Person::operator<(const Person& p) const
{
	if( lastName < p.lastName )
		return true;
	if( lastName == p.lastName && firstName < p.firstName)
		return true;

		return false;
}

I also had to overload == to make the remove() work.

bool Person::operator==(const Person& p) const
{
	return( lastName == p.lastName && firstName == p.firstName);
}

Here's my insert(), in case you can get anything useful out of it. Just substitute Address where you see <T> and it may make sense:

template<class T>
void orderedList<T> :: insert(const T& item)
{
	if(head)
	{
		// check against head->data
		if( item < head->data )// here's why < must be overloaded
		{
			node<T> *t=new node<T>;
			t->data = item;
			t->next = head;
			head = t;// new head
			return;
		}
		// go further into list
		node<T> *iter = head;
		while( iter->next )	
		{
			if(  iter->next->data < item )
				iter = iter->next;
			else
				break;
		}	
		// insert node 
		node<T> *t=new node<T>;
		t->data = item;
		t->next = iter->next;
		iter->next = t;
	}
	else// new item starts list
	{
		head = new node<T>;
		head->data = item;
		head->next = NULL;
	}
}

This function is working great.

[bluecoder]

Hi ,
Why are you not using structure instead of the class Address .
Also you can use bubble sort method on the fist name of each node to sort link list .
This will be quit simple.