LinkedList Part

Question

I think I might have done something right, headByRating and headByName both refer to the same address.

I have been drawing diagras working all day trying new things etc, and i havent really made any progress.

I have two list pointers, headByRating and headByName. and two node pointers nextByName and nextByRating.

Somehow I need to be able to sort this stuff by its name and rating. I've been thinking that I do that by each of the ptrs' address'.

2 statements as an example that I have been trying to sort:

//main.cpp

list *wineries = new list();
wineries->insert(winery("Lopez Island Vinyard", "San Juan Islands", 7, 95));
wineries->insert(winery("Gallo", "Napa Valley", 200, 25));

the winery ctor is fine everything is allocated and into the object at this point:

//list.cpp
void list::insert( const winery& winery )
{
         list *listPtr  = new list(); // havent really used the list obj. yet.

    node *current = new node( winery ); // winery is now a node.
    node *temp    = current;     // temp knows about the nodes address.

    while ( temp->nextByName != NULL )
    {
                 // check for null and reassign 
        temp = temp->nextByName;
    }
    node *new_node = new node( winery ); // creating a new node.
    new_node->item = winery; 
    new_node->nextByName   = new_node;
    new_node->nextByRating = new_node;
}

// list.h
struct node
{
    winery  item;
    node *  nextByName;
    node *  nextByRating;
};

class list
{
    ...
private:
    node * headByName;
    node * headByRating;
};

What is a good approach to this? I dont think im doing this right.

Answer 1

If you are need to use list with several indexes you should consider using boost::multi_index instead of inventing the wheel.

Answer 2

If you want to make your List type for experimentation, do it, otherwise use std::list.
If you want to keep your list sorted while you insert new elements then you have to implement an ordered list.

It's better to remove "winery field" dependencies from your List. A node should have only one next node, not many. You are making a List, not a Tree.

// list.h
struct node
{
    winery  item;
    node *  next;
};

class list
{
    ...
private:
    node * head;
};

You can't have one List ordered by different winery fields.
Make a new type, like CWinery, which will act as a container for your winery records.
In there, you can have a list to store your elements and methods to sort it or whatever you need.

Answer 3

It looks like you have several problems here:

1. It will always skip the while statement since temp->nextByName will always be NULL since temp points to current which is a new object.
2. You're creating a node object from winery twice
3. You're assigning the item member to winery after you sent it in the constructor
4. You're making the nextByName and nextByRating members point to itself

I'd recommend removing everything from this method and writing high-level pseudo code in its place. Then create a smaller method for each line of pseudo code. Smaller logical methods called inside insert will help it make sense.

Answer 4

Why are you rolling your own linked list? Why not use std::list? If it's for the double-sorting thing, two separate lists of pointers would work, and be a hell of a lot easier if you can then use the provided container classes.

Or alternatively, if you need to sort it, is a linked list the best option? std::vector is often easier for sorting, or std::set maintains the order itself.