正式进入数据结构的学习，先从预备知识学起，戒焦戒躁戒焦戒躁...
一、泛型的引入
1、为什么需要泛型？
先来看一个题目：
实现一个类，类中包含一个数组成员，使得数组中可以存放任何类型的数据，也可以根据成员方法返回数组中某个下标的值
在没有泛型理念的思路可能是这样：
public class java0810 {public Object[] array = new Object[5];//成员变量public void set(int a,Object b){this.array[a] = b;}public Object get(int c){return array[c];}public static void main(String[] args) {java0810 x = new java0810();x.set(0,"哈哈");x.set(1, 2);String y1 = (String) x.get(0);int y2 = (int) x.get(1); //需要强转，因为是object类型System.out.println(y1);System.out.println(y2);}
}我们通过Object类做到了让一个数组中放入不同类型的数据，但在接收数据的时候需要对其进行强转，很麻烦
于是我们想到使用泛型来解决这个问题：
public class java0810<T> { //变动1public Object[] array = new Object[5];public void set(int a,T b){this.array[a] = b;}public T get(int c){return (T)array[c]; //变动2}public static void main(String[] args) { //变动3java0810<Integer> x1 = new java0810<>();//规定了存放数据的类型x1.set(0,1);x1.set(1,2);int y1 = x1.get(0);int y2 = x1.get(1);System.out.println(y1);System.out.println(y2);java0810<String> x2 = new java0810<>();x2.set(0,"巨浪");x2.set(1,"M14大人");String y3 = x2.get(0);String y4 = x2.get(1);System.out.println(y3);System.out.println(y4);}所有的变动之处需要理解，这样做的好处就是：
“在新建一个对象时就规定了存放数据的类型，可以让系统帮忙检查同时不用强转了”
想要深入理解背后的逻辑可以搜索擦除机制和桥接方法
2、泛型类的上界
我们常常用 <? extends T> 的方式来指定约束泛型类型的上限，从而约束了‘ ？’只能是T或者其子类
来看一个题目：
写一个泛型类，求数组中的最大值，数组的类型需要通过泛型类型来指定
//这是一个泛型类public class java0811<T extends Comparable<T>> {//泛型类的上界public T find(T[] array){int i = 0;T max = array[0];for(i = 1;i < array.length;i++){if(array[i].compareTo(max) > 0){max = array[i];}}return max;}public static void main(String[] args) {java0811<Integer> y1 = new java0811<>(); //指定数组存放的类型java0811<String> y2 = new java0811<>();Integer []array1 = { 4, 3, 2, 91, 500 };String []array2 = {"巨浪", "M14大人","腾龙"};int z = y1.find(array1); //Integer或者int都可以String w = y2.find(array2);System.out.println(z);System.out.println(w);}}这里通过实现了Comparable接口，指定了上界，从而可以使用comparaTo方法进行数字或者字符串的无差别比较
当然了，你也可以写成是一个泛型方法：
public class java0811 {//这就是泛型方法public <T extends Comparable<T>> T find(T[] array){int i = 0;T max = array[0];for(i = 1;i < array.length;i++){if(array[i].compareTo(max) > 0){max = array[i];}}return max;}public static void main(String[] args) {java0811 x = new java0811(); //没有指定类型，因为它不是泛型类了Integer []array1 = { 4, 3, 2, 91, 500 };int y = x.find(array1);System.out.println(y);}
}可以观察一下里面的变动
二、通配符
1、概念：
通配符通过上下界（
extends/super）实现了比泛型类型参数更灵活的类型关系控制，并遵循PECS原则(在值设置和取出时有特定约束)。
我们先来看看通过泛型的方式存放和取出数据：
class Food{
}
class Fruit extends Food{ //先明确了继承关系
}
class apple extends Fruit{
}
class banana extends Fruit{
}public class Plate<T>{ //设置了一个泛型类public T array;public void set(T array){this.array = array;
}public T get(){return array;
}public static void main(String[] args) {Plate<apple> x1= new Plate<>(); //表示只能放入apple对象x1.set(new apple());Plate<banana> x2 = new Plate<>(); //同理x2.set(new banana());// Plate<Food> x3 = new Plate<>();
// fun1(x3); //会失败，因为通配符所以只能传入Fruit的子类fun1(x1);fun1(x2);}//通配符的上界
public static void fun1(Plate<? extends Fruit> z){//指定一个容器，存放的类型是Fruit或子类System.out.println(z.get());
}这里通过fun来打印数据，接收的类型需要是Fruit或者其子类
2、通配符的上界：
采用<? extends T>的方式，在该方法中不能写入子类，但可以接收T的子类
public static void fun1(Plate<? extends Fruit> z){//指定一个容器，存放的类型是Fruit或子类System.out.println(z.get());// z.set(new apple());
// z.set(new banana()); 设置失败，不能知道传入的是哪个子类Fruit fruit = z.get(); //得到的一定是Fruit的子类System.out.println(fruit); //成功了，同时打印了apple跟banana}3、通配符的下界：
采用<? super T>的方式，在该方法中主要用于写入，接收时要用Object类保证安全
public static void main(String[] args) {Plate<Food> x3 = new Plate<>();x3.set(new Food());fun2(x3);}
public static void fun2(Plate<? super Fruit> t){t.set(new Fruit()); //可以放自己以及子类t.set(new apple());t.set(new banana()); //会打印最后一个传入的值// Food food = new Fruit();
// Fruit fruit2 = (Fruit) food; //这样做就安全// Fruit fruit2=(Fruit) new Food();//但是这样直接指向不安全,打印不出来结果// Fruit fruit3 = (Fruit) t.get(); //觉得这个写法突兀的就向上看,也不安全Object o = t.get(); //Object来接收就安全了System.out.println(o);
}
小总结：通配符上界不能写入子类但能接收子类
通配符下界只能写入自己以及子类，只能接收自己以及父类
三、顺序表
顺序表（Sequential List） 是一种线性表，它用一段地址连续的存储单元依次存储线性表的数据元素
核心比喻：电影院座位
你可以把顺序表想象成电影院里一排连续的座位。
连续存储：这些座位是紧挨着的，一个接一个，拥有固定的座位号（如1排1座、1排2座...）。这就是“顺序”的含义——数据在物理内存中是连续存储的。
快速“按号找座”：如果你想找第5个座位上坐的是谁，你可以立刻计算出来并直接走过去。
“插队”与“离场”麻烦：
插入：如果这排座位已经坐满了，你想在中间加一个人，那么从这个位置开始以后的所有人都需要向后移动一个位置，才能空出一个新的座位。
删除：同理，如果中间有一个人离开了，那么他后面的所有人都需要向前移动一个位置来填补空位，以保持座位的连续性。
这是一个自己实现的顺序表：
public interface IList {void add(int data); // 新增元素,默认在数组最后新增void add(int pos, int data); // 在 pos 位置新增元素boolean contains(int toFind); // 判定是否包含某个元素int indexOf(int toFind); // 查找某个元素对应的位置int get(int pos); // 获取 pos 位置的元素void set(int pos, int value); // 给 pos 位置的元素设为 valuevoid remove(int toRemove); //删除第一次出现的关键字keyint size(); // 获取顺序表长度void clear(); // 清空顺序表void display(); // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的boolean isFull();boolean isEmpty();}
import java.util.Arrays;public class MyarrayList implements IList{public int[]array;public int useside;public static final int l = 5;public MyarrayList(){array = new int[l];}//检查是否放满了@Overridepublic boolean isFull() {if(useside == array.length){return true;}return false;}@Overridepublic boolean isEmpty() {if(useside == 0){return true;}return false;}//自己设置的2倍扩容public void grow(){array = Arrays.copyOf(array,2 * array.length);}//在顺序表中，默认在最后位置添加元素，这个没有@Overridepublic void add(int data) {array[useside++] = data;}public void checkpos(int pos){if(pos < 0 || pos > useside){//这里在数组末尾插入是合法的throw new ArrayIndexOutOfBoundsException("pos位置不合法" + pos);} //自定义异常}public void checkpos2(int pos){ //一个典型的受检异常if(pos < 0 || pos >= useside){throw new ListEmptyException("获取位置不合法" + pos);}}@Overridepublic void add(int pos,int data) {checkpos(pos);if(isFull()){grow();} //移动元素for(int i = useside - 1;i >= pos;i--){array[i+1] = array[i];}array[pos] = data;useside++; //新加入了元素就更新计数}@Overridepublic boolean contains(int toFind) {for (int i = 0; i < array.length; i++) {if(array[i] == toFind){return true;}}return false;}@Overridepublic int indexOf(int toFind) {for (int i = 0; i < useside; i++) {//这里写成了array.length会打印没用的0if (array[i] == toFind){return i;}}return -1; //-1肯定不属于下标}@Overridepublic int get(int pos) {if(isEmpty()){throw new ArrayIndexOutOfBoundsException("数组是空的");}checkpos2(pos);return array[pos];}@Overridepublic void set(int pos, int value) {checkpos(pos);array[pos] = value;}@Overridepublic int size() {return array.length;}@Overridepublic void clear() {
// for (int i = 0; i < array.length; i++) {
// array[i] = 0/Null;
// }useside = 0;}@Overridepublic void display() {//这里也是一样，要写useside而不是array.lengthfor (int i = 0; i < useside; i++) {System.out.print(array[i] + " ");}System.out.println();}@Overridepublic void remove(int toRemove) {int v = indexOf(toRemove);if(v == -1){System.out.println("找不到要删除的值");return; //终止代码}for (int i = v; i < useside-1; i++) {array[i] = array[i+1];}useside--;}public static void main(String[] args) {MyarrayList x = new MyarrayList();x.add(0,9); //在1位置添加一个9x.add(1,2);x.add(2,3);x.display();
// try {
// x.checkpos(100);
// }catch (ArrayIndexOutOfBoundsException e){
// e.printStackTrace();
// }int c = x.get(1);System.out.println(c);x.remove(100);x.display();}}
public class ListEmptyException extends RuntimeException{public ListEmptyException() {}public ListEmptyException(String message) {super(message);}
}自己实现过后有助于我们更好的理解顺序表
完
