How can I insert an Item at the end of the 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 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 insert an Item at an Index it works unless it’s the last item in the list. When I try to insert an item at the end of the list it replaces the last item and the item that was there before is erased when It shouldn’t. For example, If I had a list: “[9, 8, 15, 7, 5, 15, 19, 6, 19, 2]” and I want to insert the number “90” and the last index it should look like [9, 8, 15, 7, 5, 15, 19, 6, 19, 90, 2] but instead I get [9, 8, 15, 7, 5, 15, 19, 6, 19, 90]. How can I fix this in my code so if I was to insert an item at the tail it would move the Item I want inserted to be placed before the tail?

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) {
            if (index == i) {
                Node newItem = new Node(item, null);
                prev.nextNode = newItem;
                if (temp.nextNode != null) {
                    newItem.nextNode = temp;
                }
            }
            if (temp.nextNode != null) {
                prev = temp;
                temp = temp.nextNode;
                i++;
            }
        }
    }

    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

You have an error in this line:

if (temp.nextNode != null) {
    newItem.nextNode = temp;
}

Right there, temp is your last element, be it 2. Your new element ( 90) will only have temp assigned, it temp has a pointer to the next element (temp.nextNode != null) Because temp has no next element, nextNode won’t be assigned at all. In fact, you can omit this check at all cause if temp was null , you would only assign null to the nextNode of the newItem which would be fine.

Also, make sure to handle other issues in your implementation, such as adding the element at index 0. At the moment, in the beginning you set Node prev = null; and then in the first iteration of the loop prev is null and you would end up with the NPE whenever you try to add the element at index 0.

To fix this, you need to change this section:

 if (index == i) {
     Node newItem = new Node(item, null);
     prev.nextNode = newItem;
     newItem.nextNode = temp;
 }

into

 if (index == i) {
     Node newItem = new Node(item, null);
     if (prev != null) {
         prev.nextNode = newItem;
     }
     newItem.nextNode = temp;
 }

Writing good unit tests may help you with the robust implementation and will help you solve this kind of issues much quicker. Check out this question to see how to write unit tests in java.

Advertisement

Answer