Implementing a linkedlist in java

Question

I am learning data structures current and below is my implementation for linkedlist.I have kept it as simple as possible as my aim here is to understand the logic.

/*
 * Singly linked list
 */
package linkedlisttest;


class Node {
    int data;
    Node next;

    public Node(int data) 
    {
        this.data = data;
    }

}

class LinkedList {

    Node head;

    public void add(int data) 
    {
        if (head == null) 
        {
            head = new Node(data);  
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new Node(data);
    }

    public int getSize() {
        int i = 0;
        Node current = head;
        while (current != null) {
            i += 1;
            current = current.next;
        }
        return i;
    }

    public void add(int data, int index) 
    {
        if (head == null && index == 0) 
        {
              head = new Node(data);
              return;
        } else if (head == null && index != 0) {
              return; // invalid position
        } else if ( index > getSize() ) {
            return;
        }

        Node current = head;
        //iterate through whole list 
        int pos = -1; 
        Node previous = null;
        Node next = null;
        Node newNode = new Node(data);
        //find next and previous nodes with relation to position
        while (current != null) {
            if (pos == index - 1) {
                previous = current;
            } else if (pos == index + 1) {
                next = current;
            }
            pos++;
            current = current.next;
        }
        previous.next = newNode;

        newNode.next = next;

    }

    public void print() 
    {
        Node current = head;
        while (current.next != null) {
            System.out.print(current.data + "->");
            current = current.next;
        }
        System.out.print(current.data);
    }

}

public class LinkedListTest {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        LinkedList lt = new LinkedList();
        lt.add(3);
        lt.add(5);
        lt.add(6);
        lt.add(4,1);
        lt.print();
    }

}

The bug happens for lt.add(4,1) and i suspect its an off by one error.

Expected output: 3->4->6

Actual output: 3->5->4

Thanks for the help guys...

Edit

Thanks to @StephenP and @rosemilk for their help.Indeed the code above has a logical bug as it replaces the value at index and not add it.

Here is the new optimized code

/*
 * Singly linked list
 */
package linkedlisttest;

class Node {

    int data;
    Node next;

    public Node(int data) {
        this.data = data;
    }

}

class LinkedList {

    Node head;
    int size;

    /**
     *
     * @param data element to add to list 
     * Time Complexity : O(n)
     */
    public void add(int data) {
        if (head == null) {
            head = new Node(data);
            size += 1;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new Node(data);
        size += 1;
    }

    /**
     *
     * @return size of list 
     * Time Complexity: O(1) 
     * This is because we use a class
     * variable size to keep track of size of linked list
     */
    public int getSize() {
        return size;
    }
    /**
     * 
     * @param data element to insert 
     * @param index position at which to insert the element (zero based)
     * Time Complexity : O(n)
     */
    public void add(int data, int index) {

        if (index > getSize()) {
            return; // invalid position
        }

        Node current = head; //iterate through whole list 
        int pos = 0;
        Node newNode = new Node(data);

        if (index == 0) // special case, since its a single reference change!
        {
            newNode.next = head;
            head = newNode; // this node is now the head
            size += 1;
            return;
        }
        while (current.next != null) {
            if (pos == index - 1) {
                break;
            }
            pos++;
            current = current.next;
        }
        // These are 2 reference changes, as compared to adding at index 0
        newNode.next = current.next; // here we are changing a refernce
        current.next = newNode; // changing a reference here as well
        size += 1;

    }

    /**
     * Prints the whole linked list 
     * Time Complexity : O(n)
     */
    public void print() {

        if(getSize() == 0) { //list is empty
            return;
        }
        Node current = head;
        while (current.next != null) {
            System.out.print(current.data + "->");
            current = current.next;
        }
        System.out.print(current.data + "\n"); 
    }
}

public class LinkedListTest {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        LinkedList lt = new LinkedList();
        lt.print();
        lt.add(3);
        lt.add(5);
        lt.add(6);
        lt.print();
        lt.add(4, 1);
        lt.print();
        lt.add(4, 7);// 7 is an invalid index
        lt.add(8, 3);
        lt.print();
    }

}

Answer 1

Your add (int , int ) function has a logical bug and can be made better. You don't need previous current and next references, and can cleverly manipulate the list using just the reference to current node, handling inseration at index 0 separately. I would write the add function as follows

public void add(int data, int index) 
{
    if ( index > getSize() ) {
        return; // invalid position
    }

    Node current = head; //iterate through whole list 
    int pos = 0; 
    Node newNode = new Node(data);

    if (index == 0) // special case, since its a single reference change!
    {
        newNode.next = head; 
        head = newNode; // this node is now the head
        return;
    }
    while (current.next != null) {
        if (pos == index - 1) {
            break;
        }
        pos++;
        current = current.next;
    }
    // These are 2 reference changes, as compared to adding at index 0
    newNode.next = current.next; // here we are changing a refernce
    current.next = newNode; // changing a reference here as well

}

Also, your print function gives a NullPointerException when you try to print an empty list. I would write the print function like this,

public void print() 
{
    Node current = head;
    while (current != null) {
        System.out.print(current.data + "->");
        current = current.next;
    }
    System.out.println("null"); // this is just to say last node next points to null!
}

Hope this helps :)

Answer 2

Currently, if you print out pos in your loop, the indices are -1, 0, 1 (instead of 0, 1, 2), so it'll never "find" the correct next. Replace int pos = -1; with int pos = 0; and it'll work.

I do agree with @StephenP that the output should (arguably) be 3->4->5->6, but that's a design decision.