Python实现有序列表

有序列表

有序列表中元素是按照从小到大顺序排列的。当我们考虑有序列表时，我们应该可以注意到isEmpty和size方法的实现和无序列表相同，因为它们只处理列表中节点的数量而不考虑节点的实际值。需要改变的是index，remove，search和add，因为有序列表的有序性，当我们搜索到的节点值大于target时，即表示当前值不存在。

有序列表操作

orderedList()
add()
remove()
search()
isEmpty()
size()
index(item)
pop()
pop(pos)

python实现有序列表

# python实现有序列表

# Node 类
class Node():
    def __init__(self, element):
        self.data = element
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self, newelement):
        self.data = newelement

    def setNext(self, newnext):
        self.next = newnext

# 无序列表类
class orderedList():
    # unorderedList要保持对列表头一个节点的引用
    def __init__(self):
        self.head = None
    # 判断链表是否为空，即列表头是否指向None
    def isEmpty(self):
        return self.head == None
    # 添加add()方法
    def add(self, item):
        previous = None
        current = self.head
        stop = False
        while current != None and not stop:
            if current.getData() > item:
                stop = True
            else:
                previous = current
                current = current.getNext()
        newNode = Node(item)
        if previous == None:
            newNode.setNext(self.head)
            self.head = newNode
        else:
            newNode.setNext(current)
            previous.setNext(newNode)


    # 添加size()方法，此过程需要遍历链表
    def size(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.getNext()
        return count

    # 添加search方法
    def search(self, item):
        current = self.head
        found = False
        stop = False
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
            else:
                if current.getData() > item:
                    stop = True
                else:
                    current = current.getNext()
        return found

    # 添加remove()方法
    def remove(self, item):
        if not self.search(item):
            return "The unorderedList don't contain this item!"
        previous = None
        current = self.head
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        # 要删除的节点为第一个节点
        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())


    # 添加index()方法
    def index(self, item):
        current = self.head
        count = -1
        while current != None:
            count += 1
            if current.getData() == item:
                return count
            current = current.getNext()
        return None

    # 添加pop()方法
    def pop(self):
        previous = None
        current = self.head
        while current != None:
            previous = current
            current = current.getNext()
        previous.setNext(None)
        return previous.data

    # 添加insert()方法
    def insert(self, pos, item):
        newNode = Node(item)
        previous = None
        current = self.head
        for i in range(pos):
            previous = current
            current = current.getNext()

        # in case of pos = 0
        if previous == None:
            newNode.setNext(self.head)
            self.head = newNode
        else:
            previous.setNext(newNode)
            newNode.setNext(current)

    # traverse the unorderedList
    def println(self):
        current = self.head
        lists = []
        while current != None:
            lists.append(current.data)
            current = current.getNext()
        print(lists)

链表的分析：
当分析链表方法的复杂度时，我们应该考虑它们是否需要遍历链表。考虑一个有 n 个节点的链表，isEmpty 方法复杂度是 O（1），因为它只需要检查链表的头指针是否为 None。对于方法 size，则总需要 n 个步骤，因为除了遍历整个链表以外，没有办法知道链表的节点数。因此，size 方法的复杂度是 O（n）。无序列表的 add 方法的复杂度是 O（1），因为我们永远只需要在链表的头部简单地添加一个新的节点。但是，search、remove 和在有序列表中的 add 方法，需要遍历。尽管在平均情况下，它们可能只需要遍历一半的节点，但这些方法的复杂度都是 O(n)，因为在最糟糕的情况下需要遍历整个链表。
你可能还注意到，这些方法的实现性能与 Python 的内置列表 list 不同，这表明 Python 中的 list 不是这么实现的。实际上，Python 中的列表的实现是基于数组的。

文章目录

有序列表操作