Проблемы обращения дважды связанного списка

Я должен отменить дважды связанный список (DLL) между двумя узлами. Я сделал это с одиночно связанных списков( SLL), но я считаю, что это труднее сделать с DLL? Это может быть необходимость делать это между двумя определенными узлами.
Вот код для my DLLNode & DLL. Когда я тестирую этот код, он, кажется, ничего не делает с моей DLL. Есть советы о том, что я делаю неправильно??

EDIT: So i’M inputting a linked list ‘a’,’b’,’c’,’d’,’e’,’ f’and call twist (‘b’,’ e’): This should result in the linked list’ a » b » e ‘ d » c ‘f’

class DoublyLinkedListNode:
def __init__(self, item, prevnode = None, nextnode = None):
    self._data = item
    self.setnext(nextnode)
    self.setprev(prevnode)

def data(self):
    return self._data

def next(self):
    return self._next

def prev(self):
    return self._prev

def setprev(self, prevnode):
    self._prev = prevnode

def setnext(self, nextnode):
    self._next = nextnode

class DoublyLinkedList:
def __init__(self):
    self._head = None
    self._tail = None
    self._length = 0

def _newnode(self, item, nextnode = None, prevnode = None):
    return DoublyLinkedListNode(item, nextnode, prevnode)

def addfirst(self, item):
    if self.isempty():
        return self._addtoempty(item)
    node = self._newnode(item, None, self._head)
    self._head.setprev(node)
    self._head = node
    self._length += 1

def addlast(self, item):
    if self.isempty():
        return self._addtoempty(item)
    node = self._newnode(item, self._tail, None)
    self._tail.setnext(node)
    self._tail = node
    self._length += 1

def _addtoempty(self, item):
    node = self._newnode(item, None, None)
    self._head = self._tail = node
    self._length = 1

def removefirst(self):
    if len(self) <= 1:
        return self._removelastitem()
    data = self._head.data()
    self._head = self._head.next()
    self._head.setprev(None)
    self._length -= 1
    return data

def removelast(self):
    if len(self) <= 1:
        return self._removelastitem()
    data = self._tail.data()
    self._tail = self._tail.prev()
    self._tail.setnext(None)
    self._length -= 1
    return data

def _removelastitem(self):
    if self.isempty():
        return None # Should probably raise an error.
    data = self._head.data()
    self._head = self._tail = None
    self._length = 0
    return data

def twist(self, endpt1, endpt2):
    current = self._head
    while current != None:
        if current.data() == endpt1:
            current.next().setnext(endpt2.next())
            endpt2.setnext(current.next())
            current.setnext(endpt2)
        else:
            current = current.next()

def isempty(self):
    return len(self) == 0

def _nodes(self):
    node = self._head
    while node is not None:
        yield node
        node = node.next()

def __iter__(self):
    for node in self._nodes():
        yield node.data()

def __len__(self):
    return self._length

def __str__(self):
    items = [str(data) for data in self]
    return ", ".join(items)

Вот тест, который я запускаю:

    def testtwist1(self):
        n = [0,1,2,3,4,5]
        L = DoublyLinkedList()
        for i in n:
            L.addlast(i)
        L.twist(2,5)
        print(L)   # returns the list 0,1,2,3,4,5

1 ответ

  1. Я вообще не вижу, как это происходит. Очевидно, вы настроили DLL, а затем вызвали DLL.twist (‘b’,’ e’). Таким образом, endpt1 = ‘b’ и endpt2 = ‘e’. Затем вы сравниваете endpt1 с current.данные, но затем вы получаете доступ к endpt2.следующий. endpt2-это строка из одного символа .

    Вы никогда не ссылаетесь на указатели prev вообще.

    Единственный раз, когда вы пытаетесь что-то изменить, это когда вы нажимаете узел b . Затем вы, кажется, пытаетесь обменять следующие указатели b и e (so b.далее f и e.далее идет c, но это все.

    На этом этапе я ожидаю, что ваши прямые ссылки дают вам два списка: a->b->>f и c->>>d->>>>e->>>>> > > c (цикл), и что обратные ссылки неизменны.

    Возьмите карандаш и бумагу или белую доску и пройдите через эти изменения, одно утверждение за раз; это то, что я делаю …


    Я восстановил твист с вашего предыдущего поста, исправил отступ и побежал. Как я объясню выше, это ошибки в исполнении:

    Traceback (most recent call last):
      File "so.py", line 113, in <module>
        L.twist(2,5)
      File "so.py", line 102, in twist
        current.next().setnext(endpt2.next())
    AttributeError: 'int' object has no attribute 'next'
    

    Нет такой вещи, как 2.next (). Я не думаю, что вы на самом деле добираетесь до своего печатного заявления. Кроме того, print(L) не будет печатать значения узлов по порядку; вы не включили метод __repr__ для вашего объекта DLL. _ _ str _ _ сделал бы работу, но вы использовали указатель на головку списка, как если бы он был итерацией по прямолинейному связанному списку.

    Я настоятельно рекомендую вам создать резервную копию и подойти к этому с помощью инкрементального программирования: напишите метод или несколько строк, проверьте это и не продолжайте, пока это не сработает так, как вы ожидаете. Да, это означает, что вы пишете подробные тесты, когда вы идете … это хорошо. Держите их, и продолжайте управлять ими.