python - 头尾指针是否足以使我的附加方法在链表中保持恒定时间？

Question

我正在 Python 上从头开始实现一个链表。我已经实施了。特别是，我对 append 方法的不同实现感兴趣。按照我正在使用的书中的说明，在实现append为线性时间函数之后，我现在尝试在恒定时间内实现它。

我首先创建一个Node类来帮助创建我的链表：

class Node:
    """
    A node class that is used to implement a linked list object.
    The node contains a data field, aka the item in the node and a
    reference to the next node.
    """
    def __init__(self, init_data):
        self.data = init_data
        self.next = None

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next

    def set_data(self, new_data):
        self.data = new_data

    def set_next(self, new_next):
        self.next= new_next

这是我使用不同方法实现的链表：

from node_class import Node

class UnorderedList:
    """
    An unordered list class built from a collection of nodes.
    """
    
    def __init__(self):
        self.head = None
        
    def is_empty(self):
        return self.head == None
    
    def add(self, item):
        temp = Node(item)
        temp.set_next(self.head)
        self.head = temp
        

    def size(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.get_next()

        return count

    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
            if current.get_data() == item:
                found = True
            else:
                current = current.get_next()

        return found


    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.get_data() == item:
                found = True
            else:
                previous = current
                current = current.get_next()

        if previous == None:
            self.head = current.get_next()
        else:
            previous.set_next(current.get_next())

    def print_list(self):
        current = self.head
        while current != None:
            print(current.data)
            current = current.get_next()

    def append(self, item):
        new_node = Node(item)

##      Append Linear Time O(n)
        if self.head == None:
            self.head = new_node
            return 
            
        current = self.head
        found_last = False
        while not found_last:
            if current.get_next() == None:
                found_last = True
                current.set_next(new_node)
                
            else:
                current = current.get_next()

我知道我的附加实现是线性时间，因为它必须遍历列表的长度才能找到最后一个节点，以便它可以将我的新节点附加到它。

我遵循的实现我的恒定时间解决方案的逻辑是首先添加一个名为 tail 的实例变量，这样我就可以将它指向最后一个节点（从而绕过遍历整个列表以找到最后一个节点的需要）。我正在考虑我的列表可能只有一项长的特殊情况。

直观地说，这应该可以工作，就像我提到的那样，我不需要遍历整个列表来查找最后一项，我可以简单地将尾巴的下一个节点设置为我想要附加的新节点。我的问题是，是否有任何情况下这不起作用？

我添加了我的 add 方法的修改版本，因为它是添加节点的另一种方式，如果我想保持我的 append 方法恒定时间，我也需要跟踪最后一个节点。

class UnorderedList:
    """
    An unordered list class built from a collection of nodes.
    """
    
    def __init__(self):
        self.head = None
        self.tail = None
    
    def add(self, item):
        temp = Node(item)
        temp.set_next(self.head)
        if self.head == None:
            self.tail = temp
        self.head = temp
        

    def append(self, item):
        new_node = Node(item)
##      Append Constant Time O(1)

        if self.head == None:
            self.tail = new_node
            self.head = new_node
            return
        else:
            self.tail.set_next(new_node)
            return

标签： pythonpython-3.xlinked-listappendbig-o