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

Question

该作业要求我们为无序列表实现 append、insert、index 和 pop 方法。（到目前为止我所拥有的）

    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等），或删除它们（remove，pop，等）。所以它应该是这样的：

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)