Implementing an AddAtIndex method in a LinkedList

Question

currently, I am working on implementing an AddAtIndex method and for the most part it seems to be working fine. However, my method is not passing my JUnit test and I can't seem to understand why. Thus, I have chosen to show the code I have done thus far:

**
     * Add an element to the list at the specified index
     * @param The index where the element should be added
     * @param element The element to add
     */
    public void add(int index, E element ) //Method should be O(1) time.
    {
        // TODO: Implement this method
        if (index < 0) { 
            System.out.println("Can't add an element at a negative index.");
        }
        int i = 0;
        LLNode<E> currentNode = head.next;
        while ( i < size ) {
            if ( i == index ) {
                LLNode<E> newNode = new LLNode<E>(element);
                LLNode<E> tempNode = new LLNode<E>(currentNode.data);

                currentNode.next = tempNode;
                currentNode.data = newNode.data;

                newNode.prev = currentNode.prev;
                newNode.next = tempNode;
                tempNode.prev = newNode;
                size++;
            }
            currentNode = currentNode.next;
            i++;
        }

    }

My thought process behind the code is that the method creates a new Node, then it replaces the data at the specified index of the linked list. However, the data at the node it is replacing is stored in a temporary node which is incremented in position to the next node after the new node. I am about 80% confident in my implementation though the code looks a bit sloppy. I have created a driver to demonstrate the implementation. The drivers code is as follows:

public class LinkedListDriver {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyLinkedList<String> nameList = new MyLinkedList<String>();
        nameList.add("Hamadi");
        nameList.add("Ballo");
        nameList.add(1, "Salisu");
        nameList.add(2, "Galo");
        System.out.println(nameList.toString());
        System.out.println(nameList.size());
        nameList.set(2, "Abdullahi");
        System.out.println(nameList.toString());
        nameList.remove(1);
        System.out.println(nameList.toString());
        MyLinkedList<Integer> list1 = new MyLinkedList<Integer>();
        list1.add(65);
        list1.add(21);
        list1.add(42);
        System.out.println(list1.toString());
        list1.remove(0);
        System.out.println(list1.toString());
    }

}

The Output from the driver is as follows:

List: Hamadi, Salisu, Galo, Ballo, 
4
Replacing Galo with Abdullahi
List: Hamadi, Salisu, Abdullahi, Ballo, 
Removing Salisu from the list
List: Hamadi, Abdullahi, Ballo, 
List: 65, 21, 42, 
Removing 65 from the list
List: 21, 42, 

The unit test fails however with the following error:

It fails at the AssertEquals method:

shortList.add(2, "E");
        shortList.add(3, "F");
        **assertEquals("AddAtIndex: at position 2 ", "E", shortList.get(2)); //fails here**
        assertEquals("AddAtIndex: at position 3 ", "F", shortList.get(3));
        assertEquals("AddAtIndex: List size is ", 6, shortList.size());

I would like to know what I'm doing wrong. I have this literally completely figured out, though I know that there is something a bit off about my AddAtindex method. Thanks!

Answer 1

I used head and tail as sentinel nodes. Created a new node to be added in the list.

public boolean add(E element) {
        // create new element
        LLNode<E> variable = new LLNode(element);
        variable.next = null;
        variable.prev = null;

        // if element is null, throw exception
        if (element == null) {
            // return false;
            throw new NullPointerException("Element is null");
        } else {
            // get the value stored in tail.prev in variable temp. 
            variable.prev = tail.prev;
            variable.next = tail;
            // now modify the tail node prev and new node next
            tail.prev = variable;

            // get prev node next link changed
            variable.prev.next = variable;

            // update size
            if (head.next.next != tail) {
                size++;
            }
            return true;
        }
    }

Answer 2

You don't need that tempNode. Just create the newNode and insert it properly between currentNode and its previous node.

You should also consider the possibility of adding an element at the beginning (no previous) or end (no next) of the list.