ОСУЩЕСТВЛЕНИЮ двусвязного списка в Python

Question

Я пытался реализовать дважды связанный список со следующими функциями:

_insertItemAfterNode(self,index) 

_nodeBeforeIndex(self, index) 



insertItemAtTheFront(self,item) 

insertItemAtTheEnd(self,item) 

insertItemAtIndex(self, index, item) 

Последние три функции должны использовать два первых частных методов. Это то, что у меня есть до сих пор, но я не могу работать. Любая помощь приветствуется !!!

# DoublyLinkedLists 

class Node(object): 

    def __init__(self, prev = None, data=None, next = None): 
     self._prev = prev 
     self._data = data 
     self._next = next 

    def __str__(self): 
     return str(self._data) 
    def __repr__(self): 
     return "Node(%s,%s,%s)" % (repr(self._prev), repr(self._data), repr (self._next)) 

    def __eq__(self, other): 
     if other == None: 
      return False 
     else: 
      return self._prev == other._prev and self._data == other._data and self._next == other._next`enter code here` 

class DoublyLinkedList(object): 

    def __init__(self): 
     self._first = Node(None, None, None) 
     self._length = 0 
     self._last = Node(None, None, None) 

    def __len__(self): 
     return self._length 

    def _insertItemAfterNode(self,item,aNode): 
     newNode = Node(aNode._prev, item, aNode._next) 
     aNode._next= newNode._prev 
     aNode._prev=newNode._next 
     self._length += 1 

    def _nodeBeforeIndex(self, index): 
     if 0 <= index <= self._length: 
      aNode = self._first 
      for i in range(index): 
       aNode = aNode._next 
      return aNode 
     else: 
      raise IndexError 

    def _nodeAfterIndex(self, index): 
     if 0<= index <= self.length: 
      aNode = self._last 
      for i in range(index): 
       aNode = aNode._prev 
      return aNode 
     else: 
      raise IndexError 

    def __getitem__(self, index): 
     return self._nodeBeforeIndex(index)._next._data 

    def insertAtEnd(self, item): 
     self._nodeAfterIndex(item)   

    def __iter__(self): 
     return DoublyLinkedListIterator(self) 

    def __setitem__(self, index, item): 
     self._nodeBeforeIndex(index)._next._data = item 

    def insertItemAtTheFront(self, item): 
     self._insertItemAfterNode(item, self._nodeBeforeIndex(0)) 

    def insertItemAtTheEnd(self, item): 
     self._insertItemAfterNode(item, self._nodeBeforeIndex(self._length)) 

    def insertItemAtIndex(self, index, item): 
     '''Valid range 0 <= index <= length.''' 
     self._insertItemAfterNode(item, self._nodeBeforeIndex(index)) 

    def __iter__(self): 
     return DoublyLinkedListIterator(self) 

    def __repr__(self): 
     #used by print in abscence of __str__ . 
     plist = [] 
     for item in self: 
      plist.append(item) 
     return "DoublyLinkedList(%s)" % str(plist) 

class DoublyLinkedListIterator(object): 

    def __init__(self, aList): 
     self._list = aList 
     self._currentIndex = -1 
     self._currentNode = self._list._first 

    def __iter__(self): 
     return self 

    def __next__(self): 
     if self._currentIndex == self._list._length - 1: 
      raise StopIteration 
     else: 
      self._currentIndex += 1 
      self._currentNode = self._currentNode._next 
      return self._currentNode._data 

def main(): 

    x = DoublyLinkedList() 

    x.insertItemAtTheEnd(45) 

    print(x) 

main() 

Answer 1

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

def _insertItemAfterNode(self,item,aNode): 
    newNode = Node(aNode._prev, item, aNode._next) 
    aNode._next= newNode._prev 
    aNode._prev=newNode._next 
    self._length += 1 

Предположим, что у вас есть:

prevNode <-> aNode <-> nextNode

Теперь создать newNode, который указывает на prevNode как его предыдущий и nextNode в последующей деятельности , Затем вы поворачиваете указатели на aNode. prevNode все еще думает, что его следующий узел aNode, но aNode теперь думает, что его следующий узел снова prevNode.

   /---------\ 
     /----> aNode < v 
prevNode <--------/ \-- nextNode 
    ^    ^
     \---- newNode --/ 

Который далеко не то, что вы хотите:

prevNode <-> aNode <-> newNode <-> nextNode 

Вот лучший вариант:

def _insertItemAfterNode(self,item,aNode): 
    # If the new Node follows aNode, than its preceeding node is aNode, 
    # not aNode._prev! 
    newNode = Node(aNode, item, aNode._next) 
    # Now we need to make aNode point at its new following Node, newNode 
    aNode._next = newNode 
    # And finally, we need to make the following Node notice that 
    # its preceeding Node has changed. 
    newNode._next._prev = newNode 
    self._length += 1 

Это не заботится о каких-либо крайних случаях, например, что делать, если aNode - последний узел в связанном списке.

Что я рекомендую, так это то, что вы вынимаете листок бумаги и рисуете, как нужно менять разные ссылки для каждой из операций, которые вам нужно выполнить, потому что это трудно сохранить в голове.

Убедитесь, что вы просматриваете все краевые кейсы, т.е. помещая в пустой список, помещая элемент в первую и последнюю позиции.

И, наконец, при перетасовке ссылок всегда проверяйте, где каждая ссылка указывает на каждую инструкцию, и чтобы случайно не удалять узлы.

Answer 2

Я вижу две проблемы с вашим кодом. Может быть больше проблем, которые я не заметил, но они, вероятно, помешают вам увидеть других, пока они не будут исправлены.

Первая проблема очень проста. У вас есть два дозорных узла: _first и _last в вашем классе DoublyLinkedList. Однако они не связаны друг с другом, поэтому, когда больше узлов добавляется позже, они не будут подключены к обоим сторонам, как они должны быть.

Вы можете это исправить, изменив метод __init__:

def __init__(self): 
    self._first = Node(None, None, None) 
    self._length = 0 
    self._last = Node(self._first, None, None) # pass first node as an arg here 
    self._first._next = self._last    # make a link back too 

Второй вопрос заключается в том, как вы добавляете узлы. Есть несколько мест, где вы назначаете значения из атрибутов или _next узла, а не ссылаетесь на сам узел.

Давайте рассмотрим список, содержащий A и C узлов, и вы хотите вставить B между ними. Вы должны сделать ссылку узла B как на A, так и на C, а затем изменить C и A для ссылки на него. В вашем коде A: aNode, B: newNode и C есть (в начале) aNode._next.

def _insertItemAfterNode(self, item, aNode): 
    newNode = Node(aNode, item, aNode._next)  # link B to A and C 
    aNode._next._prev = newNode     # link C back to B 
    aNode._next = newNode      # and A to B too! 
    self._length += 1