如何在列表末尾插入一个项目？

Question

我正在为我的数据结构 class 开发一个项目，该项目要求我编写一个 class 来实现一个整数链表。

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.

我有一个名为“public void insertAt(int index, int item)”的方法。此方法旨在“在位置索引处插入一个项目，其中索引传递给方法”我在下面有此方法的代码。当我在索引处插入一个项目时，除非它是列表中的最后一个项目，否则它会起作用。当我尝试在列表末尾插入一个项目时，它会替换最后一个项目，并且之前存在的项目在不应该被删除时被删除。例如，如果我有一个列表：“[9, 8, 15, 7, 5, 15, 19, 6, 19, 2]”，我想插入数字“90”，最后一个索引应该是这样的[9, 8, 15, 7, 5, 15, 19, 6, 19, 90, 2] 但是我得到 [9, 8, 15, 7, 5, 15, 19, 6, 19, 90]。我怎样才能在我的代码中解决这个问题，这样如果我要在尾部插入一个项目，它会将我想要插入的项目移动到尾部之前？

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 1

你在这行有错误：

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

在这里，temp 是您的最后一个元素，2。您的新元素 (90) 只会分配 temp，它的 temp 有一个指向下一个元素的指针 (temp.nextNode != null) 因为 temp 没有下一个元素，所以 nextNode 根本不会被分配。事实上，如果 temp 为 null ，您完全可以省略此检查，您只需将 null 分配给 newItem 的 nextNode 就可以了。

此外，请确保在您的实现中处理其他问题，例如在索引 0 处添加元素。目前，在开始时您设置 Node prev = null; 然后在循环的第一次迭代中 prev 为空，每当您尝试在索引 0.

处添加元素时，您最终都会遇到 NPE

要解决此问题，您需要更改此部分：

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

进入

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

编写良好的单元测试可以帮助您实现健壮的实现，并帮助您更快地解决此类问题。查看此 question 以了解如何在 java.

中编写单元测试

如何在列表末尾插入一个项目？

How can I insert an Item at the end of the List?

java

linked-list

nodes

tail