|
|
数据结构在程序中非常重要。简单来说，数据结构就是在计算机语言如何组织和操作数据。在C中，数据结构与操作是分离的，因为Java是面向对象的，因此对常用的数据结构进行了封装。这一章我们讨论简单的有序数据结构（在Java中叫容器）的使用。
|
|
|
|
|
|
## 1. Collection
|
|
|
|
|
|
> A collection is a container object that holds a group of objects, often referred to as elements. The Java Collections Framework supports three types of collections, named lists, sets, and maps.
|
|
|
>
|
|
|
> collection 是一个存放一组对象（元素）的容器。Java的Collection框架包括 List（列表，有点像Array），Set（集合，无序且唯一）和Map（key-value的对应关系）。
|
|
|
|
|
|
|
|
|
|
|
|
上图中，虚线部分是接口关系；实线部分是类的关系。Set、List、Queue都以接口的方式给出的。
|
|
|
|
|
|
引用网上一个比较完整的类图：[容器框架概述](https://blog.csdn.net/WZD2012/article/details/73245493)
|
|
|
|
|
|
|
|
|
|
|
|
上面的关系描述看起来比较复杂，大家尽量去理解就可以了，不用去记。下面会使用到一部分这个图的关系进行分析。
|
|
|
|
|
|
### 1.1. Collection接口
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Collection接口由Iterator接口扩展而来。Iterator可以翻译成迭代器还是什么，反正看接口可以大概理解成一个链表的操作接口。
|
|
|
|
|
|
了解Collection接口中的基本操作就可以了，一般是add、clear、contains、equals、remove这些。你会发现和前面学习的ArrayList的操作非常类似，仔细看类图可以发现ArrayList是间接实现了 Collection 这个接口。
|
|
|
|
|
|
**注意：Collection 接口并不包含数据有序性质的操作，因此该接口并不保证存储数据的有序性，可能是无序的，就是说，没有Index的概念。**
|
|
|
|
|
|
### 1.2. List接口
|
|
|
|
|
|
> A list stores elements in a sequential order, and allows the user to specify where the element is stored. The user can access the elements by index.
|
|
|
>
|
|
|
> List 接口存放的元素是有序的，并且允许用户指定元素的存放位置。可以通过 index 对元素进行访问。
|
|
|
|
|
|
|
|
|
|
|
|
List接口在Collection 的基础上更进一步，加入了有序操作的能力（有index的操作了）。注意这里有listIterator的函数接口，这是Iterator接口的扩展，因此具备有序遍历的特性。
|
|
|
|
|
|
关于listIterator的接口如下：
|
|
|
|
|
|
|
|
|
|
|
|
这个接口现阶段不用关心太多，只需要知道List的遍历是有序的就可以了，例如使用特有的for循环，可以保证元素是有序取出的。
|
|
|
|
|
|
## 2. ArrayList 和 LinkedList
|
|
|
|
|
|
> The ArrayList class and the LinkedList class are concrete implementations of the List interface. Which of the two classes you use depends on your specific needs. If you need to support random access through an index without inserting or removing elements from any place other than the end, ArrayList offers the most efficient collection. If, however, your application requires the insertion or deletion of elements from any place in the list, you should choose LinkedList. A list can grow or shrink dynamically. An array is fixed once it is created. If your application does not require insertion or deletion of elements, the most efficient data structure is the array.
|
|
|
>
|
|
|
> 这两个类的使用几乎完全一致，只不过ArrayList是对读进行优化的（通过Index访问元素），LinkedList是对写进行优化的（通过Index插入和修改元素）。
|
|
|
|
|
|
```java
|
|
|
import java.util.*;
|
|
|
|
|
|
public class TestArrayAndLinkedList {
|
|
|
public static void main(String[] args) {
|
|
|
List<Integer> arrayList = new ArrayList<Integer>(); // List是一个接口哦，
|
|
|
arrayList.add(1); // 1 is autoboxed to new Integer(1)
|
|
|
arrayList.add(2);
|
|
|
arrayList.add(3);
|
|
|
arrayList.add(1);
|
|
|
arrayList.add(4);
|
|
|
arrayList.add(0, 10);
|
|
|
arrayList.add(3, 30);
|
|
|
|
|
|
System.out.println("A list of integers in the array list:");
|
|
|
System.out.println(arrayList);
|
|
|
|
|
|
LinkedList<Object> linkedList = new LinkedList(arrayList);
|
|
|
linkedList.add(1, "red");
|
|
|
linkedList.removeLast();
|
|
|
linkedList.addFirst("green");
|
|
|
|
|
|
System.out.println("Display the linked list backward:");
|
|
|
for (int i = linkedList.size() - 1; i >= 0; i--) {
|
|
|
System.out.print(linkedList.get(i) + " ");
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
```
|
|
|
|
|
|
这个例子可以看到，这两个类型的使用几乎完全一样。
|
|
|
|
|
|
这里注意：`List<Integer> arrayList = new ArrayList<Integer>();`真实的对象是ArrayList，引用变量的类型是`List`；看看本章节的开始部分，List是一个接口，ArryList实现了List这个接口，因此可以使用接口来操作ArrayList对象。
|
|
|
|
|
|
```java
|
|
|
AbstractList<Integer> arrayList = new ArrayList<Integer>();
|
|
|
ArrayList<Integer> arrayList = new ArrayList<Integer>();
|
|
|
```
|
|
|
|
|
|
上面这样的赋值也是没有问题的，因为后面的代码只使用了List接口的功能（能力）。但是如果这样：
|
|
|
|
|
|
```java
|
|
|
Collection<Integer> arrayList = new ArrayList<Integer>();
|
|
|
arrayList.add(1); // 1 is autoboxed to new Integer(1)
|
|
|
arrayList.add(2); // 正确：使用Collection接口描述的add函数；
|
|
|
arrayList.add(3); // 正确：使用Collection接口描述的add函数；
|
|
|
arrayList.add(1); // 正确：使用Collection接口描述的add函数；
|
|
|
arrayList.add(4); // 正确：使用Collection接口描述的add函数；
|
|
|
arrayList.add(0, 10); // 错误：Collection 没有这样的函数能力描述
|
|
|
arrayList.add(3, 30); // 错误：Collection 没有这样的函数能力描述
|
|
|
```
|
|
|
|
|
|
那么`arrayList.add(0, 10);`这样的代码将错误，因为能力描述是Coolection，虽然对象是ArrayList具备`add(0, 10)`这样的能力，但是arrayList的变量类型是Collection，并不知道对象有这样的能力，因此如果要使用`add(0, 10)`这样的能力，需要进行类型转换：
|
|
|
|
|
|
```java
|
|
|
Collection<Integer> arrayList = new ArrayList<Integer>();
|
|
|
arrayList.add(1); // 1 is autoboxed to new Integer(1)
|
|
|
arrayList.add(2);
|
|
|
arrayList.add(3);
|
|
|
arrayList.add(1);
|
|
|
arrayList.add(4);
|
|
|
|
|
|
if (arrayList instanceof List) {
|
|
|
List list = (List) arrayList;
|
|
|
list.add(0,10);
|
|
|
list.add(3,30);
|
|
|
}
|
|
|
```
|
|
|
|
|
|
对象的类型任然是一个ArrayList，变量arrayList 和 list 都引用同一个对象；arrayList变量的类型是 Collection 因此不能使用 `add(0, 10)` 这样的能力（Collection中没有这样的能力描述）；list 变量的类型是 List 因此可以使用 `add(0, 10)` 这样的能力（List中有这样的能力描述）。
|
|
|
|
|
|
## 3. Stack
|
|
|
|
|
|
|
|
|
|
|
|
关于Stack的使用这里不做过多的描述，前面有这样的例子。只不过这个类型是Java的SDK提供的，可以直接使用。我们看看下面的代码：
|
|
|
|
|
|
```java
|
|
|
import java.util.Stack;
|
|
|
public class Test {
|
|
|
|
|
|
public static void main(String[] args) {
|
|
|
Stack<Integer> stack = new Stack();
|
|
|
stack.add(1);
|
|
|
stack.add(2);
|
|
|
stack.add(3);
|
|
|
stack.add(0, 0);
|
|
|
|
|
|
for (Integer i : stack) {
|
|
|
System.out.println(i);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
```
|
|
|
|
|
|
这段代码其实把Stack当成了List来使用，看看本章开始的类图关系，就知道了Stack其实是实现了List的接口的，或者是这样：
|
|
|
|
|
|
```java
|
|
|
import java.util.List;
|
|
|
import java.util.Stack;
|
|
|
public class Test {
|
|
|
|
|
|
public static void main(String[] args) {
|
|
|
List<Integer> stack = new Stack();
|
|
|
stack.add(1);
|
|
|
stack.add(2);
|
|
|
stack.add(3);
|
|
|
stack.add(0, 0);
|
|
|
stack.remove(3);
|
|
|
|
|
|
for (Integer i : stack) {
|
|
|
System.out.println(i);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
```
|
|
|
|
|
|
这样也不会出错，想一想为什么。
|
|
|
|
|
|
|
|
|
|
|
|
## 4. Queue
|
|
|
|
|
|
|
|
|
|
|
|
```java
|
|
|
import java.util.*;
|
|
|
|
|
|
public class PriorityQueueDemo {
|
|
|
public static void main(String[] args) {
|
|
|
PriorityQueue<String> queue1 = new PriorityQueue<String>();
|
|
|
queue1.offer("Oklahoma");
|
|
|
queue1.offer("Indiana");
|
|
|
queue1.offer("Georgia");
|
|
|
queue1.offer("Texas");
|
|
|
|
|
|
System.out.println("Priority queue using Comparable:");
|
|
|
while (queue1.size() > 0) {
|
|
|
System.out.print(queue1.remove() + " ");
|
|
|
}
|
|
|
|
|
|
PriorityQueue<String> queue2 = new PriorityQueue<String>(4, Collections.reverseOrder());
|
|
|
queue2.offer("Oklahoma");
|
|
|
queue2.offer("Indiana");
|
|
|
queue2.offer("Georgia");
|
|
|
queue2.offer("Texas");
|
|
|
|
|
|
System.out.println("\nPriority queue using Comparator:");
|
|
|
while (queue2.size() > 0) {
|
|
|
System.out.print(queue2.remove() + " ");
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
```
|
|
|
|
|
|
这个例子很有意思，作为了解不需要大家掌握。PriorityQueue在添加数据的时候会对数据进行排序，因此如果取队列，取出的顺序并不是按照先进先出的原则的，而是排序后，最小的先被取出。因此结果是：
|
|
|
|
|
|
```
|
|
|
Georgia Indiana Oklahoma Texas
|
|
|
```
|
|
|
|
|
|
后面一段在构建队列的时候，有个参数`Collections.reverseOrder()`表示反向，因此结果就变成了：
|
|
|
|
|
|
```
|
|
|
Texas Oklahoma Indiana Georgia
|
|
|
```
|
|
|
|
|
|
如果严格按照队列的先进先出，应该使用非排序的队列，例如：
|
|
|
|
|
|
```java
|
|
|
import java.util.*;
|
|
|
import java.util.concurrent.LinkedBlockingQueue;
|
|
|
|
|
|
public class PriorityQueueDemo {
|
|
|
public static void main(String[] args) {
|
|
|
Queue<String> queue1 = new LinkedBlockingQueue();
|
|
|
queue1.offer("Oklahoma");
|
|
|
queue1.offer("Indiana");
|
|
|
queue1.offer("Georgia");
|
|
|
queue1.offer("Texas");
|
|
|
|
|
|
while (queue1.size() > 0) {
|
|
|
System.out.print(queue1.remove() + " ");
|
|
|
}
|
|
|
|
|
|
}
|
|
|
}
|
|
|
```
|
|
|
|
|
|
这样的结果就是先进先出了：
|
|
|
|
|
|
```
|
|
|
Oklahoma Indiana Georgia Texas
|
|
|
```
|
|
|
|
|
|
## 5. 本章重点
|
|
|
|
|
|
1. 本章大多类容作为了解，通过本章，可以大约了解Java中关于接口和抽象类的使用方式。考试中可能会出现List是类还是接口这样的题，或者`List<Integer> list = new ArrayList();` 这样的题是否正确。如果大家大约了解本章开始的类图就可以有正确答案了。
|
|
|
2. ArrayList的操作需要掌握，前面已经说了，其他的作为了解就可以了。
|
|
|
|