java 将节点插入链表中间，并且不小心插入了空节点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13262333/
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
Inserting Node into middle of Linked List, and accidentally inserting null node as well
提问by JayneCobb's_HatDesigner
I'm working on a program that does not use Java's built in Linked List class; I'm building it from scratch. I've been successful with everything except writing a method that inserts a Node into a particular position of the linked list.
我正在开发一个不使用 Java 内置链表类的程序；我正在从头开始构建它。除了编写一个将节点插入到链表特定位置的方法之外，我在所有方面都取得了成功。
I have a method that sets a particular Node as the "current" Node. So, for example, I have a linked list that looks like this: cats--> dogs--> make--> good--> pets, and "current" is equal to 2; that means that the "current" Node is "dogs".
我有一种方法可以将特定节点设置为“当前”节点。因此，例如，我有一个看起来像这样的链表：猫-->狗-->制造-->好-->宠物，并且“当前”等于 2；这意味着“当前”节点是“狗”。
From here, let's say I want to insert a new Node at the position of "current" whose info field reads and. If done correctly, the final linked list will be: cats--> and--> dogs--> make--> good--> pets; "and" will replace "dogs" at position 2.
从这里开始，假设我想在“当前”的位置插入一个新节点，其信息字段为和。如果操作正确，最终的链表将是：cats--> and--> dogs--> make--> good--> pets；“and”将替换位置 2 处的“dogs”。
So here's my problem: my method works to insert a new Node at position two, but something's going wrong with linking the newly created node to pre-existing nodes. Not only am I inserting my new node into the list, but I'm also inserting a node with no information before "dogs". As my code currently runs, the output looks like this: cats--> and--> (blank) --> dogs--> make--> good--> pets.
所以这是我的问题：我的方法可以在位置 2 插入一个新节点，但是将新创建的节点链接到预先存在的节点时出现问题。我不仅将我的新节点插入到列表中，而且我还在“狗”之前插入了一个没有信息的节点。当我的代码当前运行时，输出如下所示：猫-->和-->（空白） -->狗-->制作-->好-->宠物。
I'm 99.9% sure the problem lies in the (if current != null) portion of the code, I just can't figure out how to fix it.
我 99.9% 确定问题出在代码的（如果当前！= null）部分，我只是不知道如何修复它。
Any thoughts on why I'm inserting a blank node in addition to the node I actually want to add?
除了我实际想要添加的节点之外，还有什么关于为什么我要插入一个空白节点的想法吗？
public void insert () {
System.out.println("Please enter the text you wish to insert, or type \"end\" if you are done inserting.");
String theString;
theString = console.nextLine();
while (!theString.equals("end")){
newNode = new Node ();
newNode.info = theString;
newNode.next = null;
if (first == null){
first = newNode;
last = newNode;
} else if (current != null){
Node p = new Node (current.info, current.next);
current.info = newNode.info;
current.next = p;
}
else {
last.next = newNode;
last = newNode;
}
System.out.println("Please enter the text you wish to insert, or type \"end\" if you are done inserting.");
theString = console.nextLine();
}
}
EDIT
编辑
The entire program is quite long, but here is the "setLine" method which sets current equal to whatever position the user wishes to insert their Node at. It takes a parameter "int line" which is obtained via a user prompt.
整个程序很长，但这里是“setLine”方法，它将当前设置为用户希望插入节点的任何位置。它需要一个通过用户提示获得的参数“int line”。
public Node setLine(int line) {
int index = 0;
current = first;
while (index < line) {
previous = current;
current = current.next;
index++;
}
return current;
}
回答by Zzz
Here is a code that inserts the node properly. This should be a good starting point, good luck(you can read more here: http://www.algolist.net/Data_structures/Singly-linked_list/Insertion).
这是正确插入节点的代码。这应该是一个很好的起点，祝你好运（你可以在这里阅读更多信息：http: //www.algolist.net/Data_structures/Singly-linked_list/Insertion）。
public class SinglyLinkedList {
public void addLast(SinglyLinkedListNode newNode) {
if (newNode == null)
return;
else {
newNode.next = null;
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
}
}
public void addFirst(SinglyLinkedListNode newNode) {
if (newNode == null)
return;
else {
if (head == null) {
newNode.next = null;
head = newNode;
tail = newNode;
} else {
newNode.next = head;
head = newNode;
}
}
}
public void insertAfter(SinglyLinkedListNode previous,
SinglyLinkedListNode newNode) {
if (newNode == null)
return;
else {
if (previous == null)
addFirst(newNode);
else if (previous == tail)
addLast(newNode);
else {
SinglyLinkedListNode next = previous.next;
previous.next = newNode;
newNode.next = next;
}
}
}
}
回答by Venky
You can refer the following method which inserts node in the middle, based on the index.
您可以参考以下基于索引在中间插入节点的方法。
public boolean insertInMiddle(int index, int data){
boolean isInserted = false;
Node node = new Node(data);
Node temp = head;
int i=0;
if(index >= 0 && index <= size()){
isInserted = true;
if(index == 0){
if(head !=null){
node.nextNode = head;
head.prevNode = node;
head = node;
}else{
head = node;
tail=node;
}
}else{
while(i<index){
temp = temp.nextNode;
i++;
}
if(temp == null){
node.nextNode = temp;
node.prevNode = tail;
node.prevNode.nextNode = node;
tail=node;
}else{
node.nextNode = temp;
node.prevNode = temp.prevNode;
temp.prevNode = node;
node.prevNode.nextNode = node;
}
}
}
return isInserted;
}
//Method to get the size
public int size(){
int size = 0;
Node node = head;
if(node !=null){
while (node !=null){
size++;
node = node.nextNode;
}
}
return size;
}
