Java 如何在链表中的给定位置插入项目？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20076364/
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
How to insert an item at a given position in a linked list?
提问by user2810123
This how you would add an item:
这是您添加项目的方式：
public void insert (Object item)
{
Link add = new Link();
add.data = item;
add.next = head;
_head = add;
++_listsize;
}
But how do you add an item at a given position. So far this is what I got:
但是如何在给定位置添加项目。到目前为止，这是我得到的：
public void insert (Object item, int pos)
{
Link add = new Link();
int ix = pos - 1;
add.next = _head;
for (int i = _listsize - 1; i >= ix; --i)
add = add.next;
add.data = item;
_head = add;
++_listsize;
}
This will insert the item correctly if it is sequential, but let say I am given a position which is in the middle, what it will do it will insert the item but it will completely cut off (or delete the rest). For example:
如果它是连续的，这将正确插入项目，但假设我得到了一个位于中间的位置，它将插入该项目但它会完全切断（或删除其余部分）。例如：
insert at 1: a
在 1 处插入：a
insert at 2: b a
在 2 处插入： b a
insert at 3: c b a
在 3 处插入： c b a
insert at 2: d a
在 2 处插入：d a
回答by Jérémy Dutheil
Use add( int index, E element), which insert the element at the specified index : http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html#add(int, E)
使用add( int index, E element)，在指定的索引处插入元素：http: //docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html#add(int, E)
EDIT : if you're using LinkedList, of course ; with your own class, you have to store prev/next pointers and simply update them (previous node next's pointer should point to the new element, and next node previous's pointer should point to the new element too)
编辑：当然，如果您使用的是 LinkedList；对于您自己的类，您必须存储 prev/next 指针并简单地更新它们（上一个节点 next 的指针应该指向新元素，下一个节点 previous 的指针也应该指向新元素）
回答by RouteMapper
You should do something like this:
你应该做这样的事情：
public void insert (Object item, int pos)
{
Link add = new Link();
int ix = pos - 1;
Link cur = _head;
for (int i = 0; i < _list_size; i++) {
if(i == ix) {
add.next = cur.next;
cur.next = add;
}
cur = cur.next;
}
++_listsize;
}
回答by lkamal
It seems you have not correctly inserted the new Linkinto the list. When you do that, you need to find the Linkat the given position as well as the Linkat the previous position. Then only you can set the previous.next = addand add.next = position.
看来您没有正确地将新Link插入到列表中。当你这样做时，你需要找到Link给定位置的 以及Link上一个位置的 。那么只有您可以设置previous.next = add和add.next = position。
Below is the updated method that does the task.
下面是执行任务的更新方法。
public void insert (Object item)
{
Link add = new Link();
add.data = item;
add.next = _head;
_head = add;
++_listsize;
}
public void insert (Object item, int pos)
{
Link add = new Link();
add.data = item;
int ix = pos - 1;
add.next = _head;
Link previous = _head;
for (int i = _listsize - 1; i > ix; --i) {
previous = previous.next;
}
Link position = previous.next;
previous.next = add;
add.next = position;
++_listsize;
}
回答by Mohit Jain
It is definetly possible. But what would matter most is deciding at which position to insert new element because after each insertion the list would change and position of new element coming will have to be decided appropriately. You can try this
这绝对是可能的。但最重要的是决定在哪个位置插入新元素，因为每次插入后列表都会改变，新元素到来的位置必须适当地决定。你可以试试这个
insertat=head;
for(i=0;i<pos;i++){
insertat=insertat.next;
}
add.next=insertat.next;
insertat.next=add;
listsize++;
回答by Luiggi Mendoza
You need a temporary variable that start from the head, traverse each node until the desired position or the end of the list, then insert the new node.
您需要一个从头开始的临时变量，遍历每个节点直到所需的位置或列表的末尾，然后插入新节点。
Since it is a homework exercise, I will only post pseudo code:
既然是作业练习，我就只贴伪代码：
if pos < 0
//define what to do here...
return
end if
if pos == 0
//inserting at the beginning
insert(item)
return
end if
Link temp <- head
int index <- 0
while index < pos and temp->next != null
temp <- temp->next
index <- index + 1
end while
//now you're at your desired location or at the end of the list
Link newLink <- new Link
newLink->data <- item
newLink->next <- temp->next
temp->next <- newLink
回答by Lucas Oliveira
After attempting alone the implementation of the concept, you can consider the open-source research. One of the best things you can do with open source is learn from it, study the implementation of java.util.LinkedList,
在单独尝试实现概念后，您可以考虑开源研究。你可以用开源做的最好的事情之一就是从中学习，研究 java.util.LinkedList 的实现，
following the logic of the method add (int index, E element) { http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#360}, you can divide in;
遵循方法的逻辑 add (int index, E element) { http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java #360}，可以分割；
1) Get where the element will be added, in your case "link" http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#380
1）获取元素的添加位置，在您的情况下为“链接” http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList。爪哇#380
2) and you can examine the code that links the elements following the logic "before adding" in the code snippet http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#794
2) 并且您可以检查在代码片段http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14中的“添加之前”逻辑之后链接元素的代码 /java/util/LinkedList.java#794
So, you will understand the logic behind the algorithm and will be able to perform your own implementation
因此，您将了解算法背后的逻辑，并能够执行您自己的实现
回答by user3597577
My solution is not as clean as it will be with recursion but if you are testing more than 50,000 elements on the list go with an iterative solution. or you can modify the JVM and change the stack size. Because you can get a stack overflow just because you will pass the capacity of activation records in the stack. Think about the worst case scenario that you will do an insert at the end of the list.
我的解决方案不像递归那样干净，但是如果您要测试列表中超过 50,000 个元素，请使用迭代解决方案。或者您可以修改 JVM 并更改堆栈大小。因为您可能会因为您将在堆栈中传递激活记录的容量而导致堆栈溢出。考虑最坏的情况，您将在列表末尾插入。
/**
* Inserts the specified element at the specified position in this list.
*
* @param :index the desire position starting from 0 2,3,4,5
* @param :data the content of the new node
* @return Boolean: if the insertion was successfully return true otherwise false
*/
public boolean add(int index, T data) {
/*Add to the end of the list*/
if (index == size()) {
add(data);
return true;
}
/*Empty list and index bigger than 0*/
else if (this.front == null && index != 0) {
return false;
} else {
Node<T> tempNode = this.front;
while (tempNode != null && tempNode.next != null && --index != 0) {
tempNode = tempNode.next;
}
if (index != 0) {
return false;
} else {
Node<T> newNode = new Node<T>(data);
/*Empty list,and index is 0*/
if (tempNode == null) {
this.front = newNode;
} else {
newNode.next = tempNode.next;
tempNode.next = newNode;
}
}
}
return true;
}
