链表或列表的数组实现的优缺点
本文关键字：实现 优缺点 数组 链表 列表 | 更新日期: 2023-09-27 18:34:06
列表
的链表实现与基于数组的数组实现相比有什么优势？
对于初学者来说，我知道 linked-list 比数组占用更多的空间，因为它必须使用额外的 4 字节空间来保存对下一个节点的引用，而数组不必这样做。所以阵列使用更少的空间。
与数组实现相比，链表实现的优势在于数组在初始化时具有固定的大小，您必须编写代码来增加数组的大小，因此与链表实现相比，这可能是一个缺点。
对其他有利劣势有什么想法吗？
对于数组，如果你有索引（常量时间复杂度O（1）），你可以访问任何元素。但是对于列表，您必须逐个迭代才能访问，尽管您有索引（时间复杂度 O（n））
对于列表，插入和删除元素需要恒定时间 （O（1））。但是对于数组，插入和删除需要 O（n） 时间。
对于排序，列表实现优于数组实现。