指向错误事物的双向链表中的指针

Question

我正在尝试将字符串转换为双向链表。我希望能够遍历它，找到一个匹配项，然后在某个位置插入另一个链表。但是，我的指针有问题。我有“current.prev”、“current”和“current.next”指针，它们都应该按顺序指向节点。相反，我的 .prev 和 current 指针总是指向同一事物。我需要能够指向链表的不同部分，否则我将无法遍历回某个位置插入新的链表。

这是为我创建双向链表的代码：

#-----------------------doubly-linked-lists-----------------------#
class NodeD:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None
    

class DoublyLL:
    def __init__(self):
        self.head = None
        
    def append(self, new_data):
        new_node = NodeD(new_data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last
        return
    
    def printList(self, node):
        while node:
            print(node.data, end=""),
            last = node
            node = node.next

这是将字符串变成链表的代码：

#making-linked-lists-from-strings#

def dnaToLL(dnainput):
    dnaLL = DoublyLL()
    head = NodeD(dnainput[0])
    dnaLL.head = head
    current = dnaLL.head
    for i in range(1, len(dnainput)):
        current.prev = current
        current = current.next
        current.next = NodeD(dnainput[i])
    return dnaLL

我一直在用它来测试指针指向的位置：

dnaLL = dnaToLL(DNA)
dnaLL = dnaLL.head
print(dnaLL.prev.data +dnaLL.data+dnaLL.next.data)

但使用此输入：

S1 = "neho"
DNA = "imfinehowru"

我得到这个输出：

iim

知道我哪里出错了吗？我假设这是我尝试将字符串制作成双向链表的地方，但是我将指针放入的任何其他顺序都会给我错误。

感谢您的帮助！

Answer 1

问题是，当您执行 current.prev = current 时，您说的是“前一个节点是当前节点”——而不是实际前一个节点。

请记住，列表中的第一个节点应该具有.prev = None。您只想为以后的节点设置 .prev。此修改应修复您的 dnaToLL() 函数：

def dnaToLL(dnainput):
    dnaLL = DoublyLL()
    head = NodeD(dnainput[0])
    dnaLL.head = head
    current = dnaLL.head
    for i in range(1, len(dnainput)):
        # note how the order is changed
        current.next = NodeD(dnainput[i])
        current.next.prev = current
        current = current.next
    return dnaLL

指向错误事物的双向链表中的指针

Pointer in doubly linked list pointing at the wrong thing

python

linked-list

doubly-linked-list