Thread: doubly Linked list - sorting

  1. #1
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221

    doubly Linked list - sorting

    I have a project that i have to sort a Doubly linked list by name and sort by rating..
    I have a insert function where i am adding all my data from main()

    I have 2 pointers headByName and headByrating. One thread suppose to go through them by name, the other goes through them by rating.

    My question is if i am sorting by name how do i sort by rating in the same function? Also, is my link list not a doubly linked list?
    if not can you help me in what i am doing wrong?


    Code:
    class list
    {
    public:
    	list(void);				// constructor
    	virtual ~list(void);	// destructor
    	void displayByName(ostream& out) const;
    	void displayByRating(ostream& out) const;
    	void insert(const winery& winery);
    	winery * const find(const char * const name) const;
    	bool remove(const char * const name);
    
    private:
    	struct node
    	{
    		node(const winery& winery);		// constructor
    		winery item;
    		node * nextByName;
    		node * nextByRating;
    	};
    
    	node * headByName;
    	node * headByRating;
    };
    
    #endif // _LIST_
    Code:
    int main()
    {
    	char mytry;
    
        list	*wineries = new list();
    	winery	*wPtr;
    
        cout << "\nCS260 - Lab1 - " << endl << endl;
    
    	wineries->insert(winery("Lopez Island Vinyard", "San Juan Islands", 7, 95));
    	wineries->insert(winery("Gallo", "Napa Valley", 200, 25));
    	wineries->insert(winery("Cooper Mountain", "Willamette Valley", 100, 47));
    This is where i am doing a insertion sort on name.
    The sort works fine, however, i do not think the linked list is done correctly..
    I am having a hard time implementing two heads..

    Code:
    void list::insert(const winery& winery)
    {
    
    node* wineryNode = new node(winery);
    node* prev = NULL;
    node* check = headByName;
    headByRating = check;
    
      
      while (check != NULL && (strcmp(check->item.getName(), wineryNode->item.getName() ) < 0))
    	   {
    
            prev = check;
            check = check->nextByName;
    	   }
    
         
    
        if (prev == NULL)
        {
            headByName = wineryNode;
            headByRating = wineryNode;
        }
        else
        {
          
            prev->nextByName = wineryNode;
            prev->nextByRating = wineryNode;
        }
        wineryNode->nextByName = check;  
        wineryNode->nextByRating = check;
    I also have a function for display rating..
    Code:
    void list::displayByName(ostream& out) const
    {
    
    	node *curr  = headByName;
    
     while ( curr )
     {
    	 //out << curr;
      out << curr->item.getName()
          << curr->item.getLocation()
       << curr->item.getAcres()  
        << curr->item.getRating()
       << endl;
    
      curr = curr->nextByName;
     }
    Any help is very welcome..

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    That list structure may have two links, but I wouldn't call it a doubly-linked list that you're making. It's more of a threaded list, or a doubly-intrusive list.

    Okay here's the easy way:
    1. Ignore the rating list links entirely and write everything you need for just the name list.
    2. Duplicate the body of the functions you have and in the copy, search and replace anything to do with name with the equivalent for ranking.
    3. Edit the code to only allocate and deallocate each node once and share the same allocated nodes.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Make your sort function take a bool. 1, you sort the name list, 0 you sort the rating list. The sorting is the same, you just set it up on a different pointer to start:
    Code:
    sort(bool x)
    {
        Node *n = bool ? this->headByName : this->headByRating;
        ...sort n...
        ...set the correct head...
    }

    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  3. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  4. Doubly linked list woes
    By foniks munkee in forum C Programming
    Replies: 3
    Last Post: 03-06-2002, 03:04 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM