Python 链表追加

Question

我为UnorderedList（）类制作了一个附加方法，该方法在我的IDLE窗口中工作正常，但是当它分配给大学的测试时：

my_list = UnorderedList()
my_list.append(13)
for num in my_list: 
    print(num, end=" ")
print()    

它返回一个错误：AttributeError: Nonetype object has no attribute 'getNext' 。

下面是追加方法：

def append(self,item):
    current = self.head
    while current.getNext() != None:
        current = current.getNext()
    current.setNext(Node(item))

这是我的其余类和代码：

class Node:
    def __init__(self,initdata):
        self.data = initdata
        self.next = None
    def getData(self):
        return self.data
    def getNext(self):
        return self.next
    def setData(self,newdata):
        self.data = newdata
    def setNext(self,newnext):
        self.next = newnext
class UnorderedList:
    def __init__(self):
        self.head = None
        self.count = 0
    def append(self,item):
        current = self.head
        while current.getNext() != None:
            current = current.getNext()
        current.setNext(Node(item))

为什么测试返回该错误以及如何修复我的追加方法？

Answer 1

问题出在追加方法中：

def append(self,item):
    current = self.head
    while current.getNext() != None:
        current = current.getNext()
    current.setNext(Node(item))

在第一次迭代中，current 的值为 self.head ，最初设置为 None，您不检查它。

因此，请改为更改此设置，并在下面引入针对此条件广告的检查：

def append(self,item):
    current = self.head
    if current:
        while current.getNext() != None:
            current = current.getNext()
        current.setNext(Node(item))
    else:
        self.head = Node(item)

PS：您还在使用 变量self.count ，您没有更新。您可能还想更新相同的内容。

Answer 2

您的追加方法工作正常，但它遍历列表直到找到最后一个节点 - 这使它成为 O（n）。如果你跟踪最后一个节点，你可以做一个附加，即 O（1）：

def append_O1(self, item):
        temp = Node(item)
        last = self.tail
        last.setnext(temp)
        self.tail = temp
        self.length += 1

要启用此功能，您的列表类构造函数应为：

class unorderedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

Answer 3

添加更多精细的追加方法

在开头插入的方法

def inserAtBeginning(self, item):
    newNode = Node(item)
    newNode.setdata(item)
    if self.listLength() == 0:
        self.head = newNode
    else:
        newNode.setnext(self.head)
        self.head = newNode

在末尾插入的方法

def insertAtEnd(self, item):
    newNode = Node(item)
    newNode.setdata(item)
    current = self.head
    while current.getnext() != None:
        current = current.getnext()
    current.setnext(newNode)

在指定位置插入的方法

def insertAtPos(self, pos, item):
    if pos > self.listLength() or pos < 0:
        return None
    if pos == 0:
        self.inserAtBeginning(item)
    else:
        if pos == self.listLength():
            self.insertAtEnd(item)
        else:
            newNode = Node(item)
            newNode.setdata(item)
            current = self.head
            count = 0
            while count < pos - 1:
                count += 1
                current = current.getnext()
            newNode.setnext(current.getnext())
            current.setnext(newNode)

Answer 4

这个 O（n） 实现也应该适用于空列表：

def append(self,item):
    current = self.head
    if current == None:
        self.head = Node(item)
    else:
        while current.getNext() != None:
            current = current.getNext()
        current.setNext(Node(item))