3
\$\begingroup\$

This code is built to insert a Node into a specific position of a linked-list. It passes all the test cases for the interview, but I was wondering about the coding style regarding techniques, and especially variable naming, and any other best-practices you can help with.

Node* InsertNth(Node *head, int data, int position)
{
    // Complete this method only
    // Do not write main function. 
    Node * sentinel = new Node();
    sentinel->data = -1;
    sentinel->next = head;
    Node* node = sentinel;
    int i = 0;
    while (node->next && i < position) {
        node = node->next;
        i++;
    }

    Node* preNext = node->next;
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = preNext;
    node->next = newNode;
    head = sentinel->next;
    delete sentinel;

    return head;

}
\$\endgroup\$
0

2 Answers 2

1
\$\begingroup\$

This is how I would have done it:

Node* InsertNth(Node *head, int data, int position)
{
    // Use a sentinel as this leads to simpler code
    // and no need to test for the empty list case.
    Node sentinel{-1, head};

    // Find the position we want to insert in.
    // Note: If there are less than `position` elements then
    //       the new element will be added to the end.
    Node* current = &sentinel;
    for(; position != 0 && current->next;--position, current = current->next)
    {}

    // Create the new Node and insert it into the chain.
    Node* newNode = new Node{data, current->next};
    current->next = newNode;

    // Update head.
    // In the case of null list or inserting at position 0
    // this will do something. Otherwise this is a no-op.
    head = sentinel.next;

    return newNode;
}

Notes:

  1. Make notes of assumptions you have made in the comments.
  2. I like the for() expression over the while() expression.
    It expresses my intent more clearly (ie that I am just chaining along the list).
  3. No need to dynamically create the sentinel. By declaring it on the stack. It works better.
  4. I have assumed node has a reasonable constructor to make the code cleaner.
\$\endgroup\$
11
  • \$\begingroup\$ You made assumptions about the available constructors of Node. A brace initializer might be more appropriate. Also there aren't any checks for the position parameter. I know my rewrite of the original version wasn't good. I'll try to reformulate my answer. \$\endgroup\$ Jan 20, 2017 at 18:31
  • \$\begingroup\$ Minor nitpick: Also the for loops body {} could be simplified just using a ;. \$\endgroup\$ Jan 20, 2017 at 18:43
  • \$\begingroup\$ I hope you don't mind I've adopted your for() loop idea, though in a slightly different way. \$\endgroup\$ Jan 20, 2017 at 18:55
  • \$\begingroup\$ Oops there's a major error: current can't be accessed outside the for() loops body! coliru.stacked-crooked.com/a/9a4572250c4174ac \$\endgroup\$ Jan 20, 2017 at 19:03
  • 1
    \$\begingroup\$ @πάνταῥεῖ: Never use ; to terminate a for loop. That makes code really hard to read because you can not tell if the ; is an accident or by design. So ALWAYS use the {} even if it is empty as the intention can not be confused. \$\endgroup\$ Jan 21, 2017 at 18:52
0
\$\begingroup\$

It looks like you way overcomplicated that task. What you currently have can be rewritten in a few lines and with less variables.

Also your code will simply append a new node at the end of the linked list, if position is beyond the lists range.
So you probably should add some error checking for valid input parameters.

The use of sentinel as a newed and deleted node will cover creation of a new list, but seems unnecessary overhead for me.

Node* InsertNth(Node *head, int data, int position)
{
    if(position < 0) {
        throw std::invalid_argument("Parameter 'position' must be greater or equal to 0.");
    }

    Node * node = head;
    int i = 0;
    for(;node && node->next && i < position; node = node->next, ++i) {}

    if(i != position) { // position is a value beyond the list positions
        throw std::out_of_range("Parameter 'position' is out of range of the linked list.");
    }

    Node* newNode = new Node();
    newNode->data = data;
    if(node) {
         newNode->next = node->next;
    }
    else { // Create a new head, list was empty, position was 0
         newNode->next = nullptr;
         return newNode;
    }

    node->next = newNode;
    return head;
}

but I was wondering about the coding style regarding techniques

Returning the head looks a little bit odd. One would rather expect such function returns a pointer to the newly created node.

This would simplify the code from above even further:

Node* InsertNth(Node *head, int data, int position)
{
    if(position < 0) {
        throw std::invalid_argument("Parameter 'position' must be greater or equal to 0.");
    }

    Node * node = head;
    int i = 0;
    for(;node && node->next && i < position; node = node->next, ++i) {}

    if(i != position) { // position is a value beyond the list positions
        throw std::out_of_range("Parameter 'position' is out of range of the linked list.");
    }

    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = node ? node->next : nullptr;
    if(node) {
        node->next = newNode;
    }
    return newNode;
}

and especially variable naming

The name sentinel sounds misleading for me (besides you don't need that at all). A sentinel is some variable to survey a specific value like a threshold or such.
Naming that tempNode or suchlike would sound clearer for me.

Since node is used as an iterator on the singly linked list, I would rather name it currentNode.


Probably beyond what was asked in that interview, but the linked list should be a class that manages the Node structure, and InsertNth() should be a member function of the LinkedList class.
Also int data; could be a templated type.

Here's a sketch how it should look like:

#include <memory>
#include <iostream>

template<typename T>
class LinkedList {
private:
    template<typename U> struct Node;
    template<typename U = T>
    struct Node {
        U data;
        std::unique_ptr<Node<U>> next;
    };
    std::unique_ptr<Node<T>> head;
public:
    Node<T> const* insert(int position, T data) {
        if(position < 0) {
            throw std::invalid_argument("Parameter 'position' must be greater or equal to 0.");
        }

        auto node = head.get();
        int i = 0;
        for(;node && node->next && i < position; node = node->next.get(), ++i) {}

        if(i != position) { // position is a value beyond the list positions
            throw std::out_of_range("Parameter 'position' is out of range of the linked list.");
        }

        auto newNode = std::make_unique<Node<T>>();
        newNode->data = data;
        // newNode->next = node ? node->next : nullptr;
        if(node) {
            newNode->next = std::move(node->next);
            node->next = std::move(newNode);
            return node->next.get();
        }
        else {
            head = std::move(newNode);
            return head.get();
        }       
    }
   // Other linked list operations ...
};

int main() {
    LinkedList<int> ll;
    auto newNode = ll.insert(0,5);
    std::cout << newNode->data << std::endl;
}

See a compiling version here please.

This will have the advantage that all dynamic memory management is done under the hood, and you don't have to care about memory leaks.

\$\endgroup\$
7
  • \$\begingroup\$ The reason for creating the sentinel in the OP code is to simplify the code especially in the case where the list is empty. Your revised version (of the OPS code) fails to take this into account. Now the code does overcomplicate the creation and use of the sentinel. \$\endgroup\$ Jan 20, 2017 at 18:12
  • \$\begingroup\$ @LokiAstari My (second) code proposal covers the empty list case. \$\endgroup\$ Jan 20, 2017 at 18:14
  • \$\begingroup\$ Your code does. But your simplification of the OP original code does not. \$\endgroup\$ Jan 20, 2017 at 18:15
  • \$\begingroup\$ @LokiAstari Well, may be that oversimplified the original code. \$\endgroup\$ Jan 20, 2017 at 18:16
  • \$\begingroup\$ But the original code already handles the null head case (that is what the sentinel is for). Also it is well named; this is a common technique used to make the handling of empty list no different from the handling of the normal case (there are no need for special null checks when using a sentinel). \$\endgroup\$ Jan 20, 2017 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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