双链接列表中间插入不起作用

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。

这可能会导致您在代码中发现错误。

删除这些额外的创建后，您应该只需切换prev和next指针，检查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

在双向链表中，您必须保持上下指针。在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