在Python中创建n长度链表的更快方法

Question

我正试图使用Python创建一个长度为n的链表。我实现了简单的列表，一个可工作的串联函数和一个可操作的create_list函数；然而，我只想知道是否有比使用我的concatenate函数（用于测试）更有效的方法来制作链表。

简单列表类：

class Cell:
    def __init__( self, data, next = None ):
        self.data = data
        self.next = next

连接函数：

def list_concat(A, B):
    current = A
    while current.next != None:
        current = current.next
    current.next = B
    return A

列表创建（这需要很长时间！）：

def create_list(n):
    a = cell.Cell(0)
    for i in (range(1,n)):
        b = cell.Cell(i)
        new_list = cell.list_concat(a, b)   
    return new_list

Answer 1

改进代码的最简单方法是：

def create_list(n):
    new_list = cell.Cell(0)
    last_a = new_list
    for i in (range(1,n)):
        a = cell.Cell(i)
        cell.list_concat(last_a, a)
        last_a = a
    return new_list

这将使该方法的复杂性从O（n**2）降低到O（n）。