网站备案被注销了怎么办,北京网站建设 标准型 新翼,域名网址区别,购买域名后如何建设网站这是我的第 215 期分享作者 | 王磊来源 | Java中文社群#xff08;ID#xff1a;javacn666#xff09;转载请联系授权#xff08;微信ID#xff1a;GG_Stone#xff09;数组和链表是程序中常用的两种数据结构#xff0c;也是面试中常考的面试题之一。然而对于很多人来说… 这是我的第 215 期分享作者 | 王磊来源 | Java中文社群IDjavacn666转载请联系授权微信IDGG_Stone数组和链表是程序中常用的两种数据结构也是面试中常考的面试题之一。然而对于很多人来说只是模糊的记得二者的区别可能还记得不一定对并且每次到了面试的时候都得把这些的概念拿出来背一遍才行未免有些麻烦。而本文则会从执行过程图以及性能评测等方面入手让你更加深入的理解和记忆二者的区别有了这次深入的学习之后相信会让你记忆深刻。数组在开始性能评测之前我们先来回顾一下什么是数组数组的定义如下数组Array是由相同类型的元素element的集合所组成的数据结构分配一块连续的内存来存储。利用元素的索引index可以计算出该元素对应的存储地址。最简单的数据结构类型是一维数组。例如索引为 0 到 9 的 32 位整数数组可作为在存储器地址 200020042008...2036 中存储 10个 变量因此索引为 i 的元素即在存储器中的 20004×i 地址。数组第一个元素的存储器地址称为第一地址或基础地址。简单来说数组就是由一块连续的内存组成的数据结构。这个概念中有一个关键词“连续”它反映了数组的一大特点就是它必须是由一个连续的内存组成的。数组的数据结构如下图所示数组添加的过程如下图所示数组的优点数组的“连续”特征决定了它的访问速度很快因为它是连续存储的所以这就决定了它的存储位置就是固定的因此它的访问速度就很快。比如现在有 10 个房间是按照年龄顺序入住的当我们知道第一房子住的是 20 岁的人之后那么我们就知道了第二个房子是 21 岁的人第五个房子是 24 岁的人......等等。数组的缺点祸兮福所倚福兮祸所伏。数组的连续性既有优点又有缺点优点上面已经说了而缺点它对内存的要求比较高必须要找到一块连续的内存才行。数组的另一个缺点就是插入和删除的效率比较慢假如我们在数组的非尾部插入或删除一个数据那么就要移动之后的所有数据这就会带来一定的性能开销删除的过程如下图所示数组还有一个缺点它的大小固定不能动态拓展。链表链表是和数组互补的一种数据结构它的定义如下链表Linked list是一种常见的基础数据结构是一种线性表但是并不会按线性的顺序存储数据而是在每一个节点里存到下一个节点的指针Pointer。由于不必须按顺序存储链表在插入的时候可以达到 O(1) 的复杂度比另一种线性表顺序表快得多但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间而顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。也就说链表是一个无需连续内存存储的数据结构链表的元素有两个属性一个是元素的值另一个是指针此指针标记了下一个元素的地址。链表的数据结构如下图所示链表添加的过程如下图所示链表删除的过程如下图所示链表分类链表主要分为以下几类单向链表双向链表循环链表单向链表单向链表中包含两个域一个信息域和一个指针域。这个链接指向列表中的下一个节点而最后一个节点则指向一个空值我们上面所展示的链表就是单向链表。双向链表双向链表也叫双链表双向链表中不仅有指向后一个节点的指针还有指向前一个节点的指针这样可以从任何一个节点访问前一个节点当然也可以访问后一个节点以至整个链表。双向链表的结构如下图所示循环链表循环链表中第一个节点之前就是最后一个节点反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。循环链表的结构如下图所示为什么会有单、双链表之分有人可能会问既然已经有单向链表了那为什么还要双向链表呢双向链表有什么优势呢这个就要从链表的删除说起了如果单向链表要删除元素的话不但要找到删除的节点还要找到删除节点的上一个节点通常称之为前驱因为需要变更上一个节点中 next 的指针但又因为它是单向链表所以在删除的节点中并没有存储上一个节点的相关信息那么我们就需要再查询一遍链表以找到上一个节点这样就带来了一定的性能问题所以就有了双向链表。链表优点链表的优点大致可分为以下三个链表对内存的利用率比较高无需连续的内存空间即使有内存碎片也不影响链表的创建链表的插入和删除的速度很快无需像数组一样需要移动大量的元素链表大小不固定可以很方便的进行动态扩展。链表缺点链表的主要缺点是不能随机查找必须从第一个开始遍历查找效率比较低链表查询的时间复杂度是 O(n)。性能评测了解了数组和链表的基础知识之后接下来我们正式进入性能评测环节。在正式开始之前我们先来明确一下测试目标我们需要测试的点其实只有 6 个从头部/中间部分/尾部进行添加操作的性能测试从头部/中间部分/尾部开始查询的性能测试。因为添加操作和删除操作在执行时间层面基本是一致的比如数组添加需要移动后面的元素删除也同样是移动后面的元素而链表也是如此添加和删除都是改变自身和相连节点的信息因此我们就把添加和删除的测试合二为一用添加操作来进行测试。测试说明在 Java 语言中数组的代表为 ArrayList而链表的代表为 LinkedList因此我们就用这两个对象来进行测试本文我们将使用 Oracle 官方推荐 JMH 框架来进行测试点击查看更多关于 JMH 的内容本文测试环境是 JDK 1.8、MacMini、Idea 2020.1。1.头部添加性能测试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 ArrayListInteger arrayList;private static LinkedListInteger linkedList;public static void main(String[] args) throws RunnerException {// 启动基准测试Options opt new OptionsBuilder().include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类.build();new Runner(opt).run(); // 执行测试}Setuppublic void init() {// 启动执行事件arrayList new ArrayListInteger();linkedList new LinkedListInteger();for (int i 0; i maxSize; i) {arrayList.add(i);linkedList.add(i);}}Benchmarkpublic void addArrayByFirst(Blackhole blackhole) {for (int i 0; i operationSize; i) {arrayList.add(i, i);}// 为了避免 JIT 忽略未被使用的结果计算blackhole.consume(arrayList);}Benchmarkpublic 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 倍。2.中间添加性能测试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 ArrayListInteger arrayList;private static LinkedListInteger linkedList;public static void main(String[] args) throws RunnerException {// 启动基准测试Options opt new OptionsBuilder().include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类.build();new Runner(opt).run(); // 执行测试}Setuppublic void init() {// 启动执行事件arrayList new ArrayListInteger();linkedList new LinkedListInteger();for (int i 0; i maxSize; i) {arrayList.add(i);linkedList.add(i);}}Benchmarkpublic void addArrayByMiddle(Blackhole blackhole) {int startCount maxSize / 2; // 计算中间位置// 中间部分进行插入for (int i startCount; i (startCount operationSize); i) {arrayList.add(i, i);}// 为了避免 JIT 忽略未被使用的结果计算blackhole.consume(arrayList);}Benchmarkpublic 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 倍。3.尾部添加性能测试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 ArrayListInteger arrayList;private static LinkedListInteger linkedList;public static void main(String[] args) throws RunnerException {// 启动基准测试Options opt new OptionsBuilder().include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类.build();new Runner(opt).run(); // 执行测试}Setuppublic void init() {// 启动执行事件arrayList new ArrayListInteger();linkedList new LinkedListInteger();for (int i 0; i maxSize; i) {arrayList.add(i);linkedList.add(i);}}Benchmarkpublic 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);}Benchmarkpublic 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 倍。4.头部查询性能评测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 ArrayListInteger arrayList;private static LinkedListInteger linkedList;public static void main(String[] args) throws RunnerException {// 启动基准测试Options opt new OptionsBuilder().include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类.build();new Runner(opt).run(); // 执行测试}Setuppublic void init() {// 启动执行事件arrayList new ArrayListInteger();linkedList new LinkedListInteger();for (int i 0; i maxSize; i) {arrayList.add(i);linkedList.add(i);}}Benchmarkpublic void findArrayByFirst() {for (int i 0; i operationSize; i) {arrayList.get(i);}}Benchmarkpublic void findLinkedyByFirst() { for (int i 0; i operationSize; i) {linkedList.get(i);}}
}
以上程序的执行结果为从上述结果可以看出从头部查询 100 个元素时 ArrayList 的平均执行时间比 LinkedList 平均执行时间快了约 1990 倍。5.中间查询性能评测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 ArrayListInteger arrayList;private static LinkedListInteger linkedList;public static void main(String[] args) throws RunnerException {// 启动基准测试Options opt new OptionsBuilder().include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类.build();new Runner(opt).run(); // 执行测试}Setuppublic void init() {// 启动执行事件arrayList new ArrayListInteger();linkedList new LinkedListInteger();for (int i 0; i maxSize; i) {arrayList.add(i);linkedList.add(i);}}Benchmarkpublic void findArrayByMiddle() { int startCount maxSize / 2;int endCount startCount operationSize;for (int i startCount; i endCount; i) {arrayList.get(i);}}Benchmarkpublic void findLinkedyByMiddle() { int startCount maxSize / 2;int endCount startCount operationSize;for (int i startCount; i endCount; i) {linkedList.get(i);}}
}
以上程序的执行结果为从上述结果可以看出从中间查询 100 个元素时 ArrayList 的平均执行时间比 LinkedList 平均执行时间快了约 28089 倍真是恐怖。6.尾部查询性能评测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 ArrayListInteger arrayList;private static LinkedListInteger linkedList;public static void main(String[] args) throws RunnerException {// 启动基准测试Options opt new OptionsBuilder().include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类.build();new Runner(opt).run(); // 执行测试}Setuppublic void init() {// 启动执行事件arrayList new ArrayListInteger();linkedList new LinkedListInteger();for (int i 0; i maxSize; i) {arrayList.add(i);linkedList.add(i);}}Benchmarkpublic void findArrayByEnd() {for (int i (maxSize - operationSize); i maxSize; i) {arrayList.get(i);}}Benchmarkpublic void findLinkedyByEnd() { for (int i (maxSize - operationSize); i maxSize; i) {linkedList.get(i);}}
}
以上程序的执行结果为从上述结果可以看出从尾部查询 100 个元素时 ArrayList 的平均执行时间比 LinkedList 平均执行成时间快了约 1839 倍。7.扩展添加测试接下来我们再来测试一下正常情况下我们从头开始添加数组和链表的性能对比测试代码如下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 ArrayListInteger arrayList;private static LinkedListInteger linkedList;public static void main(String[] args) throws RunnerException {// 启动基准测试Options opt new OptionsBuilder().include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类.build();new Runner(opt).run(); // 执行测试}Benchmarkpublic void addArray(Blackhole blackhole) { // 中间删数组表arrayList new ArrayListInteger();for (int i 0; i maxSize; i) {arrayList.add(i);}// 为了避免 JIT 忽略未被使用的结果计算blackhole.consume(arrayList);}Benchmarkpublic void addLinked(Blackhole blackhole) { // 中间删除链表linkedList new LinkedListInteger();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)最后的话原创不易用心写好每篇文章若能看出来请给我一个「在看」鼓励吧。往期推荐
轻松学算法的秘密可视化算法网站汇总(附动图)50种Java编程技巧越早知道越好(建议收藏)关注下方二维码每一天都有干货点亮“在看”助我写出更多好文
