python - Python 中的链表 - Append、Index、Insert 和 Pop 函数。不确定代码/错误

Question

这个作业要求我们为无序链表实现追加、插入、索引和弹出方法。(到目前为止我所拥有的)

    def main():
class Node:
    def __init__(self, data):
        self.data = data
        self.next_node = None

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

    def AppendNode(self, data):
        new_node = Node(data)

        if self.head == None:
            self.head = new_node

        if self.tail != None:
            self.tail.next = new_node

        self.tail = new_node
    def PrintList( self ):
        node = self.head

        while node != None:
            print (node.data)
            node = node.next

    def PopNode( self, index ):
        prev = None
        node = self.head
        i = 0

        while ( node != None ) and ( i < index ):
            prev = node
            node = node.next
            i += 1

        if prev == None:
            self.head = node.next
        else:
            prev.next = node.next

list = LinkedList()
list.AppendNode(1)
list.AppendNode(2)
list.AppendNode(3)
list.AppendNode(4)
list.PopNode(0)
list.PrintList( )

到目前为止的输出:

    2
    3
    4
    Traceback (most recent call last):
      File "<pyshell#32>", line 1, in <module>
        main()
      File "<pyshell#31>", line 50, in main
        list.PrintList( )
      File "<pyshell#31>", line 27, in PrintList
        node = node.next
    AttributeError: 'Node' object has no attribute 'next'

我不确定为什么会出现错误，因为代码在技术上是可行的。此外，插入和索引函数的任何输入将不胜感激。

Answer 1

对于 insert 和 index 方法，您将需要另一个 Node 属性，因为您需要跟踪哪个项目在什么上位置。我们称它为 position。您的 Node 类现在如下所示:

class Node:
    def __init__(self, data, position = 0):
        self.data = data
        self.next_node = None
        self.position = position

现在检索索引值很容易:

def index(self,item):
    current = self.head
    while current != None:
        if current.data == item:
            return current.position
        else:
            current = current.next
    print ("item not present in list")

至于改变列表的方法，我将从一个简单的 add 方法开始，该方法将项目添加到列表中的最左边位置:

def add(self,item):
        temp = Node(item)           #create a new node with the `item` value
        temp.next = self.head     #putting this new node as the first (leftmost) item in a list is a two-step process. First step is to point the new node to the old first (lefmost) value
        self.head = temp            #and second is to set `LinkedList` `head` attribute to point at the new node. Done!
        current = self.head         #now we need to correct position values of all items. We start by assigning `current` to the head of the list
        self.index_correct(current) #and we'll write helper `index_correct` method to do the actual work.
        current = self.head
        previous = None
        while current.position != self.size() - 1:
             previous = current
             current = current.next
             current.back = previous
        self.tail = current

index_correct 方法应该做什么？只有一件事 - 当我们添加新项目(例如:add、insert 等)或删除它们时，遍历列表以更正项目的索引位置(删除、弹出 等)。所以它应该是这样的:

def index_correct(self, value):
    position = 0
    while value != None:
        value.position = position
        position += 1
        value = value.next

很简单。现在，让我们按照您的要求实现 insert 方法:

def insert(self,item,position):
    if position == 0:
        self.add(item)
    elif position > self.size():
        print("position index out of range")
    elif position == self.size():
        self.AppendNode(item)
    else:
        temp = Node(item, position)
        current = self.head
        previous = None
        while current.position != position:
            previous = current
            current = current.next
        previous.next = temp
        temp.next = current
        temp.back = previous
        current.back = temp
        current = self.head
        self.index_correct(current)