有没有区别,或者它们是同一事物的两个术语?从理论的角度来看,有序列表和数组之间有什么区别?
回答
虽然数组和列表之间有一些相似之处,但它们被用于不同的目的。
数组是连续的内存段,而列表只是一堆节点,每个节点都有指向“下一个”节点的指针(在双向列表的情况下也指向“上一个”节点)。 O(1) - 支持随机访问(即通过任意给定的索引i),但删除/插入元素到数组中很慢 - O(n),因为必须在所有元素之后移动所有元素删除/插入元素。另一方面,列表不支持有效的随机访问(同时支持高效的连续遍历),但插入和删除操作快 - O(1)。
看这张图片:: 和this link为了更好的解释。
数组中的项不一定是任何特定的顺序。
通常,可以更快速地将项目添加到列表中的特定点,而不是在等效点添加新项目。 (在数组中,您必须对其他条目进行混洗;在列表中,只需调整最多3个元素中的适当指针即可)。类似地,用于从列表和数组中删除元素。
访问N th列表中的项需要O(N)时间,但是O(1)时间是一个数组。
所以数组是一个基于硬件(或实现)的概念,而有序列表是一种抽象数据类型? – 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)在列表中。
- 1. 从SOA角度来看Registry和Repository之间有什么区别?
- 2. 从设计的角度来看,Log()和Log(LogLevel)之间有什么区别吗?
- 3. 列表,排序列表和数组列表之间有什么区别? (c#)
- 4. 从任何角度来看,++ i和i + = 1之间的区别
- 5. 从.NET的角度来看,EXE和DLL之间有什么特别的区别吗?
- 6. 从内核的角度来看,GLI和CLI在Linux中有什么区别
- 7. 冲突序列化和序列化之间有什么区别?
- 8. 在Python中列表和列表[:]之间有什么区别?
- 9. 从编译器/ CLR的角度来看,Interface和具体实例之间有什么区别?
- 10. 原始数组和引用数组之间有什么区别?
- 11. 角度数据表dtInstance.reloadData()与dtInstance.rerender()之间的区别是什么
- 12. 数组和散列有什么区别?
- 13. 从编码的角度来看,kafka和mapr流之间有什么不同?
- 14. 数据沿袭和数据来源之间有什么区别?
- 15. ERB评论中'<%#'和'<%#='之间有什么区别?
- 16. 深度数据和点云之间有什么区别?
- 17. “层”和“层”之间有什么区别?
- 18. Tableau和QlikView之间有什么区别
- 19. Microsoft.CompilerServices.AsyncTargetingPack和Microsoft.Bcl.Async之间有什么区别?
- 20. @Entity和@embeddable之间有什么区别
- 21. ContentObservable和DataSetObservable之间有什么区别?
- 22. touchmove和gesturechange之间有什么区别?
- 23. :notification.flags和notification.defaults之间有什么区别?
- 24. proc和lambda之间有什么区别?
- 25. :: after和after之间有什么区别?
- 26. read()和io.read()之间有什么区别?
- 27. Request()和Request.Form()之间有什么区别?
- 28. WebServiceBinding.EmitConformanceClaims和WebServiceBinding.ConformanceClaims之间有什么区别?
- 29. getA()和this.getA()之间有什么区别?
- 30. (int)和intval()之间有什么区别?
它与HTML有什么关系? – doc 2016-08-14 20:38:29