共计 3030 个字符，预计需要花费 8 分钟才能阅读完成。
数组
数组是最罕用的数据结构，创立数组必须要内存中一块 间断 的空间，并且数组中必须寄存 雷同 的数据类型。比方咱们创立一个长度为 10，数据类型为整型的数组，在内存中的地址是从 1000 开始，那么它在内存中的存储格局如下。
因为每个整型数据占据 4 个字节的内存空间，因而整个数组的内存空间地址是 1000～1039，依据这个，咱们就能够轻易算出数组中每个数据的内存下标地址。利用这个个性，咱们只有晓得了数组下标，也就是数据在数组中的地位，比方下标 2，就能够计算失去这个数据在内存中的地位 1008，从而对这个地位的数据 241 进行疾速读写访问，工夫复杂度为 O(1)。
随机疾速读写是数组的一个重要个性，然而要随机拜访数据，必须晓得数据在数组中的下标。如果咱们只是晓得数据的值，想要在数组中找到这个值，那么就只能遍历整个数组，工夫复杂度为 O(N)。
链表
不同于数组必须要间断的内存空间，链表能够应用零散的内存空间存储数据。不过，因为链表在内存中的数据不是间断的，所以链表中的每个数据元素都必须蕴含一个指向下一个数据元素的内存地址指针。如下图，链表的每个元素蕴含两局部，一部分是数据，一部分是指向下一个元素的地址指针。最初一个元素指向 null，示意链表到此为止。
因为链表是不间断存储的，要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是 O(N)。
然而正因为链表是不间断存储的，所以在链表中插入或者删除一个数据是非常容易的，只有找到要插入（删除）的地位，批改链表指针就能够了。如图，想在 b 和 c 之间插入一个元素 x，只须要将 b 指向 c 的指针批改为指向 x，而后将 x 的指针指向 c 就能够了。
相比在链表中轻易插入、删除一个元素这种简略的操作，如果咱们要想在数组中插入、删除一个数据，就会扭转数组间断内存空间的大小，须要重新分配内存空间，这样要简单得多。
Hash 表
后面说过，对数组中的数据进行快速访问必须要通过数组的下标，工夫复杂度为 O(1)。如果只晓得数据或者数据中的局部内容，想在数组中找到这个数据，还是须要遍历数组，工夫复杂度为 O(N)。
事实上，晓得局部数据查找残缺数据的需要在软件开发中会常常用到，比方晓得了商品 ID，想要查找残缺的商品信息；晓得了词条名称，想要查找百科词条中的详细信息等。
这类场景就须要用到 Hash 表这种数据结构。Hash 表中数据以 Key、Value 的形式存储，下面例子中，商品 ID 和词条名称就是 Key，商品信息和词条详细信息就是 Value。存储的时候将 Key、Value 写入 Hash 表，读取的时候，只须要提供 Key，就能够疾速查找到 Value。
Hash 表的物理存储其实是一个数组，如果咱们可能依据 Key 计算出数组下标，那么就能够疾速在数组中查找到须要的 Key 和 Value。许多编程语言反对取得任意对象的 HashCode，比方 Java 语言中 HashCode 办法蕴含在根对象 Object 中，其返回值是一个 Int。咱们能够利用这个 Int 类型的 HashCode 计算数组下标。最简略的办法就是余数法，应用 Hash 表的数组长度对 HashCode 求余，余数即为 Hash 表数组的下标，应用这个下标就能够间接拜访失去 Hash 表中存储的 Key、Value。
上图这个例子中，Key 是字符串 abc，Value 是字符串 hello。咱们先计算 Key 的哈希值，失去 101 这样一个整型值。而后用 101 对 8 取模，这个 8 是哈希表数组的长度。101 对 8 取模余 5，这个 5 就是数组的下标，这样就能够把 (“abc”,“hello”) 这样一个 Key、Value 值存储在下标为 5 的数组记录中。
当咱们要读取数据的时候，只有给定 Key abc，还是用这样一个算法过程，先求取它的 HashCode 101，而后再对 8 取模，因为数组的长度不变，对 8 取模当前仍然是余 5，那么咱们到数组下标中去找 5 的这个地位，就能够找到后面存储进去的 abc 对应的 Value 值。
然而如果不同的 Key 计算出来的数组下标雷同怎么办？HashCode101 对 8 取模余数是 5，HashCode109 对 8 取模余数还是 5，也就是说，不同的 Key 有可能计算失去雷同的数组下标，这就是所谓的 Hash 抵触，解决 Hash 抵触罕用的办法是链表法。
事实上，(“abc”,“hello”)这样的 Key、Value 数据并不会间接存储在 Hash 表的数组中，因为数组要求存储固定数据类型，次要目标是每个数组元素中要寄存固定长度的数据。所以，数组中存储的是 Key、Value 数据元素的地址指针。一旦产生 Hash 抵触，只须要将雷同下标，不同 Key 的数据元素增加到这个链表就能够了。查找的时候再遍历这个链表，匹配正确的 Key。
如下图：
因为有 Hash 抵触的存在，所以“Hash 表的工夫复杂度为什么是 O(1)？”这句话并不谨严，极其状况下，如果所有 Key 的数组下标都抵触，那么 Hash 表就进化为一条链表，查问的工夫复杂度是 O(N)。然而作为一个面试题，“Hash 表的工夫复杂度为什么是 O(1)”是没有问题的。
栈
数组和链表都被称为线性表，因为外面的数据是依照线性组织寄存的，每个数据元素的后面只能有一个（前驱）数据元素，前面也只能有一个（后继）数据元素，所以称为线性表。然而对数组和链表的操作能够是随机的，能够对其上任何元素进行操作，如果对操作形式加以限度，就造成了新的数据结构。
栈就是在线性表的根底上加了这样的操作限度条件：前面增加的数据，在删除的时候必须先删除，即通常所说的“后进先出”。咱们能够把栈能够设想成一个大桶，往桶外面放食物，一层一层放进去，如果要吃的时候，必须从最下面一层吃，吃了几层后，再往里放食物，还是从以后的最下面一层放起。
栈在线性表的根底上减少了操作限度，具体实现的时候，因为栈不须要随机拜访、也不须要在两头增加、删除数据，所以能够用数组实现，也能够用链表实现。那么在程序表的根底上减少操作限度有什么益处呢？
咱们上篇提到的程序运行过程中，办法的调用须要用栈来治理每个办法的工作区，这样，不论办法如何嵌套调用，栈顶元素始终是以后正在执行的办法的工作区。这样，事件就简略了。而简略，正是咱们做软件开发应该致力谋求的一个指标。
队列
队列也是一种操作受限的线性表，栈是后进先出，而队列是先进先出。
在软件运行期，常常会遇到资源有余的状况：提交工作申请线程池执行，然而线程曾经用完了，工作须要放入队列，先进先出排队执行；线程在运行中须要拜访数据库，数据库连贯无限，曾经用完了，线程进入阻塞队列，当有数据库连贯开释的时候，从阻塞队列头部唤醒一个线程，出队列取得连贯拜访数据库。
我在下面讲堆栈的时候，举了一个大桶放食物的例子，事实上，如果用这种形式寄存食物，有可能最底下食物永远都吃不到，最初过期了。
事实中也是如此，超市在货架上摆放食品的时候，其实是依照队列摆放的，而不是堆栈摆放的。工作人员在上架新食品的时候，总是把新食品摆在前面，使食品成为一个队列，以便让以前上架的食品被尽快卖出。
树
数组、链表、栈、队列都是线性表，也就是每个数据元素都只有一个前驱，一个后继。而树则是非线性表，树是这样的。
软件开发中，也有很多中央用到树，比方咱们要开发一个 OA 零碎，部门的组织构造就是一棵树；咱们编写的程序在编译的时候，第一步就是将程序代码生成形象语法树。传统上树的遍历应用递归的形式，而我集体更喜爱用设计模式中的组合模式进行树的遍历，具体我将会在设计模式局部具体探讨。
本文由 mdnice 多平台公布
