java 手动链表 - 在方法之前插入
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6824067/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Manual Linked List - Insert before method
提问by Kevin
This is part of an exercise we did in class, I just can't figure it out...
这是我们在课堂上做的练习的一部分，我就是想不通……
The required method is the insertBefore(object data) method wherein when a user choose this method it will prompt it to enter a data to be inserted before the reference data(input by user)
所需的方法是 insertBefore(object data) 方法，其中当用户选择此方法时，它会提示它在引用数据（用户输入）之前输入要插入的数据
An example of how it should run:
它应该如何运行的一个例子：
// assuming linked list has data 1,2,3 inserted already
Choose Method:
1)Insert Before
choice: 1 // input by user
====Insert Before====
Enter Reference data: 2 // input by user
Enter Data to be inserted: 5 // input by user
supposed output: 1,5,2,3
Here's my code for this exercise: (This is inside a class called LinkList with variables
这是我用于此练习的代码：（这是在一个名为 LinkList 的类中，带有变量
protected int end;
protected Node start;
and an inner class called Node)
和一个名为 Node 的内部类）
private class Node
{
public char data;
public Node next;
public Node(char data)
{
this.data = data;
}
}
public void insertBef(char ref,char data)
{
Node temp = new Node(data);
Node current = start;
if(end!=0)
{
for(int i = 1; i<end; i++)
{
if(current == start)
{
Node newNode = start;
newNode.data = current.data;
newNode.next = temp;
current = current.next;
}
else if(current.data == ref)
{
Node newNode = current;
newNode.data = current.data;
newNode.next = temp;
current = current.next;
}
}
end++;
}
else
{
temp.next = start;
start = temp;
}
end++;
}
But when I run my code it ouputs 3,5, not 1,5,2,3! I can't see where I might have gone wrong...
但是当我运行我的代码时，它会输出3,5，而不是1,5,2,3！我看不出我哪里出错了......
Can someone please tell me where the mistake is, and explain how I might fix it?
有人可以告诉我错误在哪里，并解释我如何解决它？
I understand that to be able to insert before a reference value you should:
我知道为了能够在参考值之前插入，您应该：
- Make a new node for the new data
- Make a temporary node for the reference value and link
- Make the link of the data before the reference value point to the new node and make the link of the new node point to the temporary node
- 为新数据创建一个新节点
- 为参考值和链接制作一个临时节点
- 使参考值之前的数据的链接指向新节点，使新节点的链接指向临时节点
I just can't seem to figure out how to implement it in Java code...
我似乎无法弄清楚如何在 Java 代码中实现它......
回答by Bohemian
When programming, if it seems hard, you're probably going about it the wrong way...
在编程时，如果它看起来很难，那么您可能会以错误的方式进行...
You only need one line of code to accomplish the task!
您只需要一行代码即可完成任务！
list.add(list.indexOf(reference), data);
Here's this line wrapped as an insertBeforemethod:
这是作为insertBefore方法包装的这一行：
public static void insertBefore(List<Integer> list, int reference, int data) {
list.add(list.indexOf(reference), data);
}
Here's a test using your example:
这是使用您的示例进行的测试：
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>(Arrays.asList(1, 2, 3));
insertBefore(list, 2, 5);
System.out.println(list);
}
Output:
输出：
[1, 5, 2, 3]
Note: This code will throw an exception if the reference element is not found.
I'll leave it to you to plug that hole.
注意：如果未找到引用元素，此代码将引发异常。
我会让你来堵住那个洞。
回答by Coeffect
First things first: forloops are generally a bad idea with linked lists. whileloops are much better; you can do something like while(next != null).
首先要做的事情是：for循环对于链表来说通常是个坏主意。while循环要好得多；你可以做类似的事情while(next != null)。
Looking at your code, you seem to have a few problems.
查看您的代码，您似乎遇到了一些问题。
Your for loop is overly complicated, and doesn't seem to make a lot of sense. Here's how your loop should look:
您的 for 循环过于复杂，似乎没有多大意义。以下是您的循环的外观：
- Get head node
- Begin looping through the list, checking the next node's value as you go
- Once you find that the next node's value is the one you're looking for, creating a new node.
- Insert the new node by setting its Next value to be equal to the current node's Next value, then set the current node's next value to be the new node.
- Return from the function.
- 获取头节点
- 开始遍历列表，边走边检查下一个节点的值
- 一旦您发现下一个节点的值就是您要查找的值，就创建一个新节点。
- 通过将其 Next 值设置为等于当前节点的 Next 值来插入新节点，然后将当前节点的 next 值设置为新节点。
- 从函数返回。
Your middle bullet point is actually unnecessary, and I have no idea what you use endfor. Regardless, you seem to have the basic principle down, so I won't feel like I'm spoiling you by posting code.
你的中间要点实际上是不必要的，我不知道你用什么end。无论如何，您似乎没有基本原则，所以我不会觉得我通过发布代码来破坏您。
Now, I'm not sure what your startis. Does it hold a value, or is it a dedicated head node? I'd vote for a dedicated head node, I generally find it easier to work with because you don't need to add code for a special case where the number should come before the head. So your start node should be "empty"; the value it holds is ignored, the only thing it's used for is to keep a pointer to the first legit node in the list. If you do this, the insertBef method becomes incredibly simple. NOTE: untested code to follow.
现在，我不确定你start是什么。它是否持有价值，还是一个专用的头节点？我会投票给一个专用的头节点，我通常发现它更容易使用，因为您不需要为数字应该在头之前的特殊情况添加代码。所以你的起始节点应该是“空的”；它持有的值被忽略，它唯一的用途是保持一个指向列表中第一个合法节点的指针。如果您这样做，insertBef 方法将变得非常简单。注意：要遵循未经测试的代码。
public void insertBef(char ref, char data)
{
Node current = start;
while( current.next != null )
{
if( current.next.value == ref )
{
Node n = new Node(data);
n.next = current.next;
current.next = n;
return;
}
current = current.next;
}
}
Please don't just copy the code. If you have questions, post them and I'll do my best to answer.
请不要只是复制代码。如果您有任何问题，请发布它们，我会尽力回答。
