Search and delete in double linked list

Question

I want to search something in a double linked list and delete it.

My problem is that I lose both previous and the node of the node I want to delete.

Here is my code:

    int delnode(string moviename)
        {
            node *temp,*del;
            //check empty
            if(!head)
                {
                    cout<<"empty";
                }
            else
                {
                    temp=head;
                while (temp->next!=NULL)
                    {

                        if (temp->title==moviename)
                            {
                                del=temp;
                                temp=temp->previous;
                                temp->next=del->next;
                                delete del;
                            }
                        temp=temp->next;
                    }
                }
        }

For example if I have 5 movies, movie1,movie2,movie3,movie4,movie5 and want to delete movie3 my list will be movie1,movie4,movie5 :S

Answer 1

You're making this incredibly hard on yourself. Your code has a number of problems, including:

• failure to properly wire the previous pointers
• failure to account for a last-node deletion.
• failure to advance the head pointer if it was the prospect node.

Considering that, I think this does what you want, and I strongly advise you to examine it carefully, even stepping through it in a debugger to see how it works.

void delnode(const std::string& moviename)
{
    // pp holds the address of the pointer that will
    //  eventually point to our node being deleted.
    node **pp = &head;

    // skip nodes until we find a match
    while (*pp && (*pp)->title.compare(moviename))
        pp = &(*pp)->next;

    if (*pp)
    {
        node *tmp = *pp;
        if ((*pp = tmp->next)) // assignment-eval intentional
            (*pp)->previous = tmp->previous;
        delete tmp;
    }
}

This solves a number of issues, including

• properly updating the head pointer if it was the node matching your string.
• properly wiring next and previous to all proper pointers
• properly removing the last node in the list if that is your suspect node.
• doing absolutely nothing if the head pointer is null.

Answer 2

You're not updating the previous link on what is temp->next at the end of it all.

You need to add in temp->next->previous = temp just before the delete del line, since you're using a double linked list.

Answer 3

You have several problems.

If your list only has one item, you'll never test it because of

if ( temp->next != NULL )

If your item is at the head of the list that you want to delete, you don't update head and you're code will crash anyways because you don't test that temp->previous is valid.

And if you delete an item, you don't update the back pointer as @Leigh mentioned.

Here is my unlink an item code from my list template:

void    untie_pointer( _Tp * aptr )
{
    if ( aptr )
    {
        if ( aptr-> prior() ) { aptr-> prev_-> next_= aptr-> next_ ; }
            else { if ( first_ == aptr ) { first_= aptr-> next_ ;  if (first_) { first_-> pr
ev_= nullptr ; } } }
        aptr -> prev_= nullptr ;
        if ( aptr-> next() ) { aptr-> next_-> prev_= aptr-> prev_ ; }
            else { if ( last_ == aptr ) { last_= aptr-> prev_ ;  if ( last_ ) { last_-> next
_= nullptr ; } } }
        aptr-> next_= nullptr ;
    }
}

Its because of all these cases that the gcc stl list uses a sentinel object.

Answer 4

Here is a code I wrote to check if the node

1.is in the front and no nodes after it.

2.is in the front and have nodes after it.

3.the node is the last node

4.a node is in the nth position

void deleteRear()
{
if(n == NULL)
{
cout <<"No People Found" << endl;
}
else
{
node *temp1;
if(n == NULL)
{
cout<<"No People Found"<<endl;
}
else
{
temp1 = start_ptr;
if(temp1->prev == NULL && temp1->nxt == NULL)
{
start_ptr = NULL;
delete temp1;
n = NULL;
}
else
{
while (temp1->nxt != NULL)
{
temp1 = temp1->nxt;
end_ptr= temp1->prev;
}
end_ptr->nxt = NULL;
delete temp1;
cout<<end_ptr->name<<endl;  
}
}
}   
}
void deleteAPerson()
{
if(n == NULL)
{
cout <<"No People Found" << endl;
}
else
{
node *temp1;
temp1 = start_ptr;
while(temp1 != NULL)
{
cout << "Name : " << temp1->name << endl;

temp1 = temp1 ->nxt;
}
node *temp, *temp2, *temp3, *temp4;
temp = start_ptr;
string names; 
cout << "Please Enter Person's Name: >>";
cin >> names;
while(temp->nxt != NULL && temp->name != names)
{
temp = temp->nxt;   
}
if (temp->name == names)
{
if(temp->prev == NULL && temp->nxt == NULL)
{
cout<<"Deleting Front"<<endl;
cout<<"Only one person on the list"<<endl;
temp = start_ptr;
start_ptr = NULL;
delete temp;
n = NULL;
}
else if (temp->prev == NULL && temp->nxt != NULL)
{
cout<<"Deleting Front"<<endl;
cout<<"There are other people on the list"<<endl;
temp2 = start_ptr;
start_ptr = start_ptr->nxt;
start_ptr->prev = NULL;
delete temp2;
}
else if(temp->prev != NULL && temp->nxt == NULL)
{
cout<<"Deleting End"<<endl;
deleteRear();
}
else
{
current = temp;
current->prev->nxt = current->nxt;
current->nxt->prev = current->prev;
delete current;
}
}
else
{
cout<<"No such person exists"<<endl;
}
}
}