How do I insert an Item at a certain Index in a Linked List?

I am working on a project for my Data Structures class that asks me to write a class to implement a linked list of ints.

• Use an inner class for the Node.
• Include the methods below.
• Write a tester to enable you to test all of the methods with whatever data you want in any order.

I have to create a method called “public void insertAt(int index, int item)”. This method is meant to “Insert an item at position index, where index is passed to the method” I have my code for this method down below. When I execute this method nothing happens. The item that I try to add to a specific index never gets added. Does someone know what I did wrong? and How to fix it?

import java.util.Random;
import java.util.Scanner;

public class LinkedListOfInts {
    Node head;
    Node tail;

    private class Node {
        int value;
        Node nextNode;

        public Node(int value, Node nextNode) {
            this.value = value;
            this.nextNode = nextNode;
        }

    }

    public LinkedListOfInts(LinkedListOfInts other) {
        Node tail = null;
        for (Node n = other.head; n != null; n = n.nextNode) {
            if (tail == null)
                this.head = tail = new Node(n.value, null);
            else {
                tail.nextNode = new Node(n.value, null);
                tail = tail.nextNode;
            }
        }
    }

    public LinkedListOfInts(int[] other) {
        Node[] nodes = new Node[other.length];
        for (int index = 0; index < other.length; index++) {
            nodes[index] = new Node(other[index], null);
            if (index > 0) {
                nodes[index - 1].nextNode = nodes[index];
            }
        }

        head = nodes[0];
    }

    public LinkedListOfInts(int N, int low, int high) {
        Random random = new Random();
        for (int i = 0; i < N; i++)
            this.addToFront(random.nextInt(high - low) + low);
    }

    public void addToFront(int x) {
        head = new Node(x, head);
    }

    public void insertAt(int index, int item) {
        Node temp = head;
        Node prev = null;
        int i = 0;
        for (Node ptr = head; ptr != null; ptr = ptr.nextNode) {
            prev = temp;
            temp = temp.nextNode;
            i++;
        }
        if (index == i) {
            Node newItem = new Node(item, null);
            prev.nextNode = newItem;
            newItem.nextNode = temp;
        }
    }

    public String toString() {
        String result = "";
        for (Node ptr = head; ptr != null; ptr = ptr.nextNode) {
            if (!result.isEmpty()) {
                result += ", ";
            }
            result += ptr.value;
        }
        return "[" + result + "]";
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        LinkedListOfInts list = new LinkedListOfInts(10, 1, 20);
        boolean done = false;
        while (!done) {
            System.out.println("1. Insert At");
            System.out.println("2. toString");
            switch (input.nextInt()) {
            case 1:
                System.out.println("Insert an Item to a certain Index on the List");
                list.insertAt(input.nextInt(), input.nextInt());
                break;
            case 2:
                System.out.println("toString");
                System.out.println(list.toString());
                break;

            }
        }
    }
}

Answer

There are a few issues, but you are most of the way there, you simply need to move the if statement if (index == i) {Node newItem... } inside of your ‘for’ loop like this:

public void insertAt(int index, int item) {
    Node temp = head;
    Node prev = null;
    int i = 0;
    for (Node ptr = head; ptr != null; ptr = ptr.nextNode) {
        prev = temp;
        //Make sure the next node is not null
        if (temp.nextNode != null) {
            temp = temp.nextNode;
        }

        //Move the if check here inside the for loop, but before i++
        if (index == i) {
            Node newItem = new Node(item, null);
            prev.nextNode = newItem;
            //Make sure the next node is not null
            if (temp.nextNode != null) {
                newItem.nextNode = temp;
            }
        }

        //now advance the index after the above
        i++;
    }
}

Note that your code had an error, which has been fixed by checking that the next node is not null.

We can see the updated method works by inserting 999 after index 2:

1. Insert At
2. toString
1
Insert an Item to a certain Index on the List
2 999
1. Insert At
2. toString
2
toString
[5, 18, 8, 999, 11, 11, 1, 19, 3, 1, 10]
1. Insert At
2. toString

If you want the item to be inserted at index 2 instead, then adjust the order and put the if statement before prev = temp;