數據結構青銅到王者第二話---數據結構基本常識（2）

????????續接上一話

一、包裝類

????????在Java中，由于基本類型不是繼承自Object，為了在泛型代碼中可以支持基本類型，Java給每個基本類型都對應了一個包裝類型。

1、基本數據類型和對應的包裝類

????????除了 Integer 和 Character，其余基本類型的包裝類都是首字母大寫。

2、裝箱和拆箱

 int i = 10; // 裝箱操作，新建一個 Integer 類型對象，將 i 的值放入對象的某個屬性中Integer ii = Integer.valueOf(i);Integer ij = new Integer(i);// 拆箱操作，將 Integer 對象中的值取出，放到一個基本數據類型中int j = ii.intValue();

3、自動裝箱和自動拆箱

????????我們可以看到在使用過程中，裝箱和拆箱帶來不少的代碼量，所以為了減少開發者的負擔，java 提供了自動機制。

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

這里給大家一個面試題：

????????下列代碼輸出什么，為什么？

 public static void main(String[] args) {Integer a = 127;Integer b = 127;Integer c = 128;Integer d = 128;System.out.println(a == b);System.out.println(c == d);}

輸出分別為：

????????????????????????true

????????????????????????false? ?

????????這是因為用到了裝箱，如下就是裝箱的操作：

public static Integer valueOf(int i){if(i >= IntegerCache.low && i <= IntegerCache.high)return IntegerCache.cache[i+(-IntegerCache.low)];return new Integer(i);
}

? ? ? ? 這就可以得到一個初步的結論：i應該是在一個范圍內的時候去數組里面直接拿值，不在這個范圍內的時候，他就會返回因的對象，新對象之間直接用等號比較，結果當然是不一樣的！！！

? ? ? ? 其實，哪怕不看的話，我們也可以猜個八九不離十，因為都是和2的幾次方相關的，經驗多了也就會了！！！

?二、泛型

1、什么是泛型

????????一般的類和方法，只能使用具體的類型: 要么是基本類型，要么是自定義的類。如果要編寫可以應用于多種類型的代碼，這種刻板的限制對代碼的束縛就會很大。----- 來源《Java編程思想》對泛型的介紹。

???????? 泛型是在JDK1.5引入的新的語法，通俗講，泛型：就是適用于許多許多類型。從代碼上講，就是對類型實現了參數化。

2、泛型的簡單介紹

????????實現一個類，類中包含一個數組成員，使得數組中可以存放任何類型的數據，也可以根據成員方法返回數組中某個下標的值？

思路：

（1）我們以前學過的數組，只能存放指定類型的元素，例如：int[] array = new int[10]; String[] strs = new String[10];

（2）所有類的父類，默認為Object類。數組是否可以創建為Object?

class MyArray {public Object[] array = new Object[10];public Object getPos(int pos) {return this.array[pos];}public void setVal(int pos,Object val) {this.array[pos] = val;}}public class TestDemo {public static void main(String[] args) {MyArray myArray = new MyArray();myArray.setVal(0,10);myArray.setVal(1,"hello");//字符串也可以存放String ret = myArray.getPos(1);//編譯報錯System.out.println(ret);}}

問題：以上代碼實現后發現

（1）任何類型數據都可以存放

（2）1號下標本身就是字符串，但是卻編譯報錯。必須進行強制類型轉換

????????雖然在這種情況下，當前數組任何數據都可以存放，但是，更多情況下，我們還是希望他只能夠持有一種數據類型。而不是同時持有這么多類型。所以，泛型的主要目的：就是指定當前的容器，要持有什么類型的對象。讓編譯器去做檢查。此時，就需要把類型，作為參數傳遞。需要什么類型，就傳入什么類型。

2.1基本語法

class 泛型類名稱<類型形參列表> {// 這里可以使用類型參數
}class ClassName<T1, T2, ..., Tn> {  
}
class 泛型類名稱<類型形參列表> extends 繼承類/* 這里可以使用類型參數 */ {// 這里可以使用類型參數
}class ClassName<T1, T2, ..., Tn> extends ParentClass<T1> {// 可以只使用部分類型參數
}

上述代碼進行改寫如下：

class MyArray<T> {public Object[] array =  new Object[10];public T getPos(int pos) {return (T)this.array[pos];}public void setVal(int pos,T val) {this.array[pos] = val;}}public class TestDemo {public static void main(String[] args) {MyArray<Integer> myArray = new MyArray<>();//1myArray.setVal(0,10);myArray.setVal(1,12);int ret = myArray.getPos(1);//2System.out.println(ret);myArray.setVal(2,"bit");//3}}

代碼解釋：

（1）類名后的代表占位符，表示當前類是一個泛型類

（了解：【規范】類型形參一般使用一個大寫字母表示，常用的名稱有：

????????????????E 表示 Element

????????????????K 表示 Key

????????????????V 表示 Value

????????????????N 表示 Number

????????????????T 表示 Type

S, U, V 等等 - 第二、第三、第四個類型）

（2）注釋1處，類型后加入指定當前類型

（3）注釋2處，不需要進行強制類型轉換

（4）注釋3處，代碼編譯報錯，此時因為在注釋2處指定類當前的類型，此時在注釋3處，編譯器會在存放元素的時候幫助我們進行類型檢查。

3、泛型的使用

3.1語法

泛型類<類型實參> 變量名;  // 定義一個泛型類引用
new 泛型類<類型實參>(構造方法實參);  // 實例化一個泛型類對象

示例：

MyArray<Integer> list = new MyArray<Integer>();

#注：泛型只能接受類，所有的基本數據類型必須使用包裝類！

3.2類型推導(Type?Inference)

????????當編譯器可以根據上下文推導出類型實參時，可以省略類型實參的填寫

MyArray<Integer> list = new MyArray<>(); // 可以推導出實例化需要的類型實參為 Integer

4、裸類型(Raw Type) （了解）

4.1說明

????????裸類型是一個泛型類但沒有帶著類型實參，例如 MyArrayList 就是一個裸類型

MyArray list = new MyArray();

#注：我們不要自己去使用裸類型，裸類型是為了兼容老版本的 API 保留的機制

????????下面的類型擦除部分，我們也會講到編譯器是如何使用裸類型的。

小結：

（1）泛型是將數據類型參數化，進行傳遞

（2）使用 <T> 表示當前類是一個泛型類。

（3）泛型目前為止的優點：數據類型參數化，編譯時自動進行類型檢查和轉換

5、擦除機制

????????在編譯的過程當中，將所有的 T 替換為 Object 這種機制，我們稱為：擦除機制。

????????Java的泛型機制是在編譯級別實現的。編譯器生成的字節碼在運行期間并不包含泛型的類型信息。

????????編譯完成以后，T被擦除為Object（編譯期間用T進行類型的檢查和轉換）

Java泛型擦除機制之答疑解惑 - 知乎https://zhuanlan.zhihu.com/p/51452375

6、泛型的上界

????????在定義泛型類時，有時需要對傳入的類型變量做一定的約束，可以通過類型邊界來約束。

6.1語法

 class 泛型類名稱<類型形參 extends 類型邊界> {...}

示例：

 public class MyArray<E extends Number> {...}

????????只接受 Number 的子類型作為 E 的類型實參

MyArray<Integer> l1;        // 正常，因為 Integer 是 Number 的子類型
MyArray<String>  l2;        // 編譯錯誤，因為 String 不是 Number 的子類型

（當沒有指定的邊界時，可以認為E extends Object）

復雜示例：

 public class MyArray<E extends Comparable<E>> {...}

（E必須是實現了Comparable接口的）

7、泛型方法

7.1定義語法

方法限定符 <類型形參列表> 返回值類型 方法名稱(形參列表) { ... }

7.2示例：

 public class Util {//靜態的泛型方法 需要在static后用<>聲明泛型類型參數public static <E> void swap(E[] array, int i, int j) {E t = array[i];array[i] = array[j];array[j] = t;}}

7.3使用示例-可以類型推導

 Integer[] a = { ... };swap(a, 0, 9);String[] b = { ... };swap(b, 0, 9);

7.4使用示例-不使用類型推導

 Integer[] a = { ... };Util.<Integer>swap(a, 0, 9);String[] b = { ... };Util.<String>swap(b, 0, 9);

三、List的介紹

1、什么是List

????????在集合框架中，List是一個接口，繼承自Collection。

????????Collection也是一個接口（繼承自Iterable），該接口中規范了后序容器中常用的一些方法，具體如下所示：

????????Iterable也是一個接口，表示實現該接口的類是可以逐個元素進行遍歷的，具體如下：

List的官方文檔：

?List (Java Platform SE 8 )https://docs.oracle.com/javase/8/docs/api/java/util/List.html????????站在數據結構的角度來看，List就是一個線性表，即n個具有相同類型元素的有限序列，在該序列上可以執行增刪改查以及變量等操作