在java中使用数组实现链接列表？

我已经在robbert laffore中读过它，我们可以使用数组实现链表。但问题是如何？在java中使用数组实现链接列表？

我有下面的方法在我的脑海：

1）而不是一个链接对象的使用大小的阵列，2一保持到下一个项目和其他参考。但我不是这样做的好方法。

有人可以建议一个更好的方法来实现链接列表使用数组？

来源

2014-02-22 Sahil Gupta

链接列表的目的是获得不使用数组的好处，所以试图实现这样的事情毫无意义。 – Whoppa

“而不是链接对象使用大小为2的数组，其中一个保存项目和其他引用到下一个。” - 这是以某种方式迫使数组进入解决方案的一种方式。不要这样做！ – RaviH

b/w JAVA和C有**主要差异。首先阅读JAVA书。 – Astrobleme

一个典型的阵列支持的链接列表存储在一个单一阵列的完整列表，如：

class ABLL<T> { 
    Node[] theList; 
    class Node { 
     T item; 
     int next; // You store the index of the next node 
        // instead of a reference 
    } 
    ... 
}

你会初始化数组的一些能力，它不会增长超出能力（除非你添加该功能，这将涉及分配一个新的数组并将内容复制到它）。您可以搜索“Array-backed Linked List”以查找有关此数据结构的更多讨论。

这使得在Java中意义不大比C.

来源

2014-02-22 07:23:17 trutheality

这就是所谓的的ArrayList

相反的是@trutheality说，他们并不需要一个固定的容量，节点不存储下一个项目的索引。为了避开典型数组的大小限制，ArrayLists被设计为当它们达到预定义的最小/最大边界时自动调整大小。

调整内部阵列的尺寸很昂贵。它包括创建一个新阵列并将数据从旧阵列移动到新阵列。因此，限制所需的调整大小操作的数量是有益的。

一种方法是在列表达到最大容量时将阵列大小加倍，当列表达到1/4容量时将其缩小一半。

阵列没有收缩到一半容量的原因是为了避免抖动。抖动是指在容量边界的边界上数组增大/减小时，导致大量调整大小操作而对内部数据进行少量更改。

尽管调整大小的成本 - 因为它只发生在数据集加倍时 - 实际性能成本只有O（log n）。因此，插入成本是线性O（N log N），而检索是恒定的O（N）。

ArrayLists有一个主要弱点。如果添加/删除列表中的任意项目，则必须移动数组内容以适应更改。耗费线性O（N）时间的操作。尽管在传统LinkedList中更改任意项目的成本很便宜（即恒定的O（1）时间），但该操作需要查找来查找耗时线性O（N）时间的链中的位置。除非你创建了一个队列，并且列表的两端都经常发生变化，否则使用ArrayList作为列表基础可能是更好的选择。

来源：目前正在参加一门算法课程，刚刚完成从头开始实现ArrayList和LinkedList。

来源

2014-02-24 10:57:36

在java中使用数组实现链接列表？

回答

相关问题