在单向链表的任何位置递归添加节点是否可行？

Question

我了解到要在单向链表的前面添加一个节点，代码是

head = new Node(data,head);

我对这是否可行的逻辑感到困惑，例如，在列表中间的某个随机索引中。我尝试实现代码：

 public void add(int index, int data) {
        if(index == 0) {
            head = new Node(data,head);
        } else {
            for(int pos = 0; pos < size; pos++) {
                if(pos == index) {
                        //Add it//
                        head = new Node(data,head);
                        size++;
                    } else {
                        //Go to the next Node//
                        head = head.getNext();
                    }
                }
            }
        }
    }

我对这个逻辑还是有点疑惑，因为我觉得这样会导致添加完成后的链表丢失数据。因此，如果我添加例如索引 5，则 6、7、8、9 等将不再是链表的一部分。

Answer 1

要将一个节点添加到链表的开头，该行将起作用，假设您的构造函数中有这样的内容：

setNext(head);

这样您就不会忘记您的列表。如果您只是简单地重置头部而不设置对列表其余部分的引用，您将丢失它。

但是您的索引 5 示例不适用于此处。在那种情况下，您要将一个节点插入到链表的中间，而不是在开头，因此过程会有所不同。例如，如果你想在位置 5 插入一些东西，你必须将位置 4 的节点的下一个设置为你的新节点，并将你的新节点的下一个设置为当前位置 5 的节点。请参阅此以获得更详细的信息解释：http://www.mycstutorials.com/articles/data_structures/linkedlists

Answer 2

你应该更清楚单向链表是如何工作的。我建议您阅读一些好的文章或视频教程。而你在这里做的是 iteration，而不是 recursion.

A head 是 pointer/reference 到链接列表开头的节点。

那么，head 什么时候改变？

当您在 0th 处插入一个新节点时（假设您从 0 开始）或当您删除第一个节点时。

在所有其他情况下，head 保持不变。添加到链接列表的前面与添加 newNode where index=0 相同。在任何 index 处添加 newNode 的逻辑应该是相同的。但是，如果要添加到 0th 索引，您应该将 head 重置为 newNode.

您的代码似乎有缺陷。采取输入并尝试逐步进行。它可能会帮助您确定缺陷（如果有）。干杯。

在单向链表的任何位置递归添加节点是否可行？

Will adding a Node recursively work in any position of a Singly Linked List?

java

linked-list

data-structures