Inserting at the tail of a doubly linked list

1
votes

I'm working with linked lists for my first time and have to create a function that can insert a node at the end of a doubly linked list. So far I have

void LinkedList::insertAtTail(const value_type& entry) {
    Node *newNode = new Node(entry, NULL, tail);
    tail->next = newNode;
    tail = newNode;
    ++node_count;
}

The Node class accepts a value to be stored, a value for the next pointer to point to, and a value for the previous pointer in that order. Whenever I try to insert a node here, I get an error saying there was an unhandled exception and there was an access violation in writing to location 0x00000008.

I'm not entirely sure what's going wrong here but I assume it has something to do with dereferencing a null pointer based on the error message. I would really appreciate some help with solving this problem.

EDIT:

I should have clarified early, tail is a pointer that points to the last node in the list. Tail->next accesses the next variable of that last node which, before the function runs, points to NULL but after it executes should point to the new node created.

3
c++linked-listnodesdoubly-linked-list
Show us: the LinkedList and Node classes, as there's not much context in your first post. - Thomas Matthews
Is there something wrong with tail and tail->next pointing to the newNode? (Looks like a circular reference, but I could be wrong.) - Thomas Matthews
Is your tail initially NULL? You can't dereference it in tail->next until it already points to the first element - Jonathan Wakely
The order of operations you have seem correct. The parameters your passing indicate proper node initialization. Just by this I would hazard a guess your tail pointer is broken or the copy-constructor of value_type is stomping on memory. Showz us more code plz. and think about if (tail) in front of that tail->next assignment. Likewise, where's the head-assignment on the chance this list is purely empty and the tail insert is the first one?? might want that as well. - WhozCraig
@Thomas, when tail->next is set to point to the newNode, tail references the former tail. - imreal

3 Answers

8
votes

Where does tail point to initially? If it's NULL then you'll dereference a null pointer when trying to insert the first element.

Does it help if you test tail before dereferencing it?

void LinkedList::insertAtTail(const value_type& entry) {
    Node *newNode = new Node(entry, NULL, tail);
    if (tail)
        tail->next = newNode;
    tail = newNode;
    ++node_count;
}

If tail is null and offsetof(Node, next) is 8 that would explain the access violation, because tail->next would be at the address 0x00000000 + 8 which is 0x00000008, so assigning to tail->next would try to write to memory at that address, which is exactly the error you're seeing.

1
votes

Assuming your LinkedList has both a head AND tail, maybe try:

void LinkedList::insertAtTail(const value_type& entry) 
{
    Node *newNode = new Node(entry, NULL, tail);
    if (tail)
        tail->next = newNode;
    tail = newNode;
    if (!head)
        head = newNode;
    ++node_count;
}

Just a shot in the dark

1
votes

It's difficult to tell what's causing the error without knowing the state of the list before the insertion operation (which is actually append rather than insert, by the way).

There's a good chance you're not handling the initial case of appending to an empty list. The basic algorithm is (an empty list is indicated by a NULL head pointer, everything else is indeterminate):

def append (entry):
    # Common stuff no matter the current list state.

    node = new Node()
    node->payload = entry
    node->next = NULL

    # Make first entry in empty list.

    if head = NULL:
        node->prev = NULL
        head = node
        tail = node
        return

    # Otherwise, we are appending to existing list.

    next->prev = tail
    tail->next = node
    tail = node