Storing objects in a linked list and sorting

[mreinecker]

For the life of me, I cannot find an answer to this question, partially due to my lack of experience and understanding.

My question is, if I create a class that stores a name, birthday, address, etc in each object instantiated from the class, can I then put each object in a linked list (it has to be a linked list) and then sort the items in the list alphabetically?

I'm not sure what value is used when sorting, but I would like the sorting to use the member name in each object for alphabetical sorting.

My guess for doing this would be to overload the < and > operators for my class to compare each objects name. Would this work?

[48T7M4Gy]

A linked list can be used to link objects of any type you like to design.

If you have objects of type Person, where Person is a struct/class which encapsulates name address etc then the pointers in the Node and list design need to be Person* head, next, etc, ie Person pointers

If you are sorting on name then your sort function/method would sort on Person.name

string 'compare' is a good key word to start for looking up possibilities with sorting

[jonnin]

while you can sort a linked list, a common approach to the issue is to 'insert where it goes' so the list is always sorted without an extra sort routine. That way every insert you just crawl through the list, fine where it goes, and put it there. This is one of the strongest features of a linked list (insert anywhere without moving the other data).

I highly recommend your list to be apart from your data. that is, you have a list that stores something, and all that class does are linked list operations -- add, removed insert sorted, etc functions. Ideally this would be a template class, but if you are not there yet at the very least you can swap which data class it uses and recompile it without any other changes.

you data class needs to be its own class, and THAT class will (or may) have overloaded comparison operators.

[JLBorges]

> My guess for doing this would be to overload the < and > operators for my class
> to compare each objects name. Would this work?

Yes; it is sufficient if the class is LessThanComparable

The other option is to provide a custom predicate to compare objects.

Sorting a list is quite efficient; average complexity O( N log N )
See: http://en.cppreference.com/w/cpp/container/list/sort

Inserting into the list maintaining sorted order is inefficient; O( N*N )

Trivial example:

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

struct person
{
    std::string name ;
    std::string birthday {} ;
    std::string address {} ;
    int phone = 0 ;
    // ...
};

bool operator< ( const person& a, const person& b ) { return a.name < b.name ; }

int main()
{
    std::list<person> lst { {"Sutter"}, {"Smith"}, {"Wakely"}, {"Nelson"}, {"Miller"} } ;

    lst.sort() ; // default; person must be LessThanComparable
    for( const person& p : lst ) std::cout << p.name << ' ' ;
    std::cout << '\n' ;

    // sort with a user provided predicate (person need not be LessThanComparable)
    // sort in descending order of names
    lst.sort( [] ( const person& a, const person& b ) { return a.name > b.name ; } ) ;
    for( const person& p : lst ) std::cout << p.name << ' ' ;
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/8c2d73f2be83c250

[jonnin]

Ill be honest I am not sure how to do an N lg N on a *student type* list (not one with a vector hidden under the hood where you array-sort it and rebuild the pointers after or the like) because you can't jump into the middle of it to cut it in half (quick sort ideas) or skip-list it (shell short ideas). What am I missing? Thinking grab 2, sort, grab 2, sort ... then mergesort those, repeat until its all back together, maybe?

[JLBorges]

> Thinking grab 2, sort, grab 2, sort ... then mergesort those, repeat until its all back together, maybe?

Yes.

The standard specifies that:
a. The complexity is approximately N log N comparisons, where N == size()
b. It must be a stable sort
c. The elements in the list need not be swappable
d. The validity of iterators and references to elements in the list must be preserved.

This strongly suggests using a variant of in-place merge sort (which just updates the links).

[mreinecker]

Thanks for the quick responses. I think the part where I'm getting confused is if I have a class person, as in the example by JLBorges:

    class Person {
    private:
        std::string name ;
        std::string birthday {} ;
        std::string address {} ;
        int phone = 0 ;
    public:
        Person (string name_in, string bday_in, string address_in, int phone_in){
            this->name = name_in;
            this->birthday = bday_in;
            this->address = address_in;
            this->phone - phone_in;
        }
        // ...
    };

When instantiating an object of this type and inserting it into the list, what about the other data members?

    std::list<person> lst { {"Sutter"}, {"Smith"}, {"Wakely"}, {"Nelson"}, {"Miller"} } ;

What if I did

    lst.push_back(new person(arguments))

Would that work, and store all of the data for the object, yet still let me sort by name?

[JLBorges]

> What if I did lst.push_back(new person(arguments))

Instead, you do lst.push_back( Person(arguments) ) ; // no new


> yet still let me sort by name

As written, name is private; you won't be able to access it.
Provide an accessor for name, and you would be able to sort by name.

For example:

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

class Person {
    private:
        std::string name_ ;
        std::string birthday_ ;
        std::string address_ ;
        int phone_ = 0 ;

    public:

        Person ( std::string name, std::string bday, std::string address, int phone )
            : name_(name), birthday_(bday), address_(address), phone_(phone) {}

        const std::string& name() const { return name_ ; }
        int phone() const { return phone_ ; }

};

bool operator< ( const Person& a, const Person& b ) { return a.name() < b.name() ; }

int main()
{
    std::list<Person> lst { { "Sutter", "aaa", "bbb", 111 }, { "Smith", "ccc", "ddd", 222 } } ;

    lst.push_back( Person( "Wakely", "eee", "fff", 333 ) ) ; // add wakely
    lst.emplace_back( "Nelson", "ggg", "hhh", 444 ) ; // add nelson


    lst.sort() ; // default; Person must be LessThanComparable
    for( const Person& p : lst ) std::cout << "{ " << p.name() << ", " << p.phone() << " } " ;
    std::cout << '\n' ;

    // sort with a user provided predicate (Person need not be LessThanComparable)
    // sort in descending order of names
    lst.sort( [] ( const Person& a, const Person& b ) { return a.name() > b.name() ; } ) ;
    for( const Person& p : lst ) std::cout << "{ " << p.name() << ", " << p.phone() << " } " ;
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/945fd1fba7e9fe8c

[48T7M4Gy]

If you have to design your own linked list and can't use a supplementary array or <list> and associated STL sort functionality then the following might be a start to enabling Person's to compare and then proceed to (albeit inefficiently) walk through the list and place each new entry in order as Jonnin above.

My guesstimate is you will only need a < or a <= overloaded operator.

#include <iostream>
#include <string>

class Person{
    
public:
    std::string name;
    int number; // etc etc etc
    
    Person(){};
    
    bool operator<(const Person &rhs) const
    {
        int result = name.compare(rhs.name);
        
        if(result < 0)
            return true;
        else
            return false;
    }
};

int main()
{
    Person one, two;
    
    one.name = "Betty";
    two.name = "Belle";
    
    if(one < two)
        std::cout << "One is before two\n";
    else
        std::cout << "Two is before one\n";
    
    return 0;
}

Two is before one
Program ended with exit code: 0

[48T7M4Gy]

Or, as earlier

bool Person::operator<(const Person &rhs) const
    {
        return name < rhs.name;
    }