Java中的数组或列表。 哪个更快？
我必须保留内存中的数千个string以Java方式串行访问。 我应该将它们存储在一个数组中，还是应该使用某种List？
由于数组将所有的数据保存在连续的内存块中（与列表不同），使用数组来存储数以千计的string会产生问题吗？
答：共识是性能差异较小。 List接口提供了更多的灵活性
我build议你使用一个分析器来testing哪个更快。
我个人的意见是你应该使用列表。
我在一个大型的代码库上工作，以前的一组开发人员在任何地方都使用数组。 它使代码非常不灵活。 在将其大块更改为列表之后，我们注意到速度没有区别。
Java的方式是你应该考虑哪些数据抽象最适合你的需求。 请记住，在Java中，List是一个抽象的，而不是一个具体的数据types。 您应该将这些string声明为List，然后使用ArrayList实现对其进行初始化。
List<String> strings = new ArrayList<String>(); 抽象数据types与具体实现的分离是面向对象编程的关键方面之一。
ArrayList使用数组作为其基础实现来实现List Abstract Data Type。 访问速度实际上与数组完全相同，具有能够向List添加和减去元素的额外优点（尽pipe这是对ArrayList的O（n）操作），并且如果稍后决定更改基础实现您可以。 例如，如果您意识到需要同步访问，则可以将实现更改为Vector，而不必重写所有代码。
事实上，ArrayList是专门devise用来取代大多数情况下的低级数组结构。 如果今天正在deviseJava，那么完全有可能数组完全被遗漏在ArrayList构造中。
由于数组将所有的数据保存在连续的内存块中（与列表不同），使用数组来存储数以千计的string会产生问题吗？
在Java中，所有集合只存储对象的引用，而不是对象本身。 数组和ArrayList都将在一个连续的数组中存储几千个引用，所以它们基本上是相同的。 您可以考虑在现代硬件上总是可以轻松使用几千个32位引用的连续块。 这并不能保证你不会完全耗尽内存，当然，只要连续的内存块要求不是很难。
你应该比数组更喜欢genericstypes。 正如其他人所提到的，数组是不灵活的，不具有genericstypes的expression能力。 （然而，它们支持运行时types检查，但与genericstypes混合不佳。）
但是，与往常一样，优化时应始终遵循以下步骤：
- 不要优化，直到你有一个漂亮，干净， 工作的版本的代码。 更改为genericstypes可能已经在这一步很好的动机了。
- 当你有一个很好，干净的版本，决定是否足够快。
- 如果速度不够快，则测量其性能 。 这一步很重要，有两个原因。 如果你不测量，你不会（1）知道你做的任何优化的影响，（2）知道在哪里优化。
- 优化代码中最热门的部分。
- 再次测量。 这和之前测量一样重要。 如果优化没有改善，则恢复 。 请记住， 没有优化的代码干净，漂亮，而且工作。
虽然提出使用ArrayList的答案在大多数情况下是有意义的，但实际的相对性能问题并没有真正的答案。
你可以用一个数组做一些事情：
- 创build它
- 设置一个项目
- 得到一个项目
- 克隆/复制它
一般结论
尽pipe在ArrayList （我的机器上每次调用1和3纳秒）上获取和设置操作的速度稍微慢一些 ， 但是对于任何非密集使用，使用ArrayList和数组的开销很小。 有几件事要记住：
- 在调用
list.add(...)时，调整列表大小的操作代价高昂，应尽可能将初始容量设置为适当的级别（请注意，使用数组时，会出现同样的问题） - 当处理基元时，数组可以显着更快，因为它们将允许避免许多装箱/拆箱转换
- 只有在ArrayList中获取/设置值的应用程序（不是很常见！）可以通过切换到数组来获得超过25％的性能增益
详细的结果
以下是我在标准x86台式机上使用JDK 7 testing了这三个使用jmh基准testing库 （以纳秒为单位）的操作的结果。 请注意，ArrayList在testing中从不resize，以确保结果具有可比性。 基准代码在这里可用 。
Array / ArrayList创build
我跑了4个testing，执行以下语句：
- createArray1：
Integer[] array = new Integer[1]; - createList1：
List<Integer> list = new ArrayList<> (1); - createArray10000：
Integer[] array = new Integer[10000]; - createList10000：
List<Integer> list = new ArrayList<> (10000);
结果（每次调用纳秒，95％的置信度）：
apgaArrayVsList.CreateArray1 [10.933, 11.097] apgaArrayVsList.CreateList1 [10.799, 11.046] apgaArrayVsList.CreateArray10000 [394.899, 404.034] apgaArrayVsList.CreateList10000 [396.706, 401.266]
结论：没有明显的差异 。
得到操作
我跑了2个testing，执行以下语句：
- getList：
return list.get(0); - getArray：
return array[0];
结果（每次调用纳秒，95％的置信度）：
apgaArrayVsList.getArray [2.958, 2.984] apgaArrayVsList.getList [3.841, 3.874]
结论：从一个数组中获得的数据比从ArrayList中获得的数据快25％ ，尽pipe差别只有一个纳秒。
设置操作
我跑了2个testing，执行以下语句：
- setList：
list.set(0, value); - setArray：
array[0] = value;
结果（每次调用纳秒）：
apgaArrayVsList.setArray [4.201, 4.236] apgaArrayVsList.setList [6.783, 6.877]
结论：对数组的设置操作比列表上的操作要快40％ ，但是对于每一个操作需要几个纳秒 – 所以为了达到1秒的差异，需要设置列表/数组中的项目数百数百万次！
克隆/复制
ArrayList的拷贝构造函数委托给Arrays.copyOf所以性能与数组拷贝相同（通过clone复制数组， Arrays.copyOf或者System.arrayCopy 在性能上没有实质性差异 ）。
我猜测原来的海报是来自C ++ / STL背景，这是造成一些混淆。 在C ++中std::list是一个双向链表。
在Java [java.util.]List是一个无实现的接口（以C ++语言表示的纯抽象类）。 List可以是一个双向链表 – 提供了java.util.LinkedList 。 然而，当你想要创build一个新的List时，100次中的99次，你想要使用java.util.ArrayList ，这相当于C ++ std::vector 。 还有其他的标准实现，比如java.util.Collections.emptyList()和java.util.Arrays.asList()返回的实现。
从性能的angular度来看，通过一个接口和一个额外的对象是非常小的，但是运行时内联意味着这很less有任何意义。 还要记住， String通常是一个对象加数组。 因此，对于每个条目，您可能还有另外两个对象。 在C ++ std::vector<std::string> ，尽pipe没有指针的值复制，字符数组将形成一个string对象（通常不会被共享）。
如果这个特殊的代码真的是性能敏感的，你可以为所有string的所有字符创build一个char[]数组（或甚至byte[] ），然后创build一个偏移量数组。 IIRC，这是如何实施javac。
我写了一个基准来比较ArrayLists和Arrays。 在我的旧笔记本电脑上，遍历5000个元素数组列表的时间是1000次，比同等数组代码慢10毫秒。
所以，如果你没有做任何事情，只是迭代列表，你做了很多，那么也许这是值得的优化。 否则，我会使用列表，因为当你需要优化代码时，它会更容易。
NB我没有注意到使用for String s: stringsList大约比使用旧式的for循环访问列表慢50％。 去图…这是我计时的两个function; 数组和列表中填充了5000个随机（不同）的string。
private static void readArray(String[] strings) { long totalchars = 0; for (int j = 0; j < ITERATIONS; j++) { totalchars = 0; for (int i = 0; i < strings.length; i++) { totalchars += strings[i].length(); } } } private static void readArrayList(List<String> stringsList) { long totalchars = 0; for (int j = 0; j < ITERATIONS; j++) { totalchars = 0; for (int i = 0; i < stringsList.size(); i++) { totalchars += stringsList.get(i).length(); } } }
那么首先它是值得澄清你的意思是“列表”在经典的科幻数据结构的意义（即链表）或你的意思是java.util.List？ 如果你的意思是一个java.util.List，它是一个接口。 如果你想使用一个数组只是使用ArrayList实现，你会得到类似数组的行为和语义。 问题解决了。
如果你的意思是一个数组vs一个链表，这是一个略有不同的论点，我们回到大O（这是一个简单的英文解释，如果这是一个陌生的术语。
arrays;
- 随机访问：O（1）;
- 插入：O（n）;
- 删除：O（n）。
链接列表：
- 随机访问：O（n）;
- 插入：O（1）;
- 删除：O（1）。
所以你select一个最适合你调整arrays大小的方法。 如果你resize，插入和删除很多，那么也许链接列表是一个更好的select。 如果随机访问是罕见的，也是如此。 你提到串行访问。 如果你主要是做很less修改的串行访问，那么你select的可能并不重要。
链接列表的开销稍高一些，因为像你说的那样，你正在处理潜在的不连续的内存块和（有效的）指向下一个元素的指针。 这可能不是一个重要的因素，除非你处理数以百万计的条目。
我同意，在大多数情况下，您应该selectArrayLists相对于数组的灵活性和优雅性 – 而且在大多数情况下，对程序性能的影响可以忽略不计。
但是，如果你正在进行不断的， 重复性较差的结构变化（不增加或删除）软件graphics渲染或定制的虚拟机，我的顺序访问基准testing显示ArrayLists比我的数组慢1.5倍系统（在我一岁的iMac的Java 1.6）。
一些代码：
import java.util.*; public class ArrayVsArrayList { static public void main( String[] args ) { String[] array = new String[300]; ArrayList<String> list = new ArrayList<String>(300); for (int i=0; i<300; ++i) { if (Math.random() > 0.5) { array[i] = "abc"; } else { array[i] = "xyz"; } list.add( array[i] ); } int iterations = 100000000; long start_ms; int sum; start_ms = System.currentTimeMillis(); sum = 0; for (int i=0; i<iterations; ++i) { for (int j=0; j<300; ++j) sum += array[j].length(); } System.out.println( (System.currentTimeMillis() - start_ms) + " ms (array)" ); // Prints ~13,500 ms on my system start_ms = System.currentTimeMillis(); sum = 0; for (int i=0; i<iterations; ++i) { for (int j=0; j<300; ++j) sum += list.get(j).length(); } System.out.println( (System.currentTimeMillis() - start_ms) + " ms (ArrayList)" ); // Prints ~20,800 ms on my system - about 1.5x slower than direct array access } }
不，从技术上讲，数组只存储对string的引用。 string本身分配在不同的位置。 对于一千个项目，我会说列表会更好，但速度更慢，但它提供了更多的灵活性，使用起来更容易，特别是如果您要调整它们的大小。
如果您有成千上万，请考虑使用一个trie。 一个trie是一个树状结构，它合并了存储的string的公共前缀。
例如，如果string是
intern international internationalize internet internets
该trie将存储：
intern -> \0 international -> \0 -> ize\0 net ->\0 ->s\0
这些string需要57个字符（包括空终止符'\ 0'）用于存储，以及包含它们的string对象的大小。 （实际上，我们也许应该将所有的大小都调整到16的倍数，但是…）粗略地称它为57 + 5 = 62字节。
为了存储，trie需要29个（包括空终止符'\ 0'）加上trie节点的大小，这是一个数组的ref和一个子trie节点的列表。
对于这个例子，这可能是相同的; 成千上万，只要你有共同的前缀，它可能出来less。
现在，在其他代码中使用trie时，必须转换为String，可能使用StringBuffer作为中介。 如果很多string在string之外被同时用作string，那么这是一个损失。
但是，如果你只用了几个字 – 比如在字典中查找东西，那么这个字典可以为你节省很多空间。 将它们存储在HashSet中的空间肯定比较less。
你说你连续访问它们 – 如果这意味着按字母顺序排列，那么如果你以深度优先的方式迭代它，那么显然还是给你免费的字母顺序。
更新：
正如Mark指出的那样，JVM热身后（几次testing通过）没有显着差异。 检查重新创build的数组，甚至新的matrix的新行开始通过。 很有可能这个标志简单的数组与索引访问不会被用于集合的青睐。
仍然第一次1-2传递简单的数组是2-3倍的速度。
原来的post：
太简单的话题太多，检查。 没有任何问题，数组比任何类容器快几倍 。 我运行这个问题寻找我的性能关键部分的替代品。 这里是我build立的原型代码来检查实际情况：
import java.util.List; import java.util.Arrays; public class IterationTest { private static final long MAX_ITERATIONS = 1000000000; public static void main(String [] args) { Integer [] array = {1, 5, 3, 5}; List<Integer> list = Arrays.asList(array); long start = System.currentTimeMillis(); int test_sum = 0; for (int i = 0; i < MAX_ITERATIONS; ++i) { // for (int e : array) { for (int e : list) { test_sum += e; } } long stop = System.currentTimeMillis(); long ms = (stop - start); System.out.println("Time: " + ms); } }
这里是答案：
基于数组（第16行有效）：
Time: 7064
基于列表（第17行是有效的）：
Time: 20950
还有什么更快的评论？ 这是很了解的。 问题是什么时候快3倍左右比List的灵活性更好。 但这是另一个问题。 顺便说一下，我也检查了这个基于手动构build的ArrayList 。 几乎相同的结果。
由于这里已经有很多好的答案，所以我想给你一些其他的实用视图的信息，即插入和迭代性能比较：Java中的基本数组与链接列表。
这实际上是简单的性能检查。
所以，结果将取决于机器的性能。
用于此的源代码如下：
import java.util.Iterator; import java.util.LinkedList; public class Array_vs_LinkedList { private final static int MAX_SIZE = 40000000; public static void main(String[] args) { LinkedList lList = new LinkedList(); /* insertion performance check */ long startTime = System.currentTimeMillis(); for (int i=0; i<MAX_SIZE; i++) { lList.add(i); } long stopTime = System.currentTimeMillis(); long elapsedTime = stopTime - startTime; System.out.println("[Insert]LinkedList insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond."); int[] arr = new int[MAX_SIZE]; startTime = System.currentTimeMillis(); for(int i=0; i<MAX_SIZE; i++){ arr[i] = i; } stopTime = System.currentTimeMillis(); elapsedTime = stopTime - startTime; System.out.println("[Insert]Array Insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond."); /* iteration performance check */ startTime = System.currentTimeMillis(); Iterator itr = lList.iterator(); while(itr.hasNext()) { itr.next(); // System.out.println("Linked list running : " + itr.next()); } stopTime = System.currentTimeMillis(); elapsedTime = stopTime - startTime; System.out.println("[Loop]LinkedList iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond."); startTime = System.currentTimeMillis(); int t = 0; for (int i=0; i < MAX_SIZE; i++) { t = arr[i]; // System.out.println("array running : " + i); } stopTime = System.currentTimeMillis(); elapsedTime = stopTime - startTime; System.out.println("[Loop]Array iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond."); } }
绩效结果如下：
如果事先知道数据有多大，那么数组将会更快。
列表更灵活。 您可以使用由数组支持的ArrayList。
列表比数组慢。如果你需要效率使用数组。如果你需要灵活使用列表。
请记住，ArrayList封装了一个数组，因此与使用基本数组相比几乎没有什么区别（除了List更容易在java中使用）。
几乎唯一有意义的是，将一个数组更改为一个ArrayList的时候，就是当你存储原始数据，比如byte，int等时，你需要使用原始数组获得特定的空间效率。
在存储string对象的情况下，数组和列表的select并不重要（考虑性能）。 因为数组和列表都将存储string对象引用，而不是实际的对象。
- 如果string的数量几乎不变，那么使用一个数组（或ArrayList）。 但是，如果数量变化太多，那么你最好使用LinkedList。
- 如果有（或将要）在中间添加或删除元素，那么您当然必须使用LinkedList。
你可以住在一个固定的大小，数组将会更快，需要更less的内存。
如果您需要添加和移除元素的List界面的灵活性，问题仍然是您应该select哪个实现。 对于任何情况，ArrayList都经常被推荐和使用，但是如果ArrayList的开始或者中间的元素必须被删除或者插入的话，ArrayList也会有性能问题。
因此，您可能需要查看介绍GapList的http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list 。 这个新的列表实现结合了ArrayList和LinkedList的强大function，几乎可以为所有操作提供非常好的性能。
取决于实施。 原始types的数组可能会比ArrayList更小，效率更高。 这是因为数组将直接将值存储在连续的内存块中，而最简单的ArrayList实现将存储指向每个值的指针。 特别是在64位平台上，这可以造成巨大的差异。
当然，对于这种情况，jvm实现有可能有一个特殊的情况，在这种情况下，性能将是相同的。
List是Java 1.5及更高版本中的首选方式，因为它可以使用generics。 数组不能有generics。 数组也有一个预定义的长度，不能dynamic增长。 初始化一个大尺寸的数组不是一个好主意。 ArrayList是用generics声明数组的方式，它可以dynamic增长。 但是，如果更频繁地使用删除和插入，则链接列表是要使用的最快的数据结构。
数组推荐到处都可以使用它们，而不是列表，尤其是在知道项目数量和大小不会改变的情况下。
请参阅Oracle Java最佳实践： http : //docs.oracle.com/cd/A97688_16/generic.903/bp/java.htm#1007056
当然，如果你需要从collections中添加和删除对象很多时候很容易使用的列表。
ArrayList将其项存储在一个Object[]数组中，并使用非types化的toArray方法，该方法比input的要快得多（蓝条）。 这是types安全的，因为非types化数组被封装在由编译器检查的genericstypesArrayList<T>中。
此图表显示了Java 7上的n = 5的基准。但是，对于更多项目或另一个VM，图片变化不大。 CPU的开销似乎不是很大，但总和。 有可能是数组的消费者必须将其转换为集合，以便对其执行任何操作，然后将结果转换回数组，以将其馈送到另一个接口方法等。使用简单的ArrayList而不是数组可以提高性能，而不增加足迹。 ArrayList向包裹数组添加一个32字节的常量开销。 例如，一个有十个对象的array需要104个字节，一个ArrayList 136个字节。
这个操作在不变的时间内执行，所以比上面的任何一个（黄色条）都要快得多。 这不是一个防守的副本。 当内部数据发生变化时，不可修改的集合将会改变。 如果发生这种情况，客户端可以在迭代项目时运行到ConcurrentModificationException 。 接口提供的方法在运行时会抛出一个UnsupportedOperationException ，这可能被认为是糟糕的devise。 但是，至less在内部使用时，这种方法可以成为防御性副本的高性能替代scheme – 这是数组无法实现的。
没有一个答案有我感兴趣的信息 – 多次重复扫描同一个arrays。 必须为此创build一个JMHtesting。
结果 （Java 1.8.0_66 x32，迭代普通数组至less比ArrayList快5倍）：
Benchmark Mode Cnt Score Error Units MyBenchmark.testArrayForGet avgt 10 8.121 ? 0.233 ms/op MyBenchmark.testListForGet avgt 10 37.416 ? 0.094 ms/op MyBenchmark.testListForEach avgt 10 75.674 ? 1.897 ms/op
testing
package my.jmh.test; import java.util.ArrayList; import java.util.List; import java.util.concurrent.TimeUnit; import org.openjdk.jmh.annotations.Benchmark; import org.openjdk.jmh.annotations.BenchmarkMode; import org.openjdk.jmh.annotations.Fork; import org.openjdk.jmh.annotations.Measurement; import org.openjdk.jmh.annotations.Mode; import org.openjdk.jmh.annotations.OutputTimeUnit; import org.openjdk.jmh.annotations.Scope; import org.openjdk.jmh.annotations.State; import org.openjdk.jmh.annotations.Warmup; @State(Scope.Benchmark) @Fork(1) @Warmup(iterations = 5, timeUnit = TimeUnit.SECONDS) @Measurement(iterations = 10) @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MILLISECONDS) public class MyBenchmark { public final static int ARR_SIZE = 100; public final static int ITER_COUNT = 100000; String arr[] = new String[ARR_SIZE]; List<String> list = new ArrayList<>(ARR_SIZE); public MyBenchmark() { for( int i = 0; i < ARR_SIZE; i++ ) { list.add(null); } } @Benchmark public void testListForEach() { int count = 0; for( int i = 0; i < ITER_COUNT; i++ ) { for( String str : list ) { if( str != null ) count++; } } if( count > 0 ) System.out.print(count); } @Benchmark public void testListForGet() { int count = 0; for( int i = 0; i < ITER_COUNT; i++ ) { for( int j = 0; j < ARR_SIZE; j++ ) { if( list.get(j) != null ) count++; } } if( count > 0 ) System.out.print(count); } @Benchmark public void testArrayForGet() { int count = 0; for( int i = 0; i < ITER_COUNT; i++ ) { for( int j = 0; j < ARR_SIZE; j++ ) { if( arr[j] != null ) count++; } } if( count > 0 ) System.out.print(count); } }
“千”不是一个大数字。 数千段长度的string大小为几兆字节。 如果你想要做的只是连续访问它们，使用一个不可变的单链表 。
如果没有适当的基准，不要进入优化的陷阱。 正如其他人所build议的，在作出任何假设之前使用一个分析器
您列举的不同数据结构有不同的用途。 列表在开始和结束处插入元素非常有效，但在访问随机元素时会遇到很多问题。 一个数组有固定的存储，但提供了快速的随机访问 最后一个ArrayList通过允许它增长来改进数组的接口。 通常，要使用的数据结构应由存储的数据如何访问或添加决定。
关于内存消耗。 你似乎在混合一些东西。 数组只会为您提供的数据types提供连续的内存块。 不要忘记，java有一个固定的数据types：布尔型，char型，int型，long型，float型和Object型（这包括所有的对象，甚至一个数组也是一个Object）。 这意味着如果你声明一个String string [1000]或者MyObject myObjects [1000]的数组，你只能得到1000个足够大的内存空间来存储对象的位置（引用或指针）。 你没有得到足够大的1000个内存盒来适应对象的大小。 不要忘记你的对象是用“新”创build的。 This is when the memory allocation is done and later a reference (their memory address) is stored in the array. The object doesn't get copied into the array only it's reference.
I don't think it makes a real difference for Strings. What is contiguous in an array of strings is the references to the strings, the strings themselves are stored at random places in memory.
Arrays vs. Lists can make a difference for primitive types, not for objects. IF you know in advance the number of elements, and don't need flexibility, an array of millions of integers or doubles will be more efficient in memory and marginally in speed than a list, because indeed they will be stored contiguously and accessed instantly. That's why Java still uses arrays of chars for strings, arrays of ints for image data, etc.
Array is faster – all memory is pre-allocated in advance.
A lot of microbenchmarks given here have found numbers of a few nanoseconds for things like array/ArrayList reads. This is quite reasonable if everything is in your L1 cache.
A higher level cache or main memory access can have order of magnitude times of something like 10nS-100nS, vs more like 1nS for L1 cache. Accessing an ArrayList has an extra memory indirection, and in a real application you could pay this cost anything from almost never to every time, depending on what your code is doing between accesses. And, of course, if you have a lot of small ArrayLists this might add to your memory use and make it more likely you'll have cache misses.
The original poster appears to be using just one and accessing a lot of contents in a short time, so it should be no great hardship. But it might be different for other people, and you should watch out when interpreting microbenchmarks.
Java Strings, however, are appallingly wasteful, especially if you store lots of small ones (just look at them with a memory analyzer, it seems to be > 60 bytes for a string of a few characters). An array of strings has an indirection to the String object, and another from the String object to a char[] which contains the string itself. If anything's going to blow your L1 cache it's this, combined with thousands or tens of thousands of Strings. So, if you're serious – really serious – about scraping out as much performance as possible then you could look at doing it differently. You could, say, hold two arrays, a char[] with all the strings in it, one after another, and an int[] with offsets to the starts. This will be a PITA to do anything with, and you almost certainly don't need it. And if you do, you've chosen the wrong language.
It depends on how you have to access it.
After storing, if you mainly want to do search operation, with little or no insert/delete, then go for Array (as search is done in O(1) in arrays, whereas add/delete may need re-ordering of the elements).
After storing, if your main purpose is to add/delete strings, with little or no search operation, then go for List.
ArrayList internally uses array object to add(or store) the elements. In other words, ArrayList is backed by Array data -structure.The array of ArrayList is resizable (or dynamic).
Array is faster than Array because ArrayList internally use array. if we can directly add elements in Array and indirectly add element in Array through ArrayList always directly mechanism is faster than indirectly mechanism.
There are two overloaded add() methods in ArrayList class:
1. add(Object) : adds object to the end of the list.
2. add(int index , Object ) : inserts the specified object at the specified position in the list.
How the size of ArrayList grows dynamically?
public boolean add(E e) { ensureCapacity(size+1); elementData[size++] = e; return true; }
Important point to note from above code is that we are checking the capacity of the ArrayList , before adding the element. ensureCapacity() determines what is the current size of occupied elements and what is the maximum size of the array. If size of the filled elements (including the new element to be added to the ArrayList class) is greater than the maximum size of the array then increase the size of array. But the size of the array can not be increased dynamically. So what happens internally is new Array is created with capacity
Till Java 6
int newCapacity = (oldCapacity * 3)/2 + 1;
(Update) From Java 7
int newCapacity = oldCapacity + (oldCapacity >> 1);
also, data from the old array is copied into the new array.
Having overhead methods in ArrayList that's why Array is faster than ArrayList .
Arrays – It would always be better when we have to achieve faster fetching of results
Lists- Performs results on insertion and deletion since they can be done in O(1) and this also provides methods to add, fetch and delete data easily. Much easier to use.
But always remember that the fetching of data would be fast when the index position in array where the data is stored – is known.
This could be achieved well by sorting the array. Hence this increases the time to fetch the data (ie; storing the data + sorting the data + seek for the position where the data is found). Hence this increases additional latency to fetch the data from the array even they may be good at fetching the data sooner.
Hence this could be solved with trie data structure or ternary data structure. As discussed above the trie data structure would be very efficient in searching for the data the search for a particularly word can be done in O(1) magnitude. When time matters ie; if you have to search and retrieve data quickly you may go with trie data structure.
If you want your memory space to be consumed less and you wish to have a better performance then go with ternary data structure. Both these are suitable for storing huge number of strings (eg; like words contained in dictionary).
