如何在链表中插入特定索引处的项?

Question

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

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

我必须创建一个名为"public void insertAt(int index, int item)"的方法。此方法的目的是"在位置index插入一个项，该位置index被传递给方法"。下面是这个方法的代码。当我执行这个方法时，什么也没发生。我试图添加到特定索引的项永远不会被添加。有人知道我做错了什么吗?和如何解决?

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 1

有一些问题，但你是大多数的方式，你只需要移动if语句if (index == i) {Node newItem... }在你的'for'循环，像这样:

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++;
}
}

请注意，您的代码有一个错误，该错误已通过检查下一个节点不为空来修复。

我们可以通过在索引2后面插入999看到更新后的方法是有效的:

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

如果您希望条目插入索引2，则调整顺序，将if语句放在prev = temp;语句之前