数组和链表

数组

数组(Array)是一种线性表数据结构, 用一组连续的内存空间, 来存储一组具有相同类型的数据

• 最好时间复杂度为O(1), 最坏时间复杂度为O(n), 平均时间复杂度为O(n)

链表

通过指针将一组零散的内存块串联在一起, 内存块称为链表的结点

• 单链表, 结点上有后继指针next; 尾结点指向null

• 循环链表
• 双向链表
• 双向循环链表

链表vs数组性能