sorting linked list of names

[WaveK89]

I'm trying to figure out a good way of alphabetizing a linked list of names where every two nodes consist of a first name and a last name. The program I am working on needs to be done using the list STL. I figured some form of bubble sort would work, but I probably would need to loop it since the list cannot be sorted in one scan. I guess with the use of the iterator and temporary values I could just copy, erase, and insert. Anyway, I was wondering if anyone had any word of advice?

Also, I'm wondering if it's possible to make a list of structs. I have a typedef struct consisting of two char values which fit firstname and lastname. I wasn't sure what the intent was. Anyway, my main concern is trying to grasp the concepts of linked lists.

[helios]

I think Insertion Sort was better for lists since it only accesses adjacent links (Bubble Sort has the same property, actually, but it's slower).

Sure it is.

[WaveK89]

Yeah, I was looking at insertion sort, and it looked to be the easier route. Using an iterator would easily solve the issue.

I guess my next question for structs would be the case of using refrence lastName within the struct to sort the list alphabetically. I just am not sure how to take the name for a .dat file and insert it into the list.

[seymore15074]

You could just use the STL sort algorithm.

[jsmith]

But sort() requires random access iterators and list does not provide that, so I don't think sort() can be used.

Sorting STL lists is extremely expensive because of this. I would use insertion sort.

[Actually, I wouldn't use list in this case, but since you are forced to...]

[WaveK89]

Well, I figured it might be relatively easier to insert the list into a vector and sort, but I think the whole idea of using a linked list ruins the idea. Even if I could use sort(), it wouldn't work because I need the first and last names to be adjacent with one another. Now I just need to configure the insertion sort to look at every other value in the list.

[jsmith]

It would work.

struct Person {
   std::string firstName;
   std::string lastName;

   explicit Person( const std::string& first = std::string(), 
       const std::string& last = std::string() ) :
       firstName( first ), lastName( last ) {}

   bool operator<( const Person& rhs ) const
       {
            if( lastName < rhs.lastName ) return true;
            if( rhs.lastName < lastName ) return false;
            return firstName < rhs.firstName;
        }
};

And now sort() will do exactly what you want.

[WaveK89]

Quite frankly, I'm not even sure if I understand the point of a linked list let alone a list. This program seems like a lost cause to me.

bdostruct.h

typedef struct
{
	char *firstName;
                char *lastName;
} binaryDataOrg_T;

source code

#include <iostream>
#include <fstream>
#include <list>
#include <string>

#include "bdostruct.h"

using namespace std;

list<binaryDataOrg_T> bdoList;
list<binaryDataOrg_T> iter;

binaryDataOrg_T first;
binaryDataOrg_T last;

int main()
{

	ifstream fin;
	
	// open data file
	fin.open("bdostruct.dat");

	// insert names into a linked list
	while (true)
	{
		fin >> first;
		if (!fin)
			break;

		fin >> last;
		if (!fin)
			break;

		bdoList.push_front(last);
		bdoList.push_front(first);
	}

	// sort implementation
	for (iter = bdoList.begin(); iter < bdoList.size(); iter + 2)
	{
		j = iter;
		target = *iter;

		while (j > 0; && target < *(j - 2))
		{
			*j = *(j - 2);
			j = j - 2;
		}
		*j = target
	}

	// output sorted list
	while (!bdoList.empty())
	{
		iter = bdoList.begin();
		cout << *iter << " " << *(iter + 1) << endl;
		iter = iter + 2;
	}

	system("pause");
}

[jsmith]

An STL list is a class implementation of a linked list which manages the pointers for you. It just makes using a linked list much, much easier.

You have many errors in the above code.

First, if you are allowed to, use std::string instead of char* in your struct.
If you aren't, I suggest using a fixed size array of chars (if allowed). It's
not as flexible, but it will work for your assignment.

Second, your while() loop is wrong because first and last are both instances of your struct, and your struct already has a first and last name. If using std::string or fixed length char array, try fin >> first.firstName and fin >> first.lastName.

Third, you need only one list, because each element of your list again holds both names.

Fourth, your for() loop increment is wrong because it does nothing. "iter + 2" , even if it were legal syntax for a list iterator, is just an expression that returns the sum (which you then ignore) and does not modify iter.

Fifth, most of the body of the for loop is wrong because a) you can't add integers to list iterators; b) you have a syntax error on line 45.

Sixth, the last while loop is also wrong because the list will either always be empty or never be empty, which means your loop either doesn't loop at all or loops infinitely.