为什么我的双向链表节点的一个变体会交换,而另一个几乎相同的变体不会在相邻节点上交换?

问题描述 投票:0回答:0

我正在用 Python 练习链接数据结构。我正在研究的一个问题是一种在不移动数据的情况下交换双向链表中的两个节点的方法。所以没有 node1._data=node2._data 或类似的东西。我必须弄乱下一个和上一个指针。它是作为双向链表类的一部分的方法。该方法特别采用指向节点的指针作为参数。不是它必须在列表中搜索的值。它旨在用于发生交换的排序。

我有两个版本。第一个工作完美,而第二个有问题。不同之处在于恰好放置了一行。它们在其他方面是相同的。工作代码如下:

def _swap(self, node1, node2):
        assert l is not None and r is not None, "nodes to swap cannot be None"
        
        #Handle cases where nodes are front or rear
        if node1==self._front:
            self._front=node2
        elif node2==self._front:
            self._front=node1
            
        if node1==self._rear:
            self._rear=node2
        elif node2==self._rear:
            self._rear=node1


        #Swap pointers
        node1._next, node2._next = node2._next, node1._next
        
        
        if node1._next is not None:
            node1._next._prev=node1
        if node2._next is not None:
            node2._next._prev=node2
            
        node1._prev, node2._prev = node2._prev, node1._prev
        
        if node1._prev is not None:
            node1._prev._next=node1
        if node2._prev is not None:
            node2._prev._next=node2
            
        return

非工作代码几乎完全相同,但如果有问题的两个节点彼此直接相邻,则会失败。区别在于交换指针部分。前一个指针的交换与下一个指针的交换一起更改。像这样

 #Swap pointers
        node1._next, node2._next = node2._next, node1._next
        node1._prev, node2._prev = node2._prev, node1._prev
        
        
        if node1._next is not None:
            node1._next._prev=node1
        if node2._next is not None:
            node2._next._prev=node2
            
        
        if node1._prev is not None:
            node1._prev._next=node1
        if node2._prev is not None:
            node2._prev._next=node2
            
        return

线条完全相同,但放置了几行。为什么这会影响相邻节点的交换?为什么在处理非相邻节点时可以正常工作?这是我现在只想到的直觉,但这是否与以下事实有关:当节点相邻并且您交换指针时,您最终会得到指向它们自己的东西?

当我第一次开始尝试解决这个问题时,我使用了导致头痛的第二个不正确的实现。移动那条线后它工作得很好但我不知道为什么它这么重要。

python swap doubly-linked-list
© www.soinside.com 2019 - 2024. All rights reserved.