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

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.

Implementing an AddAtIndex method in a LinkedList

Sign up