Prepend Double linked list

Hi - more linked lists issues

I am working on a simple prepend function for a doubly linked list - but I have hit a snag. Many of the examples I have seen use a similar algorithm to what I am using here, but I don't understand how to get around the problem when pointing the old head of the list to the new node. I am getting a memory violation issue on that line...

Code:

#include <iostream>

using namespace std;

typedef struct Node
{
	int *data;
	Node *next;
	Node *prev;
} NODE;

// Function prototypes
void output_fwd(void);
void insert_beg(int *data);

// The list
NODE *head;
NODE *tail;

int main(void)
{
	int num;
	
	cout << "Enter a number: ";
	cin >> num;

	while (num != 999)
	{
		insert_beg(&num);
		cout << "Enter a number: ";
		cin >> num;
	}
	
	output_fwd();

	return 0;
}

void output_fwd(void)
{
	NODE *current;

	current = head;

	while (current != NULL)
	{
		cout << "Number: " << *current->data << endl;
		current = current->next;
	}
}

void insert_beg(int *data)
{
	NODE *temp = new NODE;
	temp->data = new int;

	*temp->data = *data;

	temp->next = head;
	temp->prev = NULL;
        // This is the problem line..
	head->prev = temp;
	head = temp;
}

Always check for an empty list:

Code:

if (head)
    head->prev = temp;

You were dereferencing a null pointer by saying head->prev on the first prepend. At that point head was null, so you got slapped in the face.

Oh hell..

Thanks a lot for your help Brighteyes! I feel a bit stupid when it comes to pointers for some reason.

>Oh hell..
Would you like my double linked list library? That would save you a lot of work.

[edit]It's in C though, for C++ the std::list would be way better.[/edit]

Originally posted by Brighteyes
>Oh hell..
Would you like my double linked list library? That would save you a lot of work.

[edit]It's in C though, for C++ the std::list would be way better.[/edit]

Does your linked list has a pointer to the last node? I always think about the overhead of having a pointer to the first and last nodes... and I think about the advantages like faster insertion at the end of the list, and other usefull things
Just curious...

Would you like my double linked list library? That would save you a lot of work.

Thanks, but thats OK. I know I am only covering ground that has been covered a bazillion times before. But I am trying to ram this into my head. I need to know it, I need to understand it!

>Does your linked list has a pointer to the last node?
Not built in, no. I decided against it for simplicity sake, though you can easily place an iterator to point at the end of the list if you need quick insertions there:

Code:

#include <stdio.h>
#include <stdlib.h>
#include "List.h"

/* Error handling omitted in this example */
Iterator newItem(int data)
{
    Iterator item = malloc(sizeof (*item));
    item->data = malloc(sizeof (int));

    *(int*)item->data = data;
    item->prev = item->next = 0;

    return item;
}

int main(void)
{
    List head = 0;
    Iterator tail;
    int i;

    for (i = 0; i < 10; i++)
        head = ListAddBack(ListLast(head), newItem(i));

    tail = ListLast(head);
    head = ListFirst(head);

    printf("First: %d\n", *(int*)ListContent(head));
    printf("Last: %d\n", *(int*)ListContent(tail));

    return 0;
}

It's a bit ugly with casting because of the void pointers. Try writing a generic library in C and you'll remember how much you love templates.