Inserting a node at a specific position in a linked list

Posted on

Problem

Given a node class like

class Node {
     int data;
     Node next;
  }

Provide an implementation to Insert a node at a specific position in a linked list

Node insert(Node head, int data, int position) {

    Node newNode = new Node();
    newNode.data = data;
    newNode.next = null;

    if(head == null && position != 0) {
        return head;
    } else if(head == null && position == 0) {
        head = newNode;
        return head;
    }

    if(position == 0) {
        newNode.next = head;
        head = newNode;
        return head;
    }

    Node current = head;
    Node previous = null;
    int i = 0;

    for(i = 0; i < position; i++) {
        previous = current;
        current = current.next;
        if(current == null)
            break;
    }

    newNode.next = current;
    previous.next = newNode;
    return head;

}

Can you please critic my code and provide your thoughts on where I should improve my code.

Solution

  • Avoid special cases

    If position == null the new node becomes head no matter what, and you don’t need to care what the head was before.

    Similarly, the validity of position is determined in a traversal loop (if (current == null) condition); testing specifically for head == null && position != 0 is premature.

    BTW, the code handles invalid position inconsistently. Yet another cause to avoid special cases.

  • Avoid naked loops

    Every loop does an important job, and deserves a name. The loop

    for(i = 0; i < position; i++)
    

    serves a purpose of finding a node at the particular position. Factor it out into a method and name it properly.

Leave a Reply

Your email address will not be published. Required fields are marked *