How add node before doubly linked list c++

Question

I am making a code for double linked list in C++. But, i have a problem, I dont know how add node before other node. I have these.

template<class T>
void LinkedListD<T>::addNodeBeforeTo(Node<T> *before, T info) {
    Node<T>* newNode = new Node<T>( info );
    if ( isEmpty() ){
        head = newNode;
        last = newNode;
    } else{
        if ( before == head ){
            newNode->next = head;
            head = newNode;

        } if ( before == last ){
            newNode->previous = last;
            last = newNode;
        }
        else{
            Node<T>* act = head;
            Node<T>* past = last;
            while ( act->next != before && past->previous != before){
                act = act->next;
                past = past->previous;
            }
            newNode->previous = past->previous;
            newNode->next = act->next;
            act->next = newNode;
            past->previous = newNode;
        }
    }
}

The example is 10, 15, 20, 12 Add node before to 20: 30 Finish Output 10, 15, 30, 20, 12 Thks

Answer 1

You don't need the while loop at all. Each node knows the nodes on both sides of it, that is all you need to update the list properly. Given the input node before, all you have to do is:

• set newNode->previous to point at the before->previous node
• set newNode->next to point at the before node
• if before->previous is not null, set before->previous->next to point at the newNode node
• set before->previous to point at the newNode node
• if before is pointing at the head node, set head to point at the newNode node.

Done.

Also, you have some other logic errors in this code. When inserting before the head node, you are not updating head->previous to point at the newNode node before updating head itself. And since your function inserts before a given node, you should not be trying to insert after the last node at all, that job should be handled by a separate addNodeAfterTo() method instead.

Try something more like this:

template<class T>
Node<T>* LinkedListD<T>::addNodeBeforeTo(Node<T> *before, const T &info) {
    if ( !before ) return nullptr;
    Node<T>* newNode = new Node<T>( info );
    newNode->previous = before->previous;
    newNode->next = before;
    if ( before->previous )
        before->previous->next = newNode;
    before->previous = newNode;
    if ( before == head )
        head = newNode;
    return newNode;
}

Demo