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

You have a while loop that seems to be searching for the before node... why are you doing that? You already have a pointer to the before node and because this is a doubly linked list the before node knows the previous and next node. That is all the information you need. There should be no loops in the code. Because this seems like a homework problem I'm not going to post code directly. — Dean Johnson
– Dean Johnson, Commented Feb 22, 2021 at 22:30
Sorry if I used while, but I was relying on a simple linked list. With the double list there is no need to traverse the nodes — Fandi
– Fandi, Commented Feb 23, 2021 at 1:52

Amit G. · Accepted Answer · 2021-02-22 23:55:44Z

2

You have to realize how to approach the solution, methodically (n is the object you want to insert the new_item object before it):

if (head != nullptr) // i.e. if list is not empty
{

}

if (new_item.P == nullptr) // i.e. if new_item is first
     head = new_item;

edited Feb 22, 2021 at 23:55

answered Feb 22, 2021 at 23:06

Amit G.

2,7142 gold badges23 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Fandi Over a year ago

Ok. So isn't it necessary to have the last item?

Amit G. Over a year ago

@Fandi , "necessary" it is not. It is optional to have it Like if you want to add items after the last item, or to reverse-iterate from last to first more efficiently i.e without reaching the last object via the first one. But in any case this issue is not related to your question at the title.

Remy Lebeau · Accepted Answer · 2021-02-22 23:42:11Z

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

edited Feb 22, 2021 at 23:42

answered Feb 22, 2021 at 23:17

Remy Lebeau

609k36 gold badges516 silver badges875 bronze badges

2 Comments

Fandi Over a year ago

I have tried it. I have another method to add later, the problem was when it showed the nodes, because I have another bool method to show from back to front and vice versa. I have changed it as if it shows a normal list and it has worked

Fandi Over a year ago

For the problem with the head: The solution is in the if ( before == head ) newNode->next = head head = newNode;

Collectives™ on Stack Overflow

How add node before doubly linked list c++

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related