大家好，我是晓星航。今天为大家带来的是 java数据结构中List知识的讲解！😀

1. 预备知识-泛型(Generic)

1.1 泛型的引入

**问题：**我们之前实现过的顺序表，只能保存 int 类型的元素，如果现在需要保存 指向 Person 类型对象的引用的顺序表，请问应该如何解决？如果又需要保存指向 Book 对象类型的引用呢？

回答：

1. 首先，我们在学习多态过程中已知一个前提，基类的引用可以指向子类的对象。
2. 其次，我们也已知 Object 是 java 中所有类的祖先类。

那么，要解决上述问题，我们很自然的想到一个解决办法，将我们的顺序表的元素类型定义成 Object 类型，这样我们的 Object 类型的引用可以指向 Person 类型的对象或者指向 Book 类型的对象了。

示例代码：

public class MyArrayList {private Object[] array; // 保存顺序表的元素，即 Object 类型的引用private int size; // 保存顺序表内数据个数public void add(Object o) { 尾插 }public Object get(int index) {获取 index 位置的元素 }...
}

这样，我们可以就可以很自由的存储指向任意类型对象的引用到我们的顺序表了。

示例代码：

MyArrayList books = new MyArrayList();
for (int i = 0; i < 10; i++) {books.add(new Book()); // 尾插 10 本书到顺序表
}
MyArrayList people = new MyArrayList();
for (int i = 0; i < 10; i++) {people.add(new Person()); // 尾插 10 个人到顺序表
}

遗留问题：现在的 MyArrayList 虽然可以做到添加任意类型的引用到其中了，但遇到以下代码就会产生问题。

MyArrayList books = new MyArrayList();
books.add(new Book);
// 将 Object 类型转换为 Person 类型，需要类型转换才能成功
// 这里编译正确，但运行时会抛出异常 ClassCastException
Person person = (Person)books.get(0);

提示：问题暴露的越早，影响越小。编译期间的问题只会让开发者感觉到，运行期间的错误会让所有的软件使用者承受错误风险。

所以我们需要一种机制，可以 1. 增加编译期间的类型检查 2. 取消类型转换的使用 泛型就此诞生！

泛型的意义：

1. 自动对类型进行检查
2. 自动对类型进行强制类型的转换

1.2 泛型的分类

1. 泛型类
2. 泛型方法

1.3 泛型类的定义的简单演示

关于泛型类的定义，这里只是了解即可，我们重点学习泛型类的使用。

// 1. 尖括号 <> 是泛型的标志
// 2. E 是类型变量(Type Variable)，变量名一般要大写
// 3. E 在定义时是形参，代表的意思是 MyArrayList 最终传入的类型，但现在还不知道public class MyArrayList<E> {private E[] array;private int size;...}

注意： 泛型类可以一次有多个类型变量，用逗号分割。

1.4 泛型背后作用时期和背后的简单原理

1. 泛型是作用在编译期间的一种机制，即运行期间没有泛型的概念。
2. 泛型代码在运行期间，就是我们上面提到的，利用 Object 达到的效果（这里不是很准确，以后会做说明）。

1.5 泛型类的使用

// 定义了一个元素是 Book 引用的 MyArrayList
MyArrayList<Book> books = new MyArrayList<Book>();
books.add(new Book());// 会产生编译错误，Person 类型无法转换为 Book 类型
books.add(new Person());// 不需要做类型转换
Book book = book.get(0);// 不需要做类型转换
// 会产生编译错误，Book 类型无法转换为 Person 类型
Person person = book.get(0);

通过以上代码，我们可以看到泛型类的一个使用方式：只需要在所有类型后边跟尖括号，并且尖括号内是真正的类型，即 E 可以看作的最后的类型。

注意： Book 只能想象成 E 的类型，但实际上 E 的类型还是 Object。

1.6 泛型总结

1. 泛型是为了解决某些容器、算法等代码的通用性而引入，并且能在编译期间做类型检查。
2. 泛型利用的是 Object 是所有类的祖先类，并且父类的引用可以指向子类对象的特定而工作。
3. 泛型是一种编译期间的机制，即 MyArrayList 和 MyArrayList

在运行期间是一个类型

1. 泛型是 java 中的一种合法语法，标志就是尖括号 <>

2. 预备知识-包装类(Wrapper Class)

Object 引用可以指向任意类型的对象，但有例外出现了，8 种基本数据类型不是对象，那岂不是刚才的泛型机制要失效了？

实际上也确实如此，为了解决这个问题，java 引入了一类特殊的类，即这 8 种基本数据类型的包装类，在使用过程中，会将类似 int 这样的值包装到一个对象中去。

2.1 基本数据类型和包装类直接的对应关系

基本就是类型的首字母大写，除了 Integer 和 Character。

例如我们将String(字符串)转为int(整形)类型：

String str = "123";
int ret = Integer.valueOf(str);
System.out.println(ret + 1);

2.2 包装类的使用，装箱(boxing)和拆箱(unboxing)

装箱、装包：把简单类型–>包装类类型

拆箱、拆包：把包装类类型–>简单数据类型

int i = 10;// 装箱操作，新建一个 Integer 类型对象，将 i 的值放入对象的某个属性中
Integer ii = Integer.valueOf(i);
Integer ij = new Integer(i);// 拆箱操作，将 Integer 对象中的值取出，放到一个基本数据类型中
int j = ii.intValue();

2.3 自动装箱(autoboxing)和自动拆箱(autounboxing)

可以看到在使用过程中，装箱和拆箱带来不少的代码量，所以为了减少开发者的负担，java 提供了自动机制。

int i = 10;Integer ii = i; // 自动装箱
Integer ij = (Integer)i; // 自动装箱int j = ii; // 自动拆箱
int k = (int)ii; // 自动拆箱

注意：自动装箱和自动拆箱是工作在编译期间的一种机制。

小问题-为什么Interger类型的a与b赋值为129时结果是false，但是a与b赋值为123时结果是true?

底层方法代码：

答：因为Integer value0f中如果范围在-128——127时就调用high方法，运行结果就是true。如果范围不在-128——127时那么就会调用catch中的low方法，结果就为false

2.4 javap 反编译工具

这里我们刚好学习一个 jdk 中一个反编译工具来查看下自动装箱和自动拆箱过程，并且看到这个过程是发生在编译期间的。

javap -c类名称Compiled from "Main.java"public class Main {public Main();Code:0: aload_01: invokespecial #1 // Method java/lang/Object."<init>":()V4: returnpublic static void main(java.lang.String[]);Code:0: bipush 102: istore_13: iload_14: invokestatic #2 // Method java/lang/Integer.valueOf:
(I)Ljava/lang/Integer;7: astore_28: iload_19: invokestatic #2 // Method java/lang/Integer.valueOf:
(I)Ljava/lang/Integer;12: astore_313: aload_214: invokevirtual #3 // Method java/lang/Integer.intValue:()I17: istore 419: aload_220: invokevirtual #3 // Method java/lang/Integer.intValue:()I23: istore 525: return
}

3. List 的使用

List的官方文档

ArrayList的官方文档

LinkedList的官方文档

3.1 常见方法

List（线性表）：

上述图片方法举例可以参考下方超链接中的String中6.1–6.6的方法举例。

String方法博客

subList方法演示：

ArrayList<String> list = new ArrayList<>();
list.add("hello");
list.add("xxh");
list.add("xyh");
list.add("lol");
list.add("coc");
System.out.println(list.subList(1, 3));
System.out.println(list);

这里subList截取了三个元素，但是只输出了两个元素是因为我们在使用list的方法中采取的是左闭右开的模式。

ArrayList（顺序表）：

如果ArrayList调用，不带参数的构造方法，那么顺序表的大小是0.当第一次add的时候，整个顺序表才变为了10；当这10个放满了，开始扩容，以1.5倍的方式进行扩容。

如果调用的是给定容量的构造方法，那么你的顺序表大小，就是你给定的容量，放满了还是1.5倍扩充。

此时ArrayList链表的初始大小即为13。

LinkedList（链表）：

3.2 示例

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;public class TestDemo {public static void main(String[] args) {List<String> courses = new ArrayList<>();courses.add("C 语言");courses.add("Java SE");courses.add("Java Web");courses.add("Java EE");
// 和数组一样，允许添加重复元素courses.add("C 语言");
// 按照添加顺序打印System.out.println(courses);
// 类似数组下标的方式访问System.out.println(courses.get(0));System.out.println(courses);courses.set(0, "计算机基础");System.out.println(courses);
// 截取部分 [1, 3)List<String> subCourses = courses.subList(1, 3);System.out.println(subCourses);
// 重新构造List<String> courses2 = new ArrayList<>(courses);System.out.println(courses2);List<String> courses3 = new LinkedList<>(courses);System.out.println(courses3);
// 引用的转换ArrayList<String> courses4 = (ArrayList<String>)courses2;System.out.println(courses4);
// LinkedList<String> c = (LinkedList<String>)course2; 错误的类型LinkedList<String> courses5 = (LinkedList<String>)courses3;System.out.println(courses5);
// ArrayList<String> c = (ArrayList<String>)course3; 错误的类型}
}

运行结果：

3.3 练习-扑克牌

import java.util.List;
import java.util.ArrayList;
import java.util.Random;public class TestDemo {public class Card {public int rank; // 牌面值public String suit; // 花色@Overridepublic String toString() {return String.format("[%s %d]", suit, rank);}}public class CardDemo {public static final String[] SUITS = {"♠", "♥", "♣", "♦"};// 买一副牌private static List<Card> buyDeck() {List<Card> deck = new ArrayList<>(52);for (int i = 0; i < 4; i++) {for (int j = 1; j <= 13; j++) {String suit = SUITS[i];int rank = j;Card card = new Card();card.rank = rank;card.suit = suit;deck.add(card);}}return deck;}private static void swap(List<Card> deck, int i, int j) {Card t = deck.get(i);deck.set(i, deck.get(j));deck.set(j, t);}private static void shuffle(List<Card> deck) {Random random = new Random(20190905);for (int i = deck.size() - 1; i > 0; i--) {int r = random.nextInt(i);swap(deck, i, r);}}public static void main(String[] args) {List<Card> deck = buyDeck();System.out.println("刚买回来的牌:");System.out.println(deck);shuffle(deck);System.out.println("洗过的牌:");System.out.println(deck);
// 三个人，每个人轮流抓 5 张牌List<List<Card>> hands = new ArrayList<>();hands.add(new ArrayList<>());hands.add(new ArrayList<>());hands.add(new ArrayList<>());for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {hands.get(j).add(deck.remove(0));}}System.out.println("剩余的牌:");System.out.println(deck);System.out.println("A 手中的牌:");System.out.println(hands.get(0));System.out.println("B 手中的牌:");System.out.println(hands.get(1));System.out.println("C 手中的牌:");System.out.println(hands.get(2));}}

运行结果：

3.4 面试题练习

杨辉三角

感谢各位读者的阅读，本文章有任何错误都可以在评论区发表你们的意见，我会对文章进行改正的。如果本文章对你有帮助请动一动你们敏捷的小手点一点赞，你的每一次鼓励都是作者创作的动力哦！😘