我正在使用Python学习数据结构和算法。我已经学到,链表的优点是它没有最大节点数的限制,不像其他语言中的数组。
1. 因为Python会为我们自动调整列表大小,所以这个优点已经被抽象化了。 2. 因此,我一直认为链表唯一的优势就是在链表前面或后面添加一个节点是O(1),而向列表添加元素可能会因为Python需要调整数组大小并复制每个元素而变成O(n)。
但是,我刚学到摊销时间复杂度是今天的一件事情,并且向列表附加元素的摊销时间复杂度为O(1)。因此,向列表添加元素实际上比添加节点到链表更快,因为添加节点到链表除链表前/后以外的任何位置都需要O(n)的时间复杂度。
那么,在使用数组/列表方面,使用链表有什么意义呢?
1. 因为Python会为我们自动调整列表大小,所以这个优点已经被抽象化了。 2. 因此,我一直认为链表唯一的优势就是在链表前面或后面添加一个节点是O(1),而向列表添加元素可能会因为Python需要调整数组大小并复制每个元素而变成O(n)。
但是,我刚学到摊销时间复杂度是今天的一件事情,并且向列表附加元素的摊销时间复杂度为O(1)。因此,向列表添加元素实际上比添加节点到链表更快,因为添加节点到链表除链表前/后以外的任何位置都需要O(n)的时间复杂度。
那么,在使用数组/列表方面,使用链表有什么意义呢?