Java 链表。头尾参考
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/21940032/
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
Linked Lists. Head and Tail References
提问by Bob
Im trying to make an Add and Delete method to my linked list class. I made 2 references with the names Head and Tail.
我试图为我的链表类创建一个添加和删除方法。我用 Head 和 Tail 的名字做了 2 个参考。
Head -> 1 -> 2 -> 3 -> Tail:null
头部 -> 1 -> 2 -> 3 -> 尾部：空
I keep getting problems when I try and delete specific nodes because Java says I'm out of bounds. I think it is because my Head isn't pointing to the first Node? What do you guys think? Or am i going about this the total wrong way...
当我尝试删除特定节点时，我不断遇到问题，因为 Java 说我越界了。我认为这是因为我的 Head 没有指向第一个节点？你们有什么感想？或者我是否以完全错误的方式解决这个问题......
public class LinkedList{
private Node head;
private Node tail;
private int listCount;
public LinkedList()
{
head = new ListNode(null);
tail = new ListNode(null);
listCount = 0;
}
public void add(Object elem){
ListNode newNode = new ListNode(elem);
if (size() == 0){
newNode = head;
tail = head;
}
newNode.setLink(tail);
tail = newNode;
listCount++;
}
public Object delete(int index)
// post: removes the element at the specified position in this list.
{
// if the index is out of range, exit
if(index < 1 || index > size())
throw new IndexOutOfBoundsException();
ListNode current = head;
for(int i = 1; i < index; i++)
{
if(current.getLink() == null)
throw new IndexOutOfBoundsException();
current = current.getLink();
}
current.setLink(current.getLink().getLink());
listCount--; // decrement the number of elements variable
return current.getInfo();
}
public int size() {
return listCount;
}
}
public class Node {
private Node link;
private Object info;
public Node(Object info)
{
this.info = info;
link = null;
}
public void setInfo(Object info)
{
this.info = info;
}
public Object getInfo()
{
return info;
}
public void setLink(Node link)
{
this.link = link;
}
public Node getLink()
{
return link;
}
}
回答by ErstwhileIII
Looks like you did not initialize the link from head to tail when you set up your initial (empty) linked list.
看起来您在设置初始（空）链表时没有初始化从头到尾的链接。
Ok. Here is a strategy to use when working with singly linked lists (forward link only). You need to determine what actions will be allowed on the list (e.g. add/remove from head or tail only?; or add and remove nodes anywhere in the linked list (bringing the list back together once you have cut a node out). If you will be allowing nodes to be deleted from anywhere, then you will need to have a way of UNIQUELY identifying each node (so you can unambiguously determine the node that will be deleted). You may also want to be able to add a node before or after some other node . and uniqueness may be needed for that. If you do NOT care which value you delete or add before/after then you can relax the uniqueness constraint.
好的。这是使用单链表（仅限前向链接）时使用的策略。您需要确定允许在列表上进行哪些操作（例如，仅从头或尾添加/删除？；或在链表中的任何位置添加和删除节点（一旦删除节点，将列表重新组合在一起）。如果您将允许从任何地方删除节点，然后您需要有一种唯一标识每个节点的方法（以便您可以明确确定将被删除的节点）。您可能还希望能够在之前添加一个节点或在其他一些节点之后。并且可能需要唯一性。如果您不关心在之前/之后删除或添加哪个值，那么您可以放宽唯一性约束。
Now for strategy to implement. Start with a head (initially null).
现在是实施战略。从头开始（最初为空）。
- To add a node, walk down your linked list until you find a null next link. Replace that with your node, and have your nodes forward link set to null. (Efficiency improvement, have a tail that always has the last node in the linked list, or null if there is nothing in the list).
- To delete a node, walk your list until you find the node you want to delete, change the previous link to the link in the node to be deleted (you are now done)
- To add a node at the endof the list, go to the link pointed to by tail (if null, list is emplty); change its link to your node, ensure your new node has a null in its link; and set the tail to your node
- To count sizeof linked list, either walk your tree and count (or, for computational efficiency, keep a running size that is incremented or decremented when you add or delete a node.
- 要添加节点，请沿着链表向下走，直到找到空的下一个链接。将其替换为您的节点，并将您的节点转发链接设置为空。（效率提升，有一个尾部总是有链表中的最后一个节点，如果链表中什么都没有，则为null）。
- 要删除节点，请遍历您的列表，直到找到要删除的节点，将之前的链接更改为要删除的节点中的链接（现在已完成）
- 要在链表末尾添加节点，转到tail指向的链接（如果为null，则链表为空）；将其链接更改为您的节点，确保您的新节点在其链接中为空；并将尾部设置为您的节点
- 要计算链表的大小，请遍历树并进行计数（或者，为了计算效率，在添加或删除节点时保持递增或递减的运行大小。
Does this help?
这有帮助吗？
Look at this link for a full description!
查看此链接以获取完整说明！
回答by Embattled Swag
I think it's because your headnever links to anything. What I would do to fix it is in your add method, check the sizeof your list; if it's 0, set the head to the new element and set the tailequal to the head. If it's 1, link the headto the new node and set tail. If it's 2, just set the tail's link to the new node and set the tail(like you have now).
我认为这是因为你head从来没有链接到任何东西。我会在你的 add 方法中修复它，检查size你的列表；如果为 0，则将 head 设置为新元素并将tail等于head. 如果为 1，则将 链接head到新节点并设置tail。如果是 2，只需将tail的链接设置为新节点并设置tail（就像您现在所做的那样）。
Also, I'm not sure how you implemented it, but newNode.setLink(tail);seems wrong...the tailshould be linked to newNode. From the way it looks, it seems like you're trying to do newNode -> tail
另外，我不确定你是如何实现它的，但newNode.setLink(tail);似乎是错误的......tail应该链接到newNode. 从它的外观来看，您似乎正在尝试执行 newNode -> tail
EDIT: Ok, here is why I would try
编辑：好的，这就是我尝试的原因
public void add(Object elem){
ListNode newNode = new ListNode(elem);
if (size() == 0){
newNode = head;
tail = head;
}else if(size() == 1){
head.setLink(newNode);
tail = newNode;
}else{
tail.setLink(newNode);
tail = newNode;
}
listCount++;
}
