r 数组列表和链表

数组列表和链表是数据存储和检索中的常用术语。尽管有很多存储设备,但最终它们取决于存储机制。这两种存储机制将您的数据放置在存储设备中,并在需要时检索它们。让我们看一下它们如何在内存中存储数据。 数组列表使用顺序存储,并且数据段一个接一个地存储。这也许是一种更简单的存储方式–避免混淆。是的,我们可以从数组列表的下一个存储位置检索下一个项目或数据;但是,它借助于指针存储在“链接”列表中。在这里,我们需要两个存储位置进行存储–一个用于数据存储,另一个用于指针存储。指针指向下一个数据的存储位置。我们可以很容易地理解,链表从不顺序存储数据;相反,它使用随机存储机制。指针是定位存储器中数据位置的关键元素。

动态数组和链表

我们已经讨论了两种存储机制如何放入数据,并且可以为“数组”列表的内部存储方案指定“动态数组”一词。它只是将数据片段一个接一个地放置-因此命名-链表使用内部列表借助指针来跟踪下一个项目VsDiFFeR。因此,它使用内部链表,例如单链或双链列表,向我们显示下一个数据。

内存使用情况

由于数组列表仅存储实际数据,因此我们仅需要空间来存储数据。相反,在“链接”列表中,我们也使用指针。因此,需要两个内存位置,并且可以说,链表消耗的内存比阵列列表要多。链表的一个优势是,与数组列表相比,它不需要连续的内存位置来存储我们的数据。指针能够保存下一个数据位置的位置,甚至可以使用较小的不连续的内存插槽vSdIFfER。当涉及到内存使用时,指针在链接列表中起主要作用,其有效性也是如此。

初始数组列表和链表的大小
使用“数组”列表,即使是一个空列表也需要10个大小,但是使用“链接”列表时,我们不需要那么大的空间。可以创建一个大小为0的空链表。稍后,可以根据需要增加大小。

数据检索
数据检索在数组列表中比较简单,因为它顺序存储。它所做的只是确定第一个数据位置。从那里开始,依次访问下一个位置以检索其余位置。它的计算方式类似于第一个数据位置+“n”,其中“n”是数组列表中数据的顺序。链接列表引用初始指针以查找第一个数据位置,并从此处引用与每个数据关联的指针以查找下一个数据位置。检索过程主要取决于此处的指针,它们有效地向我们显示了下一个数据位置。

数据结束
数组列表使用空值标记数据的结尾,而链接列表为此使用空指针。一旦系统识别出空数据,“数组”列表就会停止下一次数据检索。以类似的方式,空指针会阻止系统继续进行下一个数据检索。

反向遍历
链表能够借助iterator()反向运行。 但是,数组列表中没有这样的功能–反向遍历在这里成为问题。

哪种方法更适合“获取”或“搜索”操作?
数组列表花费O(1)时间来运行任何数据搜索,而链接列表花费u O(n)进行第n个数据搜索VsdifFer。因此,数组列表始终使用恒定时间进行任何数据搜索,但是在“链接”列表中,花费的时间取决于数据的位置。因此,数组列表始终是获取或搜索操作的更好选择。

插入或加法运算哪个更好?
数组列表和链接列表都需要O(1)时间来添加数据。但是,如果数组已满,则“数组”列表将花费大量时间来调整其大小并将项目复制到较新的项目。在这种情况下,“链接”列表是更好的选择。

哪个对删除操作更好?

删除操作在“数组”列表和“链接的”列表中花费的时间几乎相同。在“数组”列表中,此操作将删除数据,然后将数据的位置移动以形成较新的数组-这需要O(n)时间。在链接列表中,此操作遍历特定数据并更改指针位置以形成较新的列表。遍历和删除的时间在这里也是O(n)。

哪个更快?
我们知道一个数组列表使用一个内部数组来存储实际数据。因此,如果删除了任何数据,则所有即将到来的数据都需要进行存储移位。显然,这需要相当长的时间并减慢速度。在“链接”列表中不需要这种内存移位,因为它所做的只是更改指针位置。因此,在任何类型的数据存储中,链接列表都比数组列表快VSDifFer。但是,这完全取决于操作的类型,即,对于“获取”或“搜索”操作,“链接”列表比“数组”列表花费更多的时间。当我们查看整体性能时,可以说“链接”列表更快。

何时使用数组列表和链接列表?
数组列表最适合可提供连续内存的较小数据要求。但是,当我们处理大量数据时,连续内存的可用性将实现数据存储机制,无论数据存储机制是小是小。接下来,决定选择哪一个-数组列表还是链接列表。当只需要存储和检索数据时,可以继续使用数组列表。但是,列表可以通过处理数据为您提供帮助。一旦确定了需要多久进行一次数据操作,检查通常执行哪种类型的数据检索就很重要。当只是Get或Search时,ArrayList是更好的选择。对于其他操作,例如插入或删除,请继续使用“链接”列表。

对比项 数组列表 链接列表
数据存储方式 使用顺序数据存储 使用非顺序数据存储
内部存储方案 维护内部动态数组 维护链接列表
内存使用情况 仅需要用于数据的存储空间 需要用于数据以及指针的存储空间
初始列表的大小 需要至少10个项目的空间 不需要空间,甚至可以创建一个大小为0的空链接列表。
数据检索计算方式 类似于第一个数据位置+“n”,其中“n”是数组列表中数据的顺序 从第一个或最后一个遍历到需要的数据
数据结束 Null值标记结束 Null指针标记结束
反向遍历 不允许 允许,它借助Descendingiterator()
列表创建语法 List <String> arraylistsample = new ArrayList <String> (); List <String> linkedlistsample = new linkedList <String> ();
添加对象 Arraylistsample.add(“name1”); Linkedlistsample.add(“ name3”);
Get或Search 花费O(1)的时间并获得更好的性能 花费O(n)的时间,而性能取决于数据的位置
插入或添加 消耗O(1)时间 但当阵列已满时则消耗O(1)时间
删除或移除 花费O(n)时间 花费O(n)时间
何时使用 当涉及大量的Get或Search操作时; 即使在开始时,内存可用性也应该更高 有很多插入或删除操作,并且内存可用性不需要连续时
欢迎任何形式的转载,但请务必注明出处,尊重他人劳动成果。
转载请注明:文章转载自 有区别网 [http://www.vsdiffer.com]
本文标题:数组列表和链表
本文链接:https://www.vsdiffer.com/vs/array-list-vs-linked-list.html
免责声明:以上内容仅是站长个人看法、理解、学习笔记、总结和研究收藏。不保证其正确性,因使用而带来的风险与本站无关!如本网站内容冒犯了您的权益,请联系站长,邮箱: ,我们核实并会尽快处理。