2
\$\begingroup\$

Is there a better way to insert after a node in a linked list? Currently I go through the node from the head of the list and find the node that has the value pos. If the node is not null at the end of the search then we found the position, so we do the insert.

void insert_after(List& list, int pos, int value)
{
    Node* newNode = new Node{value}, p;

    for (p = list.head; p && p->data != pos; p = p->next) {;}

    if (p)
    {
        newNode->next = p->next;
        p->next = newNode;
    }
}

I just don't know if this is the best way. Could it be improved at all?

\$\endgroup\$
4
\$\begingroup\$

Your solution is missing critical feedback, or alternatively, instead of feedback, fallback.

If the node is added successfully then the method should report back that success. Alternatively, it should fail, and report that fail. A simple bool return value should suffice.

If you choose to use a fallback, instead of feedback, then you should consider how the system should behave if the 'insert after' item is not found... insert at the beginning of the list? Append at the end? Whatever fallback you choose, you should implement and document it correctly.

Leaving the system as it is, though, is not a good option.

For loop blocks where there is no code in the block (a for loop with all the logic in the loop clauses), I recommend instead that you use a while loop....

Node* p = list.head;
while (p && p->data != pos) {
    p = p->next;
}
if (p) {
    ....
    return true;
}
return false;

As for whether there's a better way/algorithm, well, for a LinkedList, like you have, then no. The scan to locate the insert-point is needed.

Finally, you should only create the new Node{value} if you actually locate the insert point. There is no need to create the new node unless you are actually going to insert it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.