Insert a node at a specific position in a Linked List

Question

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;
}

Answer 1

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.

• πάντα ῥεῖ: 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.
• πάντα ῥεῖ: Minor nitpick: Also the for loops body {} could be simplified just using a ;.
• πάντα ῥεῖ: I hope you don't mind I've adopted your for() loop idea, though in a slightly different way.
• πάντα ῥεῖ: Oops there's a major error: current can't be accessed outside the for() loops body! coliru.stacked-crooked.com/a/9a4572250c4174ac
• Loki Astari: @πάνταῥεῖ: 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.

Answer 2

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.

• Loki Astari: 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.
• πάντα ῥεῖ: @LokiAstari My (second) code proposal covers the empty list case.
• Loki Astari: Your code does. But your simplification of the OP original code does not.
• πάντα ῥεῖ: @LokiAstari Well, may be that oversimplified the original code.
• Loki Astari: 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).