从理论的角度来看，有序列表和数组之间有什么区别？

有没有区别，或者它们是同一事物的两个术语？从理论的角度来看，有序列表和数组之间有什么区别？

2012-01-29 Nick

它与HTML有什么关系？ – doc 2016-08-14 20:38:29

虽然数组和列表之间有一些相似之处，但它们被用于不同的目的。

数组是连续的内存段，而列表只是一堆节点，每个节点都有指向“下一个”节点的指针（在双向列表的情况下也指向“上一个”节点）。 O（1） - 支持随机访问（即通过任意给定的索引i），但删除/插入元素到数组中很慢 - O（n），因为必须在所有元素之后移动所有元素删除/插入元素。另一方面，列表不支持有效的随机访问（同时支持高效的连续遍历），但插入和删除操作快 - O（1）。

看这张图片： enter image description here ：和this link为了更好的解释。

来源

2012-01-29 07:31:24

数组中的项不一定是任何特定的顺序。

通常，可以更快速地将项目添加到列表中的特定点，而不是在等效点添加新项目。（在数组中，您必须对其他条目进行混洗;在列表中，只需调整最多3个元素中的适当指针即可）。类似地，用于从列表和数组中删除元素。

访问N ^th列表中的项需要O（N）时间，但是O（1）时间是一个数组。

来源

2012-01-29 07:15:53

所以数组是一个基于硬件（或实现）的概念，而有序列表是一种抽象数据类型？ – Nick 2012-01-29 07:20:12

链接列表也是基于实现的（尽管人们可能会认为它们比数组更“抽象”）。顺便说一句，抽象数据类型粗略地说就是您的数据结构必须支持的接口。让数组和链表实现相同的接口并不难（例如，查看Java中的ArrayList vs LinkedList）。虽然，关键操作的效率：插入，删除和[]（在给定索引i处访问）将大不相同。 – 2012-01-29 07:36:21

数组和列表是不同的数据结构。数组不一定是有序的。性能明智，维护有序列表非常昂贵：O（N）插入，删除，但是你可以比O（N）更快地进行搜索（使用二进制搜索等）。使用常规数组，搜索是O（N）。使用数组，您可以随机访问O（1）中的成员，而这需要O（N）在列表中。

来源

2012-01-29 07:19:00 Oleksi

从理论的角度来看，有序列表和数组之间有什么区别？

回答

相关问题