java 在单个链表中添加节点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13679047/
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
Add a node in a single linked list
提问by Jeroen Vannevel
Good evening
晚上好
I'm trying to implement a single linked list by myself and I've run into an issue when I want to create a search method. Evidently when you want to search for a node (which will be used to insert a node at a certain place) you will have to evaluate some values to see if you reached the right spot. Considering my nodes only have a data field as a identifier, I don't see any other way than using that. However, since the data field isn't unique there might be multiple nodes eligible.
我正在尝试自己实现一个单链表，但是当我想创建一个搜索方法时遇到了一个问题。显然，当您想要搜索一个节点（将用于在某个位置插入一个节点）时，您必须评估一些值以查看您是否到达了正确的位置。考虑到我的节点只有一个数据字段作为标识符，我看不到除了使用它之外的任何其他方式。但是，由于数据字段不是唯一的，因此可能有多个节点符合条件。
Consider the following list: 5, 7, 2, 8, 3, 1, 6, 5, 8, 4, 2. When I want to add a node somewhere in the list (say: After the node with value 8) he will go trough the list and add the new node after the first occurrence of '8'. What should I do if I wanted to insert it after the 2nd 8?
考虑以下列表：5, 7, 2, 8, 3, 1, 6, 5, 8, 4, 2. 当我想在列表中的某处添加一个节点时（例如：在值为 8 的节点之后）他会遍历列表并在第一次出现“8”后添加新节点。如果我想在第 2 个 8 之后插入它，我该怎么做？
Is this even possible with a Single Linked List?
这甚至可以使用单链表吗？
Other than that I'd like to have some feedback on my 'removeLast()' method which doesn't seem to do what I want it to do (remove the last node from the list). I am aware my code isn't supposed to work if the list has only 1 value, I'll look into that as soon as the general code of removing the last node works.
除此之外，我想对我的“removeLast()”方法有一些反馈，该方法似乎没有做我想要它做的事情（从列表中删除最后一个节点）。我知道如果列表只有 1 个值，我的代码不应该工作，一旦删除最后一个节点的通用代码起作用，我就会研究它。
My code can be found here.
我的代码可以在这里找到。
Edited with code:
用代码编辑：
public class SingleLinkedList {
public void deleteLast() {
if (lastNode != null) {
Node currentNode = firstNode;
while (currentNode != null) {
Node nextNode = currentNode.getNextNode();
Node nextNextNode = nextNode.getNextNode();
if (nextNextNode == null) {
nextNextNode = null;
lastNode = nextNode;
}
}
listSize--;
}
}
}
}
回答by amit
Sure it can be done - you need to keep track of the number of objects you have passed in the way, and after you have passed nobjects equals to the seeked one - insert the new data:
当然可以做到 - 您需要跟踪您在途中传递的对象数量，并且在传递的n对象等于所寻找的对象之后- 插入新数据：
public void addAfterNth(Object data,Object o, int n) {
Node curr = firstNode;
while (curr != null) {
if (curr.data.equals(o)) n--;
if (n == 0) {
Node newNode = new Node(data,curr.nextNode);
curr.setNext(newNode);
break;
}
curr = curr.getNextNode();
}
}
In here you insert a new node with the data denoted in the parameter dataafter the nth encounter of a node with data equals to o.
在这里，您在遇到数据等于 的节点data后插入一个新节点，该节点的数据表示在参数n中o。
Running with:
运行：
SingleLinkedList list = new SingleLinkedList();
list.addLast(5);
list.addLast(7);
list.addLast(2);
list.addLast(8);
list.addLast(3);
list.addLast(1);
list.addLast(6);
list.addLast(5);
list.addLast(8);
list.addLast(4);
list.addLast(2);
list.drawList();
list.addAfterNth(999,8, 2);
System.out.println("");
list.drawList();
yields (as expected):
产量（如预期）：
5, 7, 2, 8, 3, 1, 6, 5, 8, 4, 2,
5, 7, 2, 8, 3, 1, 6, 5, 8, 999, 4, 2,
回答by Rahul
Here is the pseudo code for deleting the last code of a LL. The above answer correctly answers your question of inserting at a specific position.
这是删除 LL 的最后一个代码的伪代码。以上答案正确回答了您在特定位置插入的问题。
if (START == NULL){
Print: Linked-List is empty.
}
else{
PTR = START, PREV = START
while (PTR->LINK != NULL)enter code here
PREV = PTR //Assign PTR to PREV
PTR = PTR->LINK //Move PTR to next node
ITEM = PTR->INFO //Assign INFO of last node to ITEM
If (START->LINK == NULL) Then //If only one node is left
START = NULL //Assign NULL to START
Else
PREV->LINK = NULL //Assign NULL to link field of second last node
Delete PTR
}
