java - 节点数组如何工作？

Question

这是基于我的另一个问题。 What is an array linked structure or node array?

我正在尝试做这个练习

对我的另一个问题的答复之一要求我请老师澄清什么是数组链接的层次结构。我问了她之后，她说就是一个节点数组而已。

我认为节点数组符合 laune 所说的，因为“如果您有一组有限的固定类型的节点，则使用该技术，并将其保存在数组 Node[] = new Node[CAPACITY] 中，Node 的一个字段是 int - 索引。像往常一样，有效负载是任何东西。最初，您拥有可用列表中的所有节点，链接为 0->1->2->"，有效负载是以下数据:节点持有，其中包括数据及其持有的链接。

综上所述，这就是我脑海中的数据结构

public class NodeArray {
   private ListNode[] elementData;
    ...
   private class ListNode {
        private int data;
        private ListNode next;
        ....
   }
 }

这种节点数组数据结构与常规链表和数组列表相比有什么优点？我不明白为什么你会想要这样的数据结构。对我来说，它只是 ArrayList 的另一个版本，因为数组列表是通用的，它们的数组可以与任何类型一起使用，包括列表节点。

Answer 1

我倾向于认为链表更适合插入和删除，而数组列表更适合搜索。

数组列表的一些优点:

- 数组列表的内存是合并的，与链接列表不同，链接列表的不相交节点对象将位于稀疏地址。让所有对象彼此靠近可以改善缓存和内存查找。

- 使用数组列表搜索第 n 个元素是数组索引，这是一个 O(1) 操作；而在链表中搜索第 n 个元素是一个 O(N) 操作。

链接列表的一些优点:

-数组列表通常会分配比所需更多的内存，因为每次达到容量时都需要分配全新的内存块，并且必须复制原始数组中的数据。

-删除操作可以更便宜，因为删除地址上方的内存不需要向下移动。

编辑:这是您问题的一个很好的答案 When to use LinkedList over ArrayList?