C++ – Removing a node From Doubly Threaded LnkLst

c++

Im trying to remove a single node from a doubly threaded linked list.

What I have works..Its just terribly inefficient.

I was wondering if I can get some expert advice or some while termination condition tips.

Here is the function in which I remove 1 node from a set of Rating Nodes, stored in headByRating and a set of Name nodes, stored in headByName. All of which are sorted….

bool list::remove (const char * const name)
{
    node *currByName     = headByName;
    node *currByRating   = headByRating;
    node *prev_node      = NULL;

    while ( NULL != currByName &&
          ( strcmp( name, currByName->item.getName() ) != 0 ) )
        {
            prev_node  = currByName;
            currByName = currByName->nextByName;
            prev_node->nextByName = currByName; 
        }

        if ( currByName == headByName )
        {   
            currByName   = currByName->nextByName;
            headByName   = currByName;
        }
            else if ( currByName->nextByName == NULL )
            {//then we must be at the end
                currByName = prev_node;
                currByName->nextByName = NULL;
                //return true;
            }
            else
            {
                currByName = prev_node;
                currByName->nextByName = currByName->nextByName->nextByName;
                //return true;
            }

    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;
        }


    return false;
}

Yeah i just need help simplifing the code, making it more efficient. I hoping to combine and use only one while loop if thats possible.

Best Solution

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;
    }

Related Solutions

C++ – call a constructor from another constructor (do constructor chaining) in C++

C++11: Yes!

C++11 and onwards has this same feature (called delegating constructors).

The syntax is slightly different from C#:

class Foo {
public: 
  Foo(char x, int y) {}
  Foo(int y) : Foo('a', y) {}
};

C++03: No

Unfortunately, there's no way to do this in C++03, but there are two ways of simulating this:

You can combine two (or more) constructors via default parameters:

class Foo {
public:
  Foo(char x, int y=0);  // combines two constructors (char) and (char, int)
  // ...
};

Use an init method to share common code:

class Foo {
public:
  Foo(char x);
  Foo(char x, int y);
  // ...
private:
  void init(char x, int y);
};

Foo::Foo(char x)
{
  init(x, int(x) + 7);
  // ...
}

Foo::Foo(char x, int y)
{
  init(x, y);
  // ...
}

void Foo::init(char x, int y)
{
  // ...
}

See the C++FAQ entry for reference.

C++ – LinkedList Part

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.

Best Solution

Related Solutions

C++ – call a constructor from another constructor (do constructor chaining) in C++

C++ – LinkedList Part

Related Question