Removing a node From Doubly Threaded LnkLst

Answer 1

Two choices:

1) Use a high level library that solves the problem. Boost MultiIndex containers allow shared nodes with multiple ordered/mapped organizations.

2) Instead of two (sorted by rating and name) singly linked lists, use two doubly linked lists. Then deletion of a given node is O(1). To find a node quickly by name, you could use an efficient map (hash table or balanced tree). If you don't mind scanning through one list to find the node, then that list doesn't need to be doubly linked.

As for deletion for linked lists, you're right to suspect that your code can be simplified immensely. Either:

1) use a sentinel (dummy) node for the empty list; that way the "previous node" always exists for actual list items

2) instead of "pointer to previous node" in singly linked list deletion, store "pointer to "next pointer to this node"".

Here's what I mean by 2):

node **pn=&headByRating; // we will update headByRating=n via (*pn)=n if needed
node *c=*pn;  // we will have c == *pn except momentarily
while ( c && strcmp(name, c->item.getName()) {
    pn=&c->nextByRating; // c is now the previous node
    c=*pn; // c is *pn again
}
// now (*pn) points to the node we want to delete, i.e. c
*pn=c->next; // (*pn) skips right over c now.
// delete c; // or else you leak memory; you didn't specify how nodes are allocated
return true;

This should be equivalent to your:

while ( NULL != currByRating && 
      ( strcmp( name, currByRating->item.getName() ) != 0 ) )
{
    prev_node = currByRating;
    currByRating = currByRating->nextByRating;
    prev_node->nextByRating  = currByRating;
}
    if ( currByRating == headByRating ) // was it the head?
    {
     currByRating = currByRating->nextByRating;
     headByRating = currByRating;
     return true;
    }
    else if ( currByRating->nextByRating == NULL ) // could it be the tail?
    {
     currByRating = prev_node;
     currByRating->nextByRating = NULL;
     return true;
    }
    else
    {
     currByRating = prev_node;
     currByRating->nextByRating = currByRating->nextByRating->nextByRating;
     return true;
    }