第003讲：线性表（数组和单链表）

小甲鱼

待更新

小古比鱼

最基本的数据结构是线性表，包括数组、链表、栈和队列。Python中的列表是一种灵活的数组，其访问和修改元素的时间复杂度是O(1)，插入和删除元素的时间复杂度是O(n)。然而，Python中既没有指针，也没有链表，我们只能自己定义链表类及其主要操作。在链表头部插入和删除元素的时间复杂度是O(1)，索引元素的时间复杂度是O(n)。由此可见，单链表和数组是“对着干”的关系。当然，特殊情况下（在头部或尾部）进行插入、删除操作的时间复杂度可能会有所不同，稍做分析即可明了。