Java面试狂想曲之数据结构，又来送书了啦！

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系 的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行速度和存储效率。数据结构主要包含以下 4 种逻辑结构:

1. 线性结构:数据可以按照某种规则排列成线性的形式。
2. 集合结构:数据元素间除“同属于一个集合”外，没有其他的任何关系。
3. 树形结构:数据元素之间呈现倒立的树形结构，每个元素有一个双亲，每个元素有 0 个 或多个孩子，数据元素间呈现一对多的关系。
4. 网状结构:每个数据元素都有可能有多个相邻的数据元素，数据元素之间呈现一种多对多的关系。

在 Java 企业级开发中，存在各种各样的数据结构，这些数据结构被 JDK 和各种 Java 框架实现。同时，数据结构也是互联网公司面试中常见的考点。熟练掌握数据结构的知识有助于开发人员更好 地学习 JDK 和各种 Java 框架的核心代码，提升面试通过率。

2.1 线性表

2.1.1 线性表的定义

线性表是由 N 个相同数据类型的数据元素组成的有限序列，其中除了第一个数据元素外， 每个元素有且仅有一个直接前驱结点，除最后一个数据元素外，每个元素有且仅有一个直接后继结点。

线性表数据类型主要包括两个方面:数据元素集合和该数据元素集合上的操作集合。数据元素集合可以表示为 A0,A1,A2,...,An-1 大小为 N 的数据集合。

操作集合包括以下操作:

1. 向线性表插入元素。
2. 从线性表删除元素。
3. 从线性表查找元素。
4. 判断线性表是否为空。
5. 求线性表的元素个数。

2.1.2 线性表的类型

线性表是一种逻辑结构，这种逻辑结构在计算机中的表现形式(存储结构)主要有以下两种:

1. 线性存储:用顺序结构存储的线性表叫作顺序线性表，一般称作顺序表。顺序表一般通 过高级语言中的数组类型实现。
2. 链式存储:用链式结构存储的线性表叫作链式线性表，一般称作链表。链表通常是通过 定义结点的方式，通过指针(Java 语言中使用的是引用)将各个数据元素和数据元素之间的关系 体现出来的。

2.1.3 线性表的抽象类型的定义

由于线性表有顺序表和链表两种实现形式，因此可以通过软件工程的设计思想对线性表这种 数据结构进行抽象，由不同的子类生成不同的线性表的实现。

本节将定义一个 List 接口，该接口定义了线性表的规范，即定义线性表需要实现的基本操作， 这些操作包括插入元素、删除元素、查找元素、判断表是否为空和查询线性表元素个数。List 接口 代码如下:

2.1.4 线性表常见面试考点

1. 线性表的概念。
2. 线性表的存储方式和实现方式。
3. 在线性表中操作元素的时间复杂度。

2.2 顺序表

顺序表采用顺序结构存储数据，在 Java 语言中常用的顺序存储结构是数组。顺序表如图 2-1 所示。

2.2.1 顺序表添加元素

在顺序表指定位置添加元素，首先需要确定指定位置是否已经有元素。如果指定位置没有元素，就直接加入元素，如图 2-2 所示。

如果指定位置已经有元素，就需要将指定位置处的元素及其后续元素依次向后移动，将指定位置空出后，插入指定元素，如图 2-3 所示。

2.2.2 顺序表查找元素

当顺序表按照索引查找元素时，将以 O(1)的时间复杂度查找到指定的元素，如图 2-4 所示。

顺序表按照元素值查询指定元素时，需要从第一个元素开始依次向后查找元素，直至找到指 定元素，查找的时间复杂度为 O(n)。查找 V5 元素的过程如图 2-5 所示。

2.2.3 顺序表删除元素

如果从顺序表删除的元素是末尾元素，就直接删除即可，如图 2-6 所示。

如果删除的元素并非末尾元素，就已删除元素后面的所有元素将依次向前移动，如图 2-7 所示。

2.2.5 顺序表常见面试考点

1. 顺序表的概念:顺序表是使用顺序结构存储的线性表。
2. 顺序表的存储:顺序表必须使用一块连续的存储空间存储数据。
3. 顺序表的优点:顺序表是使用顺序结构存储数据的，通过索引访问元素的时间复杂度为O(1)。
4. 顺序表的缺点:
   • 顺序表的存储空间必须是连续的，如果在顺序表中存储大量数据，那么对存储介质的容量是 一个挑战。
   • 顺序表的存储容量是有限的、固定的，超过顺序表的存储容量将无法进行数据存储。
   • 顺序表中按值查找元素的时间复杂度为 O(n)。
   • 在顺序表的非末尾位置添加元素将导致顺序表此位置后的元素依次向后移动。
   • 在顺序表的非末尾位置删除元素将导致顺序表此位置后的元素依次向前移动。
5. JDK 中的实现:JDK 中的 ArrayList 实现了顺序表，并提供了动态扩容等高级特性， ArrayList 的详细内容可参考本书 4.2 节。