8
\$\begingroup\$

Given

You’re given the pointer to the head node of a linked list, an integer to add to the list and the position at which the integer must be inserted. Create a new node with the given integer, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is empty.

Solution

Node InsertNth(Node head, int data, int position) {
    Node newNode = new Node();
    newNode.data = data;
    newNode.next = null;

    if (head == null) {
        return newNode;
    }
    if (position == 0) {
        newNode.next = head;
        head = newNode;
        return head;
    }
    Node prev = null;
    Node current = head;
    int i = 0;
    while (current !=null && i < position) {
        prev = current;
        current = current.next;
        i++;
    }
    newNode.next = prev.next;
    prev.next = newNode;
    return head;
}

The code works fine. But I strongly feel that there is a chance of improvement. I see a lot of checks here, how can I reduce those and make my code more readable and covering all the edge cases?

Also, is there any recursive version possible for the given code because list is a recursive data structure hence, there should be some recursive way, right?

\$\endgroup\$
  • \$\begingroup\$ Recursion will get you a stack overflow on large lists. \$\endgroup\$ – coderodde Sep 17 '15 at 18:32
7
\$\begingroup\$

I see a lot of checks here, how can I reduce those and make my code more readable and covering all the edge cases?

Using a dummy node that points to the head can help reduce many of the checks:

Node insertNth(Node head, int data, int position) {
    Node dummy = new Node();
    dummy.next = head;

    Node runner = dummy;
    for (int i = 0; i < position; ++i) {
        runner = runner.next;
    }

    Node node = new Node();
    node.data = data;
    node.next = runner.next;
    runner.next = node;

    return dummy.next;
}

Also, is there any recursive version possible for the given code because list is a recursive data structure hence, there should be some recursive way, right?

Naturally, a recursive solution is also possible:

Node insertNthRecursive(Node head, int data, int position) {
    if (position == 0) {
        Node node = new Node();
        node.data = data;
        node.next = head;
        return node;
    }
    head.next = insertNthRecursive(head.next, data, position - 1);
    return head;
}

Update

As @PeterCordes pointed out, the above implementation is a bit dirty, as it rewrites the links unnecessarily. Here's a variant replacing the head.next = ... line above to make it cleaner.

    Node next = insertNthRecursive(head.next, data, position - 1);
    if (position == 1) {
        head.next = next;
    }

Input validation

I intentionally omitted input validation from these example implementations: they won't work with position values outside the range \$[0, n]\$. I leave that fun up to you.

\$\endgroup\$
  • \$\begingroup\$ Awesome is the word I can up with right now. I think added memory overhead is negligible as compared to the code elegance. Just the issue is how to think like this :). Also, I am coming to the conclusion that multiple exit conditions are not good, right? \$\endgroup\$ – CodeYogi Sep 17 '15 at 19:58
  • \$\begingroup\$ The recursive version rewrites the head.next pointer of every element along the way, dirtying those cache lines. It's a bad idea to rewrite data when you can easily avoid it, esp. data that wasn't recently written. \$\endgroup\$ – Peter Cordes Sep 17 '15 at 20:21
  • 2
    \$\begingroup\$ Multiple exit points can be very bad when scattered across within the function body in deeply nested control structures. In your example, they can be viewed as guard statements with early returns, which is completely acceptable. You could rearrange your code with conditions to have only one exit, but I don't think it will be better that way. How to think of dummy nodes? Try to not forget the idea! It's often helpful in linked list and tree problems. Try to find another linked list puzzle for practice and try if a dummy node will help. \$\endgroup\$ – janos Sep 17 '15 at 20:22
  • \$\begingroup\$ Good point @PeterCordes, updated my post \$\endgroup\$ – janos Sep 17 '15 at 20:36
  • \$\begingroup\$ If you want to reuse the dummy node (which you're calling a sentinel), instead of allocating a new one, I think it's possible. See my answer (the last version, InsertNth_dummy); I didn't try running my the code, but I think I have the logic right. With the right sequence of 4 assignments, you can get everything pointing where it needs to point, including updating head, all with no branches. With a good JVM, the performance gain should be small enough to make it a premature optimization, though. I'm also curious how readable other people think my other suggestions are. :) \$\endgroup\$ – Peter Cordes Sep 18 '15 at 0:47
7
\$\begingroup\$
  • Give your Node class a constructor, so you can say p.next = new Node(data, p.next) to insert a new node after p.

  • Do one-less-than-N loop iterations, to stop at the node before where you want to insert. Then you don't need to shuffle around current and previous pointers.

  • Use the same code for both new-head special cases (pos = 0 or head = null). Your special-case handling takes more reading than it needs to because you operate differently in those cases.

  • Redesign the API to not throw away the work of chasing pointers out to the Nth node. Getting the head is O(1) if the caller wants it. Getting the Nth node is O(N), so the the hard-to-compute thing you could return is the Nth node (or its parent, but that is a little obscure). Talk to whoever gave you that behaviour requirement and help them design the API you and they are implementing so it doesn't suck. Using an API that makes efficient code impossible is really frustrating.

Java makes it hard / inconvenient to return multiple values from one function, since there is no pass-by-reference. In C or C++, I'd probably pass head by reference, so it'd be node_t *insert_nth(node_t *head, int data, int pos) in C. It's not the cleanest, though, and the "hidden" modification of some of your function parameters is what makes C++ non-const references nasty. That's why passing an actual pointer is clearer (so the caller has to write insert_nth(&head, ...), which makes it clear that head is being passed by reference, and the function might modify it.

Anyway, sorry for the tangent into C. In Java, your best bet might be to have callers pass iterators to your functions, instead of passing around raw Node references. Since you'd have a reference to the caller's iterator, you can modify it to point to a new head if you need to insert a new head.

If you don't want to do that, another option would be to not even provide this function. Or implement it as a convenience function on top of two others, for cases where the caller doesn't have a use for a reference to the new node you just inserted. vnp's answer already suggests breaking FindNth out as its own function.

The more basic functions would be

  • Node Advance(Node from, int distance) (same as C++'s std::advance(std::iterator it, int distance)).
  • Node InsertBefore(Node head, int data) and/or Node InsertAfter(Node at, int data), each returning the node they just inserted (new head or new tail, if used at the ends of the list). The arg to InsertBefore is named head as a reminder that it can't know about or do anything about the previous node's .next field.

I think it's a problem to pack so many different modes of operation into InsertNth. Often the caller will have to special case inserting a new head when position = 0, or whatever produced position=0 was the result of a special case. So just passing pos=0 to a do-everything function means the do-everything function has to decode the mode of operation again.

Even having an InsertNth function means thinking about your container as having numbered positions. If you want an InsertNth function, a linked list is probably the wrong data structure. I guess it can make sense for very small N at the front of a long list.

Anyway, having InsertNth as a basic building block in a linked list class, not implemented on top of anything else, doesn't pass the smell test, IMO. That said, once you do have an Advance(), InsertAfter, and InsertBefore, it's dead easy to implement InsertNth, and easy to look at and understand that it's correct without needing many comments to explain how it works.

 ///////////// UNTESTED CODE /////////////

/* Code is over-commented with comments on the design choice
 * I wouldn't pack this much into comments mixed in with the code normally

 * I decided not to use head as the name for my method arguments
 * to emphasize that they can and should be used on any element.
 */

// returns null if you go too far, rather than the tail
// a more useful API might give you the tail but also indicate that it wasn't actually the Nth
Node Advance(Node from, int distance)
{
    Node p = from;
    // maybe omit the p!=null test so we NullPointerException on distance too large
    while (p != null && distance-- > 0) {
        p = p.next;
    }
    return p;
    /* Depending on Advance to do nothing on a negative argument would be a poor choice
     * and would confuse people familiar with C++ std::advance,
     * which can go forward or backward (and would throw an exception trying to go backward on an iterator that can't do that.)
     * 
     * We could overload a negative argument to mean forward abs(distance), but return the tail instead of null on EOL
     * Using a differently-named function would be better, like AdvanceTail (not an ideal name, can't think of a good one).
     */
}

Node InsertBefore(Node head, int data)
{
    return new Node(data, head);
}

// Returns the new node, for symmetry with with InsertBefore
// maybe useful for callers that want to insert a new tail and keep track of it.
void InsertAfter(Node p, int data)
{
 /* letting the attempt to access p.next throw a NullPointerException is prob. best.
  * TopinFrassi had a good point that doing something similar to
  * but not exactly what was requested just makes it harder to debug.
  */
    // if (!p)
    //    return new Node(data, p); // this is InsertBefore
    p.next = new Node(data, p.next);
    return p.next;
}

Node InsertNth(Node head, int data, int pos) throws IllegalArgumentException
{
    if (head == null || pos <= 0)  // all the new-head special cases.
        return InsertBefore(head, data);
    Node prev = Advance(head, pos-1);
    if (prev == null)
        throw new IllegalArgumentException("End of list reached while looking for node " + pos-1);
    InsertAfter(prev, data);
    return head;
    // do nothing with prev
}

I think this is a pretty clean decomposition of the basic list ops into pieces that are likely to be widely useful in functions using lists. I think it's also quite easy to convince oneself that each method does what it claims, without having to think for too long. (Unless I've screwed one of them up. :P)

Having a Node constructor with initializer args is another big part of making the code clean, since being able to build & return it without needing a variable name saves a lot of lines of code. (Actually, InsertBefore just wraps the constructor, since we don't have any other bookkeeping for it to do. It could wrap a no-args constructor, and InsertNth would still use it and be compact and clean.)


First stab at writing InsertNth, before I thought about the API and the original problem-statement was leading you to implement a bad function.

Node InsertNth(Node head, int data, int position) throws IllegalArgumentException
{
    if (head == null || pos <= 0)  // all the new-head special cases.
        return new Node(data, head);

    Node p = head;  // p is a time-honoured variable name for list pointers in small C functions.  Choose a more Javaish (Java-ey?) name if you like.
    /* separate the counter check from the null check so we don't have a hard time sorting out what happened after the loop
     *  assuming we want to avoid just appending to the tail when that's not what was requested
     */
     // pre-decrement to stop on the node before N.
     //  Not that easy to notice, so maybe pos-- > 1 would be better
     //  to make it clear we stop one short of N.
    while (--position > 0) {
        // testing p.next instead of maintaining curr and prev pointers keeps the code compact.
        if (p.next == null)
            throw new IllegalArgumentException("End of list reached with " + position + " positions left to go");
        p = p.next;
    }
    p.next = new Node(data, p.next);
    return head;
}

// or with the dummy-node technique:
Node InsertNth_dummynode(Node head, int data, int position) throws IllegalArgumentException
{
     Node dummy = new Node(data, head);  // janos's dummy node idea.
     // now inserting a new head isn't a special case anymore.
     /* Having to follow the special-case through the rest of the function
      * to make sure the right thing happens
      * is extra work if you aren't used to the idiom.
      * It does an extra conditional branch, though.
      */

    Node p = dummy;
    while (position-- > 0) { ///// post-decrement, because the dummy node offsets us by one
        if (p.next == null)
            throw new IllegalArgumentException("End of list reached with " + position + " positions left to go");
        p = p.next;
    }

    // p.next = new Node(data, p.next);
    // return dummy.next;   // the simple way that discards dummy

   /* Reuse dummy as the newly inserted node,
    * with the downside of hurting your brain.
    * Complicated because of the possibility of p == dummy.
    * Using this harder-to-read code would usually be a case of premature optimization.
    */
    Node tmp = p.next;
    p.next = dummy;      // insert dummy into the list

    head = dummy.next;   // new head if p == dummy.  This statement has to appear in this order, after p.next=dummy, and before setting dummy.next to point to the rest of the list

    dummy.next = tmp;    // tack on the rest of the list
    // dummy.data = data;  // we did that in the constructor
    return head;
}

Creating dummy and throwing it away may not stress the garbage collector if your JVM realizes it can just allocate it on the stack. Since nothing outside the function ever sees a references to it, it's the easiest case for escape analysis.

Unless the JVM does a really good job with creating dummy efficiently on the stack (not heap) without a real call to new, reusing the dummy will be more efficient. That sequence at the end that sets p.next and dummy.next doesn't do much work per line. In terms of number of actual CPU operations, it's only 2 loads of locals vars from objects, and 2 stores to fields in objects. The other version does nearly that much just constructing a new Node, never mind the call to new.

However, it's significantly less readable, and needs comments to point out what's going on, so it's a pretty clear case of premature optimization.

\$\endgroup\$
  • \$\begingroup\$ Wow, that's a really detailed treatment, kudos! \$\endgroup\$ – janos Sep 18 '15 at 5:21
  • 2
    \$\begingroup\$ @janos: I didn't set out to write that much. It just happened after I started to think about how ridiculous it was to write InsertNth for a linked list. Thanks for the positive review. :) \$\endgroup\$ – Peter Cordes Sep 18 '15 at 14:41
  • 2
    \$\begingroup\$ I know, these things "just happen" :) \$\endgroup\$ – janos Sep 18 '15 at 14:46
6
\$\begingroup\$
  • Avoid special cases

    There is no need to handle head == null and/or position == 0 separately: the finder loop would break immediately either way. The only thing to test is whether prev == null (need to create new head) or not (old head stays).

  • Avoid naked loops

    The finder loop does a well defined job - it finds nth node - and deserves to be a method on its own.

  • Putting it all together

    Node FindNth(Node head, int position)
    {
        Node prev = null;
        int i = 0;
    
        while (head !=null && i < position) {
            prev = head;
            head = head.next;
            i++;
        }
    
        if (i < position) {
            // List is too short. Throw an exception perhaps?
        }
    
        return prev;
    }
    
    Node InsertNth(Node head, int data, int position) {
        Node newNode = new Node();
        newNode.data = data;
    
        Node prev = FindNth(head, position);
    
        if (prev == null) {
            newNode.next = head;
            head = newNode;
        } else {
            newNode.next = prev.next;
            prev.next = newNode;
        }
    
        return head;
    }
    
\$\endgroup\$
  • \$\begingroup\$ Isn't finder gives the (n-1)th node? \$\endgroup\$ – CodeYogi Sep 17 '15 at 19:35
  • \$\begingroup\$ It does. For a production quality code we need better naming. \$\endgroup\$ – vnp Sep 17 '15 at 19:39
3
\$\begingroup\$

You handled a case that your scenario didn't ask you to support. Usually, this is something you want to avoid. Stick to the requirements! If your position > size of linked list, you decided to add that element at the end of the list. But is this really the wanted behavior? You should consider throwing an exception instead. Think about it :

//That's gonna be C#'s syntax, I'm not sure if it's exactly the same in java
//But you'll understand :p
int[] array = new int[2];
array[3] = 1;

What do you usually expect? An exception, or that array[2] = 1?

The thing is, if a user of your method inputs something, they want exactly that to be done, not a fallback scenario. Let the user know it didn't work, it's better this way.

Don't think about recursion, your while loop is a very good way to tackle this problem. Recursion has no easy way in this problem I think. I think your solution is very fine.

\$\endgroup\$

protected by Jamal Mar 31 at 1:45

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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