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

Question

我正在为我的数据结构类做一个项目，这个项目要求我写一个类来实现一个int型的链表。

• 为Node使用内部类
• 包括以下方法。
• 编写一个测试器，让你可以用任何你想要的数据以任何顺序测试所有的方法。

我有一个叫做"public void insertAt(int index, int item)"的方法。此方法的目的是"在位置index插入一个项，该位置index被传递给方法"。下面是这个方法的代码。当我在索引中插入一个项目时，它会工作，除非它是列表中的最后一个项目。当我试图在列表的末尾插入一个项目时，它会替换最后一个项目，而之前在那里的项目在不应该被删除时被删除。例如，如果我有一个列表:"[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分配给newItem的nextNode，这就可以了。

另外，确保处理了实现中的其他问题，例如在索引0处添加元素。目前，在开始时您设置Node prev = null;，然后在循环的第一次迭代中prev为null，每当您尝试添加索引为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;
}

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