Doubly threaded link list

This is a discussion on Doubly threaded link list within the C++ Programming forums, part of the General Programming Boards category; I am trying to remove an item in my link list. It does have 2 threads going threw it. headByName ...

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

    Doubly threaded link list

    I am trying to remove an item in my link list. It does have 2 threads going threw it.
    headByName and headByRating.

    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_
    What i am trying to do is remove "cooper" from the list. how can i add headByRating below so it contains all the items as headByName.

    Code:
    bool list::remove (const char * const name)
    {
    
       
    	node * prev = NULL;
    	node * p = NULL;
    	node * curr = headByName;
    
    	
    	while(curr)
    	
    	{
    
    		if(strcmp(curr->item.getName(), name) == 0)
    		{
    		prev = headByName;
    		p = prev->nextByName;
    		headByName = p;
    		//delete prev;
    		return true;
    		}
    	curr = curr->nextByName;
    }
    return false;
    Code:
    cout << "\n>>> removing Cooper Mountain\n";
    wineries->remove("Cooper Mountain");
    I think thats all the code you would need. I just dont know how to attach the headByRating in the list with headByname in the remove function?

    Thank you

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Remember I said that you need to duplicate the function body for the second threaded list? You need two of those while loops. One finds and unlinks the item from the nextByName list and the other finds and unlinks the item from the nextByRating list. Then you make one of those loops remember the pointer to the item that as unlinked and after both loops you delete that item.
    Don't try and return from inside the loop.
    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
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    Thanks. Thats what i had previously but was told it was wrong. I ill try that and get back to you.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    This is what i have, and it appears to work. I do not know if i have a memory leak because of it though?


    Code:
    bool list::remove (const char * const name)
    {
    
    	node * prev = NULL;
    	node * prevRating = NULL;
    	node * p = NULL;
    	node * d = NULL;
    	node * curr = headByName;
    	node * currRating = headByRating;
    
    	while(curr)
    
    	{
    		if(strcmp(curr->item.getName(), name) == 0)
    		{
    			prev = headByName;
    			p = prev->nextByName;
    			headByName = p;
    			//delete curr;
    			//return true;
    		}
    		curr = curr->nextByName;
    	}
    	//return false;
    
    
    	while(currRating)
    	{
    		if(strcmp(currRating->item.getName(), name) == 0)
    		{
    
    			prevRating = headByRating->nextByRating->nextByRating->nextByRating;
    			d = prevRating->nextByRating;
    			prevRating->nextByRating = d->nextByRating;
    
    		}
    		currRating = currRating->nextByRating;
    	}
    
    	prev = NULL;
    	delete prev;
    	d = NULL;
    	delete d;
    	return true;
    
    }

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    You're getting close. A few things:
    • There should only be one delete statement, don't try and delete prev.
    • You do have a memory leak, but only because you're setting a variable to NULL before calling delete.
    • When you do the unlinking in each while loop, once you find and unlink the item, break out of the loop rather than iterating over the remaining items (which you know you wont need to do anything with).
    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"

  6. #6
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    Thank you. I will take everything you said into consideration. I will break out of the loop and i already fixed the code..

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Circularly-Doubly Linked List implementation
    By BlackOps in forum C Programming
    Replies: 4
    Last Post: 07-19-2009, 04:45 AM
  2. instantiated from here: errors...
    By advocation in forum C++ Programming
    Replies: 5
    Last Post: 03-27-2005, 08:01 AM
  3. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 05:37 PM
  4. Replies: 3
    Last Post: 03-04-2005, 01:46 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21