在链表中的指定索引处插入节点

发布于 01-20 12:08 字数 822 浏览 1 评论 0原文

我正在编写链接列表的代码,当我想在指定位置插入新节点时,我很困惑。我想知道为什么我们将位置减少1?这是代码:

def insert(self, data, index):
        """
        Inserts a new Node containing data at index position
        Insertion takes O(1) time but finding the node at the 
        insertion point takes O(n) time. 
        """
        if index == 0:
            self.add(data)
        
        if index > 0:
            new = Node(data)
            
            position = index
            current = self.head
            current.next_node
            
            while position > 1:
                current = new.next_node
                position -= 1
                
            prev_node = current
            next_node = current.next_node
            
            prev_node.next_node = new
            new.next_node = next_node

I'm writing the code for Linked Lists and I'm confused when I want to insert a new node at the specified position. I'm wondering why we decrease the position by 1? Here is the code:

def insert(self, data, index):
        """
        Inserts a new Node containing data at index position
        Insertion takes O(1) time but finding the node at the 
        insertion point takes O(n) time. 
        """
        if index == 0:
            self.add(data)
        
        if index > 0:
            new = Node(data)
            
            position = index
            current = self.head
            current.next_node
            
            while position > 1:
                current = new.next_node
                position -= 1
                
            prev_node = current
            next_node = current.next_node
            
            prev_node.next_node = new
            new.next_node = next_node

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

在你怀里撒娇2025-01-27 12:08:19

您这样做的原因是您尝试移动当前
您如何做这没关系,无论您是将位置降低一个,做一个不同的循环还是做完全不同的事情 - 只要您做current = New.ne.ne.next_node 索引时间。

这正是这样做

while position > 1:
    current = new.next_node
    position -= 1

的。它运行该语句index次,因为position = index要开始。替代方案是

for _ in range(index):
    current = new.next_node

,它很可能应该是current = current.next_node,而不是current = new.ne.next_node,因为new永远不会更新。

The reason you do it is that you try to move the current forward index elements.
How you do that does not matter, whether you decrease the position by one, do a different loop or do something entirely different - as long as you do current = new.next_node index times.

And that is exactly what

while position > 1:
    current = new.next_node
    position -= 1

does. It runs that statement index times since position = index to begin with. An alternative would be

for _ in range(index):
    current = new.next_node

Note that it most likely should be current = current.next_node, not current = new.next_node, since new never gets updated.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文