数组列表和链表是数据存储和检索中的常用术语。尽管有很多存储设备，但最终它们取决于存储机制。这两种存储机制将您的数据放置在存储设备中，并在需要时检索它们。让我们看一下它们如何在内存中存储数据。 数组列表使用顺序存储，并且数据段一个接一个地存储。这也许是一种更简单的存储方式–避免混淆。是的，我们可以从数组列表的下一个存储位置检索下一个项目或数据；但是，它借助于指针存储在“链接”列表中。在这里，我们需要两个存储位置进行存储–一个用于数据存储，另一个用于指针存储。指针指向下一个数据的存储位置。我们可以很容易地理解，链表从不顺序存储数据；相反，它使用随机存储机制。指针是定位存储器中数据位置的关键元素。
动态数组和链表
我们已经讨论了两种存储机制如何放入数据，并且可以为“数组”列表的内部存储方案指定“动态数组”一词。它只是将数据片段一个接一个地放置-因此命名-链表使用内部列表借助指针来跟踪下一个项目。因此，它使用内部链表，例如单链或双链列表，向我们显示下一个数据。
内存使用情况
由于数组列表仅存储实际数据，因此我们仅需要空间来存储数据。相反，在“链接”列表中，我们也使用指针。因此，需要两个内存位置，并且可以说，链表消耗的内存比阵列列表要多。链表的一个优势是，与数组列表相比，它不需要连续的内存位置来存储我们的数据。指针能够保存下一个数据位置的位置，甚至可以使用较小的不连续的内存插槽。当涉及到内存使用时，指针在链接列表中起主要作用，其有效性也是如此。
初始数组列表和链表的大小
使用“数组”列表，即使是一个空列表也需要10个大小，但是使用“链接”列表时，我们不需要那么大的空间。可以创建一个大小为0的空链表。稍后，可以根据需要增加大小。
数据检索
数据检索在数组列表中比较简单，因为它顺序存储。它所做的只是确定第一个数据位置。从那里开始，依次访问下一个位置以检索其余位置。它的计算方式类似于第一个数据位置+“n”，其中“n”是数组列表中数据的顺序。链接列表引用初始指针以查找第一个数据位置，并从此处引用与每个数据关联的指针以查找下一个数据位置。检索过程主要取决于此处的指针，它们有效地向我们显示了下一个数据位置。
数据结束
数组列表使用空值标记数据的结尾，而链接列表为此使用空指针。一旦系统识别出空数据，“数组”列表就会停止下一次数据检索。以类似的方式，空指针会阻止系统继续进行下一个数据检索。
反向遍历
链表能够借助iterator()反向运行。 但是，数组列表中没有这样的功能–反向遍历在这里成为问题。
哪种方法更适合“获取”或“搜索”操作？
数组列表花费O(1)时间来运行任何数据搜索，而链接列表花费u O(n)进行第n个数据搜索。因此，数组列表始终使用恒定时间进行任何数据搜索，但是在“链接”列表中，花费的时间取决于数据的位置。因此，数组列表始终是获取或搜索操作的更好选择。
插入或加法运算哪个更好？
数组列表和链接列表都需要O(1)时间来添加数据。但是，如果数组已满，则“数组”列表将花费大量时间来调整其大小并将项目复制到较新的项目。在这种情况下，“链接”列表是更好的选择。
哪个对删除操作更好？
删除操作在“数组”列表和“链接的”列表中花费的时间几乎相同。在“数组”列表中，此操作将删除数据，然后将数据的位置移动以形成较新的数组-这需要O(n)时间。在链接列表中，此操作遍历特定数据并更改指针位置以形成较新的列表。遍历和删除的时间在这里也是O(n)。
哪个更快？
我们知道一个数组列表使用一个内部数组来存储实际数据。因此，如果删除了任何数据，则所有即将到来的数据都需要进行存储移位。显然，这需要相当长的时间并减慢速度。在“链接”列表中不需要这种内存移位，因为它所做的只是更改指针位置。因此，在任何类型的数据存储中，链接列表都比数组列表快。但是，这完全取决于操作的类型，即，对于“获取”或“搜索”操作，“链接”列表比“数组”列表花费更多的时间。当我们查看整体性能时，可以说“链接”列表更快。
何时使用数组列表和链接列表？
数组列表最适合可提供连续内存的较小数据要求。但是，当我们处理大量数据时，连续内存的可用性将实现数据存储机制，无论数据存储机制是小是小。接下来，决定选择哪一个-数组列表还是链接列表。当只需要存储和检索数据时，可以继续使用数组列表。但是，列表可以通过处理数据为您提供帮助。一旦确定了需要多久进行一次数据操作，检查通常执行哪种类型的数据检索就很重要。当只是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
免责声明：以上内容仅是站长个人看法、理解、学习笔记、总结和研究收藏。不保证其正确性，因使用而带来的风险与本站无关！如本网站内容冒犯了您的权益，请联系站长，邮箱：，我们核实并会尽快处理。