数组和链表是程序中经常使用的两种数据结构,也是面试中常考的面试题之一。然而对于不少人来讲,只是模糊的记得两者的区别,可能还记得不必定对,而且每次到了面试的时候,都得把这些的概念拿出来背一遍才行,未免有些麻烦。而本文则会从执行过程图以及性能评测等方面入手,让你更加深刻的理解和记忆两者的区别,有了此次深刻的学习以后,相信会让你记忆深入。java
在开始(性能评测)以前咱们先来回顾一下,什么是数组?面试
数组的定义以下:算法
数组(Array)是由相同类型的元素(element)的集合所组成的数据结构,分配一块连续的内存来存储。利用元素的索引(index)能够计算出该元素对应的存储地址。最简单的数据结构类型是一维数组。例如,索引为 0 到 9 的 32 位整数数组,可做为在存储器地址 2000,2004,2008,...2036 中,存储 10个 变量,所以索引为 i 的元素即在存储器中的 2000+4×i 地址。数组第一个元素的存储器地址称为第一地址或基础地址。数组
简单来讲,数组就是由一块连续的内存组成的数据结构。这个概念中有一个关键词“连续”,它反映了数组的一大特色,就是它必须是由一个连续的内存组成的。数据结构
数组的数据结构,以下图所示:
框架
数组添加的过程,以下图所示:
性能
数组的“连续”特征决定了它的访问速度很快,由于它是连续存储的,因此这就决定了它的存储位置就是固定的,所以它的访问速度就很快。好比如今有 10 个房间是按照年龄顺序入住的,当咱们知道第一房子住的是 20 岁的人以后,那么咱们就知道了第二个房子是 21 岁的人,第五个房子是 24 岁的人......等等。学习
祸兮福所倚,福兮祸所伏。数组的连续性既有优势又有缺点,优势上面已经说了,而缺点它对内存的要求比较高,必需要找到一块连续的内存才行。测试
数组的另外一个缺点就是插入和删除的效率比较慢,假如咱们在数组的非尾部插入或删除一个数据,那么就要移动以后的全部数据,这就会带来必定的性能开销,删除的过程以下图所示:
数组还有一个缺点,它的大小固定,不能动态拓展。ui
链表是和数组互补的一种数据结构,它的定义以下:
链表(Linked list)是一种常见的基础数据结构,是一种线性表,可是并不会按线性的顺序存储数据,而是在每个节点里存到下一个节点的指针(Pointer)。因为没必要须按顺序存储,链表在插入的时候能够达到 O(1) 的复杂度,比另外一种线性表顺序表快得多,可是查找一个节点或者访问特定编号的节点则须要 O(n) 的时间,而顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。
也就说链表是一个无需连续内存存储的数据结构,链表的元素有两个属性,一个是元素的值,另外一个是指针,此指针标记了下一个元素的地址。
链表的数据结构,以下图所示:
链表添加的过程,以下图所示:
链表删除的过程,以下图所示:
链表主要分为如下几类:
单向链表中包含两个域,一个信息域和一个指针域。这个连接指向列表中的下一个节点,而最后一个节点则指向一个空值,咱们上面所展现的链表就是单向链表。
双向链表也叫双链表,双向链表中不只有指向后一个节点的指针,还有指向前一个节点的指针,这样能够从任何一个节点访问前一个节点,固然也能够访问后一个节点,以致整个链表。
双向链表的结构以下图所示:
循环链表中第一个节点以前就是最后一个节点,反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。
循环链表的结构以下图所示:
有人可能会问,既然已经有单向链表了,那为何还要双向链表呢?双向链表有什么优点呢?
这个就要从链表的删除提及了,若是单向链表要删除元素的话,不但要找到删除的节点,还要找到删除节点的上一个节点(一般称之为前驱),由于须要变动上一个节点中 next 的指针,但又由于它是单向链表,因此在删除的节点中并无存储上一个节点的相关信息,那么咱们就须要再查询一遍链表以找到上一个节点,这样就带来了必定的性能问题,因此就有了双向链表。
链表的优势大体可分为如下三个:
链表的主要缺点是不能随机查找,必须从第一个开始遍历,查找效率比较低,链表查询的时间复杂度是 O(n)。
了解了数组和链表的基础知识以后,接下来咱们正式进入性能评测环节。
在正式开始以前,咱们先来明确一下测试目标,咱们须要测试的点其实只有 6 个:
由于添加操做和删除操做在执行时间层面基本是一致的,好比数组添加须要移动后面的元素,删除也一样是移动后面的元素;而链表也是如此,添加和删除都是改变自身和相连节点的信息,所以咱们就把添加和删除的测试合二为一,用添加操做来进行测试。
测试说明:
ArrayList
,而链表的表明为 LinkedList
,所以咱们就用这两个对象来进行测试;import org.openjdk.jmh.annotations.*; import org.openjdk.jmh.infra.Blackhole; import org.openjdk.jmh.runner.Runner; import org.openjdk.jmh.runner.RunnerException; import org.openjdk.jmh.runner.options.Options; import org.openjdk.jmh.runner.options.OptionsBuilder; import java.util.ArrayList; import java.util.LinkedList; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.AverageTime) // 测试完成时间 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热次数和时间 @Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // 测试次数和时间 @Fork(1) // fork 1 个线程 @State(Scope.Thread) public class ArrayOptimizeTest { private static final int maxSize = 1000; // 测试循环次数 private static final int operationSize = 100; // 操做次数 private static ArrayList<Integer> arrayList; private static LinkedList<Integer> linkedList; public static void main(String[] args) throws RunnerException { // 启动基准测试 Options opt = new OptionsBuilder() .include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类 .build(); new Runner(opt).run(); // 执行测试 } @Setup public void init() { // 启动执行事件 arrayList = new ArrayList<Integer>(); linkedList = new LinkedList<Integer>(); for (int i = 0; i < maxSize; i++) { arrayList.add(i); linkedList.add(i); } } @Benchmark public void addArrayByFirst(Blackhole blackhole) { for (int i = 0; i < +operationSize; i++) { arrayList.add(i, i); } // 为了不 JIT 忽略未被使用的结果计算 blackhole.consume(arrayList); } @Benchmark public void addLinkedByFirst(Blackhole blackhole) { for (int i = 0; i < +operationSize; i++) { linkedList.add(i, i); } // 为了不 JIT 忽略未被使用的结果计算 blackhole.consume(linkedList); } }
从以上代码能够看出,在测试以前,咱们先将 ArrayList
和 LinkedList
进行数据初始化,再从头部开始添加 100 个元素,执行结果以下:
从以上结果能够看出,LinkedList
的平均执行(完成)时间比 ArrayList
平均执行时间快了约 216 倍。
import org.openjdk.jmh.annotations.*; import org.openjdk.jmh.infra.Blackhole; import org.openjdk.jmh.runner.Runner; import org.openjdk.jmh.runner.RunnerException; import org.openjdk.jmh.runner.options.Options; import org.openjdk.jmh.runner.options.OptionsBuilder; import java.util.ArrayList; import java.util.LinkedList; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.AverageTime) // 测试完成时间 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热次数和时间 @Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // 测试次数和时间 @Fork(1) // fork 1 个线程 @State(Scope.Thread) public class ArrayOptimizeTest { private static final int maxSize = 1000; // 测试循环次数 private static final int operationSize = 100; // 操做次数 private static ArrayList<Integer> arrayList; private static LinkedList<Integer> linkedList; public static void main(String[] args) throws RunnerException { // 启动基准测试 Options opt = new OptionsBuilder() .include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类 .build(); new Runner(opt).run(); // 执行测试 } @Setup public void init() { // 启动执行事件 arrayList = new ArrayList<Integer>(); linkedList = new LinkedList<Integer>(); for (int i = 0; i < maxSize; i++) { arrayList.add(i); linkedList.add(i); } } @Benchmark public void addArrayByMiddle(Blackhole blackhole) { int startCount = maxSize / 2; // 计算中间位置 // 中间部分进行插入 for (int i = startCount; i < (startCount + operationSize); i++) { arrayList.add(i, i); } // 为了不 JIT 忽略未被使用的结果计算 blackhole.consume(arrayList); } @Benchmark public void addLinkedByMiddle(Blackhole blackhole) { int startCount = maxSize / 2; // 计算中间位置 // 中间部分进行插入 for (int i = startCount; i < (startCount + operationSize); i++) { linkedList.add(i, i); } // 为了不 JIT 忽略未被使用的结果计算 blackhole.consume(linkedList); } }
从以上代码能够看出,在测试以前,咱们先将 ArrayList
和 LinkedList
进行数据初始化,再从中间开始添加 100 个元素,执行结果以下:
从上述结果能够看出,LinkedList
的平均执行时间比 ArrayList
平均执行时间快了约 54 倍。
import org.openjdk.jmh.annotations.*; import org.openjdk.jmh.infra.Blackhole; import org.openjdk.jmh.runner.Runner; import org.openjdk.jmh.runner.RunnerException; import org.openjdk.jmh.runner.options.Options; import org.openjdk.jmh.runner.options.OptionsBuilder; import java.util.ArrayList; import java.util.LinkedList; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.AverageTime) // 测试完成时间 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热次数和时间 @Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // 测试次数和时间 @Fork(1) // fork 1 个线程 @State(Scope.Thread) public class ArrayOptimizeTest { private static final int maxSize = 1000; // 测试循环次数 private static final int operationSize = 100; // 操做次数 private static ArrayList<Integer> arrayList; private static LinkedList<Integer> linkedList; public static void main(String[] args) throws RunnerException { // 启动基准测试 Options opt = new OptionsBuilder() .include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类 .build(); new Runner(opt).run(); // 执行测试 } @Setup public void init() { // 启动执行事件 arrayList = new ArrayList<Integer>(); linkedList = new LinkedList<Integer>(); for (int i = 0; i < maxSize; i++) { arrayList.add(i); linkedList.add(i); } } @Benchmark public void addArrayByEnd(Blackhole blackhole) { int startCount = maxSize - 1 - operationSize; for (int i = startCount; i < (maxSize - 1); i++) { arrayList.add(i, i); } // 为了不 JIT 忽略未被使用的结果计算 blackhole.consume(arrayList); } @Benchmark public void addLinkedByEnd(Blackhole blackhole) { int startCount = maxSize - 1 - operationSize; for (int i = startCount; i < (maxSize - 1); i++) { linkedList.add(i, i); } // 为了不 JIT 忽略未被使用的结果计算 blackhole.consume(linkedList); } }
以上程序的执行结果为:
从上述结果能够看出,LinkedList
的平均执行时间比 ArrayList
平均执行时间快了约 32 倍。
import org.openjdk.jmh.annotations.*; import org.openjdk.jmh.runner.Runner; import org.openjdk.jmh.runner.RunnerException; import org.openjdk.jmh.runner.options.Options; import org.openjdk.jmh.runner.options.OptionsBuilder; import java.util.ArrayList; import java.util.LinkedList; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.AverageTime) // 测试完成时间 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热次数和时间 @Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // 测试次数和时间 @Fork(1) // fork 1 个线程 @State(Scope.Thread) public class ArrayOptimizeTest { private static final int maxSize = 1000; // 测试循环次数 private static final int operationSize = 100; // 操做次数 private static ArrayList<Integer> arrayList; private static LinkedList<Integer> linkedList; public static void main(String[] args) throws RunnerException { // 启动基准测试 Options opt = new OptionsBuilder() .include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类 .build(); new Runner(opt).run(); // 执行测试 } @Setup public void init() { // 启动执行事件 arrayList = new ArrayList<Integer>(); linkedList = new LinkedList<Integer>(); for (int i = 0; i < maxSize; i++) { arrayList.add(i); linkedList.add(i); } } @Benchmark public void findArrayByFirst() { for (int i = 0; i < operationSize; i++) { arrayList.get(i); } } @Benchmark public void findLinkedyByFirst() { for (int i = 0; i < operationSize; i++) { linkedList.get(i); } } }
以上程序的执行结果为:
从上述结果能够看出,从头部查询 100 个元素时 ArrayList
的平均执行时间比 LinkedList
平均执行时间快了约 1990 倍。
import org.openjdk.jmh.annotations.*; import org.openjdk.jmh.infra.Blackhole; import org.openjdk.jmh.runner.Runner; import org.openjdk.jmh.runner.RunnerException; import org.openjdk.jmh.runner.options.Options; import org.openjdk.jmh.runner.options.OptionsBuilder; import java.util.ArrayList; import java.util.LinkedList; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.AverageTime) // 测试完成时间 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热次数和时间 @Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // 测试次数和时间 @Fork(1) // fork 1 个线程 @State(Scope.Thread) public class ArrayOptimizeTest { private static final int maxSize = 1000; // 测试循环次数 private static final int operationSize = 100; // 操做次数 private static ArrayList<Integer> arrayList; private static LinkedList<Integer> linkedList; public static void main(String[] args) throws RunnerException { // 启动基准测试 Options opt = new OptionsBuilder() .include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类 .build(); new Runner(opt).run(); // 执行测试 } @Setup public void init() { // 启动执行事件 arrayList = new ArrayList<Integer>(); linkedList = new LinkedList<Integer>(); for (int i = 0; i < maxSize; i++) { arrayList.add(i); linkedList.add(i); } } @Benchmark public void findArrayByMiddle() { int startCount = maxSize / 2; int endCount = startCount + operationSize; for (int i = startCount; i < endCount; i++) { arrayList.get(i); } } @Benchmark public void findLinkedyByMiddle() { int startCount = maxSize / 2; int endCount = startCount + operationSize; for (int i = startCount; i < endCount; i++) { linkedList.get(i); } } }
以上程序的执行结果为:
从上述结果能够看出,从中间查询 100 个元素时 ArrayList
的平均执行时间比 LinkedList
平均执行时间快了约 28089 倍,真是恐怖。
import org.openjdk.jmh.annotations.*; import org.openjdk.jmh.runner.Runner; import org.openjdk.jmh.runner.RunnerException; import org.openjdk.jmh.runner.options.Options; import org.openjdk.jmh.runner.options.OptionsBuilder; import java.util.ArrayList; import java.util.LinkedList; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.AverageTime) // 测试完成时间 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热次数和时间 @Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // 测试次数和时间 @Fork(1) // fork 1 个线程 @State(Scope.Thread) public class ArrayOptimizeTest { private static final int maxSize = 1000; // 测试循环次数 private static final int operationSize = 100; // 操做次数 private static ArrayList<Integer> arrayList; private static LinkedList<Integer> linkedList; public static void main(String[] args) throws RunnerException { // 启动基准测试 Options opt = new OptionsBuilder() .include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类 .build(); new Runner(opt).run(); // 执行测试 } @Setup public void init() { // 启动执行事件 arrayList = new ArrayList<Integer>(); linkedList = new LinkedList<Integer>(); for (int i = 0; i < maxSize; i++) { arrayList.add(i); linkedList.add(i); } } @Benchmark public void findArrayByEnd() { for (int i = (maxSize - operationSize); i < maxSize; i++) { arrayList.get(i); } } @Benchmark public void findLinkedyByEnd() { for (int i = (maxSize - operationSize); i < maxSize; i++) { linkedList.get(i); } } }
以上程序的执行结果为:
从上述结果能够看出,从尾部查询 100 个元素时 ArrayList
的平均执行时间比 LinkedList
平均执行成时间快了约 1839 倍。
接下来咱们再来测试一下,正常状况下咱们从头开始添加数组和链表的性能对比,测试代码以下:
import org.openjdk.jmh.annotations.*; import org.openjdk.jmh.infra.Blackhole; import org.openjdk.jmh.runner.Runner; import org.openjdk.jmh.runner.RunnerException; import org.openjdk.jmh.runner.options.Options; import org.openjdk.jmh.runner.options.OptionsBuilder; import java.util.ArrayList; import java.util.LinkedList; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.AverageTime) // 测试完成时间 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热次数和时间 @Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // 测试次数和时间 @Fork(1) // fork 1 个线程 @State(Scope.Thread) public class ArrayOptimizeTest { private static final int maxSize = 1000; // 测试循环次数 private static ArrayList<Integer> arrayList; private static LinkedList<Integer> linkedList; public static void main(String[] args) throws RunnerException { // 启动基准测试 Options opt = new OptionsBuilder() .include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类 .build(); new Runner(opt).run(); // 执行测试 } @Benchmark public void addArray(Blackhole blackhole) { // 中间删数组表 arrayList = new ArrayList<Integer>(); for (int i = 0; i < maxSize; i++) { arrayList.add(i); } // 为了不 JIT 忽略未被使用的结果计算 blackhole.consume(arrayList); } @Benchmark public void addLinked(Blackhole blackhole) { // 中间删除链表 linkedList = new LinkedList<Integer>(); for (int i = 0; i < maxSize; i++) { linkedList.add(i); } // 为了不 JIT 忽略未被使用的结果计算 blackhole.consume(linkedList); } }
以上程序的执行结果为:
接下来,咱们将添加的次数调至 1w,测试结果以下:
最后,咱们再将添加次数调至 10w,测试结果以下:
从以上结果能够看出在正常状况下,从头部依次开始添加元素时,他们性能差异不大。
本文咱们介绍了数组的概念以及它的优缺点,同时还介绍了单向链表、双向链表及循环链表的概念以及链表的优缺点。咱们在最后的评测中能够看出,当咱们正常从头部依次添加元素时,链表和数组的性能差不不大。但当数据初始化完成以后,咱们再进行插入操做时,尤为是从头部插入时,由于数组要移动以后的全部元素,所以性能要比链表低不少;但在查询时性能恰好相反,由于链表要遍历查询,而且 LinkedList
是双向链表,因此在中间查询时性能要比数组查询慢了上万倍(查询 100 个元素),而两头查询(首部和尾部)时,链表也比数组慢了将近 1000 多倍(查询 100 个元素),所以在查询比较多的场景中,咱们要尽可能使用数组,而在添加和删除操做比较多时,咱们应该使用链表结构。
数组和链表的操做时间复杂度,以下表所示:
数组 | 链表 | |
---|---|---|
查询 | O(1) | O(n) |
插入 | O(n) | O(1) |
删除 | O(n) | O(1) |