Linked List. Segmentation Fault!

[bcb5082]

    void list::remove_last()
    {
        list_node* cursor = head_node;
        list_node* tmp = new list_node;

        while(cursor->next_node != NULL)
        {
            cursor = cursor->next_node;
        }
        tmp = cursor->previous_node;
        delete cursor;
        cursor = tmp;
        cursor->next_node = NULL;
    }

i am writing a linked list and trying to make it a double linked list. i cant seem to get my remove_last function to work right. can you tell me what is wrong with it and how i should go about fixing it.

thanks in advance.

[kbw]

Why are you creating a new node in a remove method?

[Jyncus]

He's creating a new node to iterate through his list.
If your list was "singly-linked", then this would be necessary, however, the nice thing about doubly-linked lists is that you can perform all the add/remove/get operations in constant O(1) time.

The algorithm:

void LinkedList::RemoveLast()
{
    if (head == NULL)    // The list is already empty
    {
        return;
    }
    else if (head->Next == NULL)    // The list has only one element
    {
        head = NULL;
        tail = NULL;   
    }
    else    // The list has at least two nodes in it
    {
        tail = tail->Prev;
        tail->Next = NULL;
    }
} 

So, because your doubly-linked list has access to a ->Prev pointer, there's no need to iterate all the way through your list with that while loop.
Hope that helps.

[kevinchkin]

He's creating a new node to iterate through his list.

What I am missing here? Why do we have to create a new node to iterate through a list O.O?
Can't we just use a pointer of the struct type and assign head pointer of that list to the pointer just created and then traverse through the list?

I don't know why do we have to create a new node for that.

@Jyncus: Please elaborate

[Jyncus]

Ahh..I didn't see that his "tmp" node was indeed a new instance of a node. When I said "..creating a new node to iterate through his list", I was referring to his "cursor" pointer that he uses in the while loop.

My mistake. >_<
Having said that, being that your list is double linked, traversing through it is not necessary in the first place. tail = tail->Prev accommodates nicely. =]

[writetonsharma]

i have a finding here..
allocating memory to some node and then putting that node pointing to some other address without keeping a count of that will result in memory leak.

tmp = cursor->previous_node; //memory leak here, it lost the real tmp which was allocated.