CODEWITHSUNDEEP
c++linked-listnodesdoubly-linked-list
Brandon Bosso
Brandon Bosso

Reputation: 157

Inserting at the tail of a doubly linked list

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.

Upvotes: 1

Views: 9100

Answers (3)

Jonathan Wakely
Jonathan Wakely

Reputation: 171263

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.

Upvotes: 8

paxdiablo
paxdiablo

Reputation: 881323

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

Upvotes: 1

WhozCraig
WhozCraig

Reputation: 66194

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

Upvotes: 1

Related Questions