抽象数据类型

设计高效数据结构的第一步是建立一个高效的数学模型来存储数据。之后，我们需要选择访问和修改数据的方法。这个模型连同这些方法被称为抽象数据类型（ADT）。

通过 ADT，我们可以涵盖数据结构的所有功能；它告诉我们希望对这些数据结构执行哪些操作。然而，ADT 并不涉及实现过程、内存管理或所采用的算法细节。

正如我们之前提到的，高效的算法依赖于高效的数据结构。在决定使用哪种算法时，我们可能很感兴趣，但在 ADT 阶段并不需要考虑这一点。

例如，如果我们实现一个字典 ADT，可能希望提供 search(word) 方法。在项目初期，我们必须明确这一点，而这一阶段所做的工作本质上就是定义 ADT。

在 Java 中，用于实现 ADT 的数据结构是一组用于存储数据的变量集合。从实现层面看，ADT 对应于 Java 接口，而 ADT 数据结构则对应于实现该接口的类。

在 ADT 阶段，正确建模结构至关重要。我们需要理解其重要性。当我们编写代码时，实际上是在用所选编程语言向计算机发出指令。此时，通过编程语言进行的人类交流也起着关键作用。

即使编译器能够理解某个语法结构，并不意味着程序员也能理解它。因此，ADT 应该清晰且简洁，同时必须易于人类阅读和理解。

因为人类思维存在诸多局限，所有代码都应详细注释，以确保使用特定算法的目的明确清楚。以栈算法为例，它用于处理编译器中的嵌套结构。如果结构过于复杂，人类难以跟踪。这在数据结构中尤其明显：深层嵌套的结构可能难以理解。

虽然对人类而言结构模糊不清，但对编译器来说却是清晰且可理解的。
考虑一个简单的除法算法：

1public class TestingDemo {
2    // 对人类来说难以理解的代码，尽管编译器能清楚识别
3    public static void main(String[] args) {
4        double a, b, c;
5        a = 20;
6        b = 10;
7        c = 5;
8        System.out.println(a/b/c);
9    }
10}

运行结果如下：

10.4

尽管人类无法在没有括号的情况下理解除法的运算顺序，但编译器不会报错，仍能给出正确结果。

另一种写法是将上述第 8 行代码加上括号：

1System.out.println((a / b) / c);

这种写法对人类更易理解。

使用数组时会遇到困难，因为它们的大小固定，添加或删除数据并不总是容易。数组是顺序排列的，因此在两个元素之间插入或删除元素时，需要移动其他元素，整个操作会使处理器负担加重。

虽然 ArrayList 也是顺序排列的，处理器执行的步骤与数组类似，但由于 ADT 的支持，它仍然更容易处理。

ArrayList.add() 方法

ArrayList 是一种 ADT，提供了一个泛型类，包含许多用于处理数据集合的有用方法。它还支持多种数据类型。通过使用 ArrayList 的方法，我们可以轻松地添加、删除或修改任意元素。此外，还可以获取列表的大小，并据此使用循环结构。

ArrayList 的声明方式如下：

1ArrayList<T> arrayList = new ArrayList<T>();

其中，T 是数据类型。它不是基本数据类型，而是包装类。下面是一些具体实现示例：

1import java.util.ArrayList;
2
3// ArrayListExamples
4class Main {
5    public static void main(String[] args) {
6        /* ArrayList 示例
7         * ArrayList 是一种 ADT，提供一个泛型类，具有许多用于处理数据集合的有用方法。
8         * 它也支持多种数据类型。
9         * ArrayList 的声明方式如下：
10         * ArrayList<T> arrayList = new ArrayList<T>();
11         * 其中 T 是数据类型。 */
12        ArrayList<String> arrayList = new ArrayList<String>();
13        arrayList.add("index");
14        arrayList.add("about");
15        arrayList.add("contact");
16        arrayList.add("products");
17        arrayList.add("sellers");
18        for (int i = 0; i < arrayList.size(); i++) {
19            System.out.println(arrayList.get(i));
20        }
21    }
22}

我们添加了几项元素，输出非常简单：

1index
2about
3contact
4products
5sellers

在上述代码中：

• 第 12 行：可以看出 ArrayList 的优势，它可以应用于多种数据类型，如本例中的 String。
• 第 13 至 17 行：它还提供了许多有用的函数，比如 add() 方法。

ArrayList.remove() 方法

接下来，我们尝试移除一些元素并查看输出，以了解其工作原理。

1import java.util.ArrayList;
2
3// ArrayListExamples
4class Main {
5    public static void main(String[] args) {
6        /* ArrayList 示例
7         * ArrayList 是一种 ADT，提供一个泛型类，具有许多用于处理数据集合的有用方法。
8         * 它也支持多种数据类型。
9         * ArrayList 的声明方式如下：
10         * ArrayList<T> arrayList = new ArrayList<T>();
11         * 其中 T 是数据类型。 */
12        ArrayList<String> arrayList = new ArrayList<String>();
13        // 添加了五个项目
14        arrayList.add("index");
15        arrayList.add("about");
16        arrayList.add("contact");
17        arrayList.add("products");
18        arrayList.add("sellers");
19        // 移除了两个项目
20        arrayList.remove("products");
21        arrayList.remove("sellers");
22
23        for (int i = 0; i < arrayList.size(); i++) {
24            System.out.println(arrayList.get(i));
25        }
26    }
27}

输出结果为：

1index
2about
3contact

在上述代码中，可以看到 remove() 方法使用起来同样简单直观，便于程序员理解和使用。

ArrayList.set() 方法

接下来，我们将列表的第一个元素从 index 修改为 home。

1import java.util.ArrayList;
2
3// ArrayListExamples
4class Main {
5    public static void main(String[] args) {
6        /* ArrayList 示例
7         * ArrayList 是一种 ADT，提供一个泛型类，具有许多用于处理数据集合的有用方法。
8         * 它也支持多种数据类型。
9         * ArrayList 的声明方式如下：
10         * ArrayList<T> arrayList = new ArrayList<T>();
11         * 其中 T 是数据类型。 */
12        ArrayList<String> arrayList = new ArrayList<String>();
13        // 添加了五个项目
14        arrayList.add("index");
15        arrayList.add("about");
16        arrayList.add("contact");
17        arrayList.add("products");
18        arrayList.add("sellers");
19        // 移除了两个项目
20        arrayList.remove("products");
21        arrayList.remove("sellers");
22        // 将第一个索引页改为 home
23        arrayList.set(0, "home");
24        for (int i = 0; i < arrayList.size(); i++) {
25            System.out.println(arrayList.get(i));
26        }
27    }
28}

我们成功修改了值。运行上述代码后得到以下输出：

1home
2about
3contact

在存储数据后，对其进行排序极为重要。在下面最后一个 ArrayList 代码片段中，我们将对数据结构进行排序。

1import java.util.ArrayList;
2import java.util.Collections;
3
4// ArrayListExamples
5class Main {
6    public static void main(String[] args) {
7        /* ArrayList 示例
8         * ArrayList 是一种 ADT，提供一个泛型类，具有许多用于处理数据集合的有用方法。
9         * 它也支持多种数据类型。
10         * ArrayList 的声明方式如下：
11         * ArrayList<T> arrayList = new ArrayList<T>();
12         * 其中 T 是数据类型。 */
13        ArrayList<String> arrayList = new ArrayList<String>();
14        // 添加了五个项目
15        arrayList.add("index");
16        arrayList.add("about");
17        arrayList.add("contact");
18        arrayList.add("products");
19        arrayList.add("sellers");
20        // 移除了两个项目
21        arrayList.remove("products");
22        arrayList.remove("sellers");
23
24        // 将第一个索引页改为 home
25        arrayList.set(0, "home");
26        System.out.println("未排序列表：");
27        for (int i = 0; i < arrayList.size(); i++) {
28            System.out.println(arrayList.get(i));
29        }
30        System.out.println("现在开始排序列表：");
31        Collections.sort(arrayList);
32
33        for (int i = 0; i < arrayList.size(); i++) {
34            System.out.println(arrayList.get(i));
35        }
36        System.out.println();
37
38        // 我们应使用包装类而非基本数据类型
39        ArrayList<Double> doubleList = new ArrayList<Double>();
40        doubleList.add(456.45);
41        doubleList.add(12.123);
42        doubleList.add(78945.0258);
43        System.out.println("未排序列表：");
44        for (int i = 0; i < doubleList.size(); i++) {
45            System.out.println(doubleList.get(i));
46        }
47        System.out.println("现在开始排序列表：");
48        Collections.sort(doubleList);
49        for (int i = 0; i < doubleList.size(); i++) {
50            System.out.println(doubleList.get(i));
51        }
52    }
53}

在上述代码中，我们首先显示未排序的结果，然后展示排序后的输出。

1未排序列表：
2home
3about
4contact
5现在开始排序列表：
6about
7contact
8home
9
10未排序列表：
11456.45
1212.123
1378945.0258
14现在开始排序列表：
1512.123
16456.45
1778945.0258

在代码中，我们进一步展示了 ArrayList 的实用性。在创建 arrayList 和 doubleList 后，我们向其中添加了一些数据成员：

• 第 2 行：导入 Collections 包以使用 sort() 方法。
• 第 30 行：使用 sort() 方法对 arrayList 的元素进行排序。
• 第 46 行：使用 sort() 方法对 doubleList 的元素进行排序。