Doubly Linked List adding elements

Question

I've a uni assignment and unfortunately, encountered a problem.
I'm still struggling with pointers and references so it's quite hard for me to find a solution, even though I've searched for it for an entire day.

Here are essential parts of my code:

struct BuenoList
{
    int value;
    BuenoList* prev;
    BuenoList* next;
};

Declaration:

void insertNode(BuenoList*, int);

Definition:

void insertNode(BuenoList* tail, int _id)
{
    BuenoList* temp = new BuenoList;

    temp->value = _id;
    temp->prev = tail;
    tail->next = temp;
    tail = temp;
    tail->next = NULL;
}

Now, in main() I do this:

int main(int argc, char **argv)
{
    BuenoList* BuenoListing = new BuenoList;
    BuenoListing->value = 1;
    BuenoListing->prev = NULL;
    BuenoListing->next = NULL;

    BuenoList* BuenoHead = BuenoListing;
    BuenoList* BuenoTail = BuenoListing;

    insertNode(BuenoTail, 2); // Add value 2 to the list
    insertNode(BuenoTail, 3); // Add value 3 to the list

    return 0;
}

Okay, so here's the problem: When I print the list from the first element it prints like this:
1
1 2
1 3
So apparently this line

insertNode(BuenoTail, 3);

overwrites value 2.

My guess would be that BuenoTail does not change so there must be a problem with the reference.

How can I solve this? Print should be: 1 2 3

@EDIT

void deleteNode(BuenoList*& tail, int _id) // Search list for specified value and delete it
{
    BuenoList* temp = tail;

    while (temp->prev != NULL)
    {
        if (temp->value == _id) break; 
        else temp = temp->prev;
    }

    if (temp->value == _id)
    {
        temp->prev = temp->next;
        free(temp);
    }
    else std::cout << "ERROR KEY DOES NOT EXIST\n";
}

Answer 1

Considering you wanted to keep your code structure the same, I will show you two possible solutions. In a C fashion, you can use a pointer to a pointer to update your head and tail pointers. Or, in C++ you can pass your head and tail pointers by reference. Personally, in C++ I would make a LinkedList class that keeps track of your head and tail nodes though.

Passing pointer by reference (C++)

In order to pass your pointer by reference, first change your insertNode declaration,

void insertNode(BuenoList *&tail, int _id);

Next, change your insertNode definition with the same function arguments. That is it, your code should work now. This minute change works, because your tail node in the insertNode function is aliased with the tail node in your main function.

Passing pointer by pointer (C)

I know you put a C++ tag, but you can also update your head and tail nodes using a more C like method. First, in the main function, you will need to declare BuenoHead and BuenoTail as a pointer to a pointer.

int main(int argc, char **argv)
{
    BuenoList* BuenoListing = new BuenoList;
    BuenoListing->value = 1;
    BuenoListing->prev = NULL;
    BuenoListing->next = NULL;

    BuenoList** BuenoHead = new BuenoList*;
    BuenoList** BuenoTail = new BuenoList*;
    *BuenoHead = BuenoListing;
    *BuenoTail = BuenoListing;

    insertNode(BuenoTail, 2); // Add value 2 to the list
    insertNode(BuenoTail, 3); // Add value 3 to the list

    return 0;
}

Then you need to update the insertNode function declaration to take a pointer to a pointer.

void insertNode(BuenoList** tail, int _id);

Then, you need to update the function definition to deference your pointer to a pointer correctly,

void insertNode(BuenoList** tail, int _id) 
{
    BuenoList* temp = new BuenoList;

    temp->value = _id;
    temp->prev = *tail;
    temp->next = NULL;
    (*tail)->next = temp;
    *tail = temp;
}

EDIT

Deleting a node

You modified your question, asking for help on deleting a node. You have several problems with your deleteNode function.

1. You mix new with free. Whenever you allocate with new, you should correspondingly use delete.
2. You call temp->prev without checking whether temp could be NULL or not.
3. You need to change the function arguments to include your head pointer. It might turn out the node you want to delete is the head of your linked list. If so, you'll need to update the head node accordingly.
4. You need to check whether the node you are deleting is in the middle of the list, the head of the list, the tail of the list, or if is is the only node of the list. Each of these cases requires different operations to update your linked list.

Considering this is a university assignment, I don't want to give you the full blown solution. Here is a partially modified deleteNode function. I left some parts for you to fill out though. Hopefully that helps. Maybe next time focus the question a bit more, so I don't have to give a partial solution.

void deleteNode(BuenoList*& tail, BuenoList*& head, int _id) {
    BuenoList* toDelete;
    toDelete = tail;

    // Traverse list and find node to delete
    while( ( toDelete != NULL ) && ( toDelete->value != _id ) ) {
        toDelete = toDelete->prev;
    }

    // If node not found, return
    if( toDelete == NULL ) {
        std::cout << "ERROR KEY DOES NOT EXIST\n";
        return;
    }

    // Check to see if node to delete is tail
    if( toDelete == tail ) {
        if( toDelete->prev != NULL ) {
            tail = toDelete->prev;
            tail->next = NULL;              
        } else { //Deleting only node in list
            tail = NULL;
            head = NULL;
        }
        delete toDelete;
        return;
    }

    // Check to see if node to delete is head
    if( toDelete == head ) {
        // FILL OUT WHAT TO DO HERE
        return;
    }

    // Node to delete is neither head nor tail.
    // FILL OUT WHAT TO DO HERE
    return;
}

Answer 2

You may want to consider using a node structure and a list structure:

struct BuenoNode
{
    int value;
    BuenoNode* prev;
    BuenoNode* next;
};

struct BuenoList
{
    BuenoNode* head;
    BuenoNode* tail;
    size_t count; // having a count would be optional
}

The list functions would take a pointer to the list structure, such as InsertNode(BuenoList * blptr, int data); The list structure would be initialized so that both head and tail pointers == NULL, and you'll need to check for adding a node to an empty list or removing the only node in a list to end up with an empty list.

Answer 3

You are updating tail within insertNode(), but the updated value is not communicated back to the caller in any way. So BuenoTail does not change, as you suspected.

One easy way to fix that is to change your function to:

BuenoList *insertNode(BuenoList* tail, int _id)

and return the new tail from that function. Also change the calls to

BuenoTail = insertNode(BuenoTail, 2); // Add value 2 to the list