Search code examples
c++linked-listswapsingly-linked-list

Insert before in linked list?


I am trying to analyze this code that inserts in a linked list given before, but i believe that there is something redundant in the code:

             //  new_n->next = p->next;
               // p->next = new_n;

I believe there is no need to assign p->next = new_n; since it we already moved new_n to the thing p->next is pointing at? /

  template <typename Object>
    bool insertBeforeS(SNode<Object>* node, Object before, Object newValue) {
        SNode<Object> *new_n = new SNode<Object>(newValue);
        for (SNode<Object> * p = node; p != nullptr && p->next != nullptr; p = p->next) {
            if (p->data == before) {
                new_n->data = p->data;
                p->data = newValue;
                new_n->next = p->next;
                p->next = new_n;
                return true;
            }
        }

        return false;
    }

Solution

  • After the value before is found in the list then the new node exchanges its value with the value of the "before" node.

    Then this "before" node shall point to the new node and the new node shall point to the node that early was pointed to by the "before" node.

    So these statements

    new_n->next = p->next;
    p->next = new_n;
    

    do the required task by setting the data members next of the nodes.

    Initially

    | before-value| pointer to the next node|
    

    The new node

    | new-value | nullptr |
    

    Then the values are exchanged

    | new-value| pointer to the next node|
    | before-value | nullptr |
    

    And then after this statement

    new_n->next = p->next;
    

    we have

    | new-value| pointer to the next node|
    | before-value | pointer to the next node |
    

    and then after this statement

    p->next = new_n;
    

    we have

    | new-value| pointer to the new node |
    | before-value | pointer to the next node |
    

    Pay attention to that the function has a memory leak in the case when a node with the value before is not found.