Средняя вставка двойного связанного списка не работает

Question

import math
class Node:
    def __init__(self, val, next = None, prev = None):
        self.data = val
        self.next = next
        self.prev = prev

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

    def StartInsert(self, val):
        newNode = Node(val)
        if self.count == 0:
            self.head = newNode
            self.tail = newNode
        else:
            self.head.prev = newNode
            newNode.next = self.head
            self.head = newNode
        self.count += 1

    def EndInsert(self, val):
        newNode = Node(val)
        if self.count == 0:
            self.head = newNode
            self.tail = newNode
        else:
            self.tail.next = newNode
            newNode.prev = self.tail
            self.tail = newNode
        self.count += 1

    def MiddleInsert(self, val):
        newNode = Node(val)
        if self.count == 0:
            self.head = newNode
            self.tail = newNode
        else:
            index = math.ceil(self.count/2)-1
            temp = self.head
            while index > 0:
                temp = temp.next
                index -= 1
            temp.next = Node(val, temp.next)
            temp.prev = Node(temp.prev.data, temp)
        self.count +=1


    def delete(self, val):
        curNode = self.head
        while curNode != None:
            if curNode.data == val:
                if curNode.prev != None:
                    curNode.prev.next = curNode.next
                else:
                    self.head = curNode.next

                if curNode.next != None:
                    curNode.next.prev = curNode.prev
                else:
                    self.tail = curNode.prev

                self.count -= 1

            curNode = curNode.next

    def reverse(self):
        temp = None
        current = self.head
        while current != None:
            temp = current.prev
            current.prev = current.next
            current.next = temp
            current = current.prev
        if temp:
            self.head = temp.prev
            self.tail = temp.next



    def traverse(self):
        s = ""
        p = self.head
        while p is not None:
            s += str(p.data) + ' ';
            p = p.next
        print(s + "| count: " + str(self.count))

list = LinkedList()
list.EndInsert("a")
list.StartInsert("b")
list.StartInsert("c")
list.EndInsert("d")
list.MiddleInsert("c")
list.traverse()

list.reverse()
list.traverse()

Средняя вставка дает правильный возврат, но не останавливается.Я сделал тот же метод для односвязного списка, но он не работает должным образом для двойного связанного списка.Он возвращает правильное значение, но продолжает зацикливаться на цикле while.

Я пытаюсь понять, как подключить newNode ().Пожалуйста, помогите мне, показывая код и причину, по которой я получаю такую ​​ошибку.

Большое спасибо за помощь.

Answer 1

Первоначальной ошибкой является то, что вы создаете больше Node, что обязательно в вашем MiddleInsert методе.

Это может привести к нахождению ошибки в вашем коде.

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

def MiddleInsert(self, val):
    newNode = Node(val)
    if self.count == 0:
        self.head = newNode
        self.tail = newNode
    else:
        index = math.ceil(self.count/2)-1
        temp = self.head
        while index > 0:
            temp = temp.next
            index -= 1
        newNode.next = temp.next
        temp.next = newNode
        newNode.prev = temp
        if newNode.next is not None:
            newNode.next.prev = newNode
    self.count +=1

Answer 2

В двусвязном списке вы должны поддерживать prev и next указатели .В MiddleInsert, как только вы выбрали элемент, после которого вы хотите добавить новый узел, вы должны вставить новый элемент между ним и его последователем.

Давайте назовем C новый узел,A выбранный узел и произнесите B=A.next.Перед вставкой у вас есть A.next == B и B.prev == A;после вставки вы хотите иметь A.next == C, C.prev == A, C.next == B и B.prev == C.

Просто напишите это в MiddleInsert (не связано, но здесь не нужен модуль math,и for ... in range(...) - это Pythonic способ подсчета циклов):

def MiddleInsert(self, val):
    newNode = Node(val)
    if self.count == 0:
        self.head = newNode
        self.tail = newNode
    elif self.count == 1:
        self.tail = newNode
        self.head.next = newNode
        newNode.prev = self.head
    else:
        index = (self.count-1) // 2
        temp = self.head
        for i in range(index):
            temp = temp.next
        temp.next.prev = newNode
        newNode.next = temp.next
        newNode.prev = temp
        temp.next = newNode
    self.count +=1