在正式學習順序表前,先簡單了解一下 List

🌲List

🌲1. 線性表

線性表(linear list）是n個具有相同特性的數據元素的有限序列。 線性表是一種在實際中廣泛使用的數據結構，常見的線性表：順序表、鏈表、棧、隊列…

線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲

🌲2. 順序表

順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改。

順序表底層是一個數組，為什么不直接操作數組就好了，還需要單獨寫個類？

這個數組里有幾個有效數據?-----6個

在Java里數組沒有元素默認為0，判斷的時候遇到0就停止，然后總數就是元素個數，那如果這6個元素中加了一個0呢?還是6個元素,但是數組認為只有5個元素,這就是為什么我們需要順序表

在使用ArrayList之前,我們自己實現一個順序表,方便我們更加深入的理解順序表,才能熟練使用它

🌿2.1 MyArrayList

public class MyArrayList implements IList {public int[] array;public int usedSize;//成員變量默認為0public static final int DEFAULT_CAPACITY = 10;public MyArrayList() {this.array = new int[DEFAULT_CAPACITY];}

成員變量包含數組，數組里的有效元素個數,數組長度(可以使用final修飾讓數據不被改變)
###🌿 2.1.1 接口IList

//10個方法
public interface IList {// 新增元素,默認在數組最后新增public void add(int data);// 在 pos 位置新增元素public void add(int pos, int data);// 判定是否包含某個元素public boolean contains(int toFind);// 查找某個元素對應的位置public int indexOf(int toFind);// 獲取 pos 位置的元素public int get(int pos);// 給 pos 位置的元素設為 valuepublic void set(int pos, int value);//刪除第一次出現的關鍵字keypublic void remove(int toRemove);// 獲取順序表長度public int size();// 清空順序表public void clear();// 打印順序表，注意：該方法并不是順序表中的方法，為了方便看測試結果給出的public void display();
}

注意:接口中的方法默認為public abstract 修飾

這些是我們要實現的所有方法,自己實現一遍,能更好的理解ArrayList

2.1.1 類中重寫所有接口方法

1.新增元素

// 新增元素,默認在數組最后新增
public void add(int data) { //默認在尾部插入數據//判滿if(isFull()){grow();//擴容}this.array[this.usedSize]=data;this.usedSize++;}public void grow(){this.array= Arrays.copyOf(this.array,2*this.array.length);}public boolean isFull(){return this.usedSize== array.length;}

默認在數組尾部新增

①需要判斷數組是否是滿的，滿的就需要擴容，
②不滿的話就進行元素插入，判斷數組滿不滿狀態的函數實現
③最后數組長度+1

2.在pos位置新增元素(指定位置)

public void add(int pos, int data) { //插入到指定位置//pos合法性try{checkPos(pos);if(isFull()){grow();//擴容}//挪動數據for (int i = usedSize-1; i >=pos ; i--) {array[i+1]=array[i];}array[pos]=data;this.usedSize++;}catch (PosIllegal e){System.out.println("插入元素pos位置不合法");e.printStackTrace();//提示異常位置}}private void checkPos(int pos) throws PosIllegal{if(pos < 0 || pos > usedSize) { //注意:usedSize能插入,只要前驅存在就可以插入throw new PosIllegal("Pos位置不合法！！");}}

①先判斷pos位置合法性，既不能是負數，又必須要有前驅信息的支持
②判斷數組元素是否滿了，繼續調用isFull()函數
③我們插入數據的時候，需要先把插入元素后面的元素都往后挪一位，挪數據實現從數組的最后一個元素開始往后挪，一次挪到當pos位置空出，沒有元素的時候即可
④挪完數據之后，我們把pos位置賦值為data，并且把數組大小擴容一位，方便再進行新增元素

3.判定是否包含了某個特定元素

 public boolean contains(int toFind) {for (int i = 0; i <this.usedSize ; i++) {if(array[i]==toFind){return true;}}return false;}

4.查找特定元素對應的位置

// 查找某個元素對應的位置
public int indexOf(int toFind) {for (int i = 0; i < this.usedSize; i++) {if(this.elem[i] == toFind){return i;}}return -1;
}

5.獲取pos下標的元素

private void checkPos2(int pos) throws PosIllegal{if(pos < 0 || pos >= usedSize) {throw new PosIllegal("Pos位置不合法！！");}}private void checkEmpty() {if(isEmpty()) {throw new EmptyException("順序表為空!");}}public boolean isEmpty(){return  usedSize==0;}@Overridepublic int get(int pos) {try{checkEmpty();checkPos2(pos);return array[pos];}catch (PosIllegal e){System.out.println("插入位置pos不合法");e.printStackTrace();}catch (EmptyException e){System.out.println("順序表位空");e.printStackTrace();}return -1;}

①先判斷pos位置合法性
②判斷數組是否為空（可有可無）

6.給pos位置的元素替換成value

①先要進行合法性判斷再替換

 public void set(int pos, int value) { //更新   pos位置更新為valuetry{checkEmpty();checkPos2(pos); array[pos]=value;}catch (PosIllegal e){System.out.println("插入位置pos不合法");e.printStackTrace();}catch (EmptyException e){System.out.println("順序表位空");e.printStackTrace();}}

7.刪除數據

 public void remove(int toRemove) {try{checkEmpty();int pos=indexOf(toRemove);if (pos==-1)return ;for (int i = pos; i <this.usedSize-1 ; i++) {array[i]=array[i+1];}this.usedSize--;}catch (EmptyException e){e.printStackTrace();}}

①順序表不為空
②順序表當中有我們要刪除的元素
③找到它的下標
④把i+1的值賦給i，i還要小于usedSize-1(只要涉及到刪除數據，如果是引用數據類型，那么就要把elem[i] = null;否則就會發生內存泄漏）

8.獲取順序表長度

// 獲取順序表長度
public int size() {return this.usedSize;
}

9.清空順序表

// 清空順序表
public void clear() {//因為是基本類型，所以置為0即可this.usedSize = 0;/*當它是引用類型時for (int i = 0; i < this.usedSize; i++) {this.elem[i] = null;}this.usedSize = 0;*/
}

①基本類型置為0即可，若是引用類型則循環打印置為null，再置為0

注意：
此處可以把elem置為null可以嗎？可以，但是很暴力，數組直接被回收了，順序表只執行了一次就沒了，再次使用的時候還需開辟新的數組，相當于我們每次使用的時候還需new一次，很麻煩也沒必要

10.打印順序表

public void display() {for (int i = 0; i < this.usedSize; i++) {System.out.print(array[i]+" ");}/*這里面所有都是 0for (int x : array) {System.out.print(x+" ");}*/}
}

需要的自定義異常

在這里面添加，獲取pos下標不合法的時候我們也可以寫我們需要的異常類來更好的實現我們需要的異常，實現異常的拋出是我們賦值命名的異常名：

public class MyArrayListEmptyException extends RuntimeException{public MyArrayListEmptyException(){}public MyArrayListEmptyException(String message){super(message);}
}

public class MyArraylistIndexOutofException extends RuntimeException{public MyArraylistIndexOutofException(){}public MyArraylistIndexOutofException(String message){super(message);}
}

好,自己實現一遍順序表是不是思路清晰了很多,我們正式進入順序表介紹

🌲3.ArrayList 簡介

在集合框架中，ArrayList是一個普通的類，實現了List接口，具體框架圖如下:

1. ArrayList是以泛型方式實現的，使用時必須要先實例化
2. ArrayList實現了RandomAccess接口，表明ArrayList支持隨機訪問
3. ArrayList實現了Cloneable接口，表明ArrayList是可以clone的
4. ArrayList實現了Serializable接口，表明ArrayList是支持序列化的
5. 和Vector不同，ArrayList不是線程安全的，在單線程下可以使用，在多線程中可以選擇Vector或者CopyOnWriteArrayList
6. ArrayList底層是一段連續的空間，并且可以動態擴容，是一個動態類型的順序表

🌲4. ArrayList 的使用

🌿4.1 ArrayList 的構造

進入ArrayList的源碼,我們來詳細了解

提問:都是空數組,那我們main函數中add的值都是存在哪里的?

答:add函數過程中會擴容1.5倍 下面我們講到擴容機制再詳細說

方法一ArrayList()不帶參數的構造方法的使用：

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);//往數組最后的一個位置存元素
arrayList.add(2);
arrayList.add(3);
arrayList.add(4);
System.out.println(arrayList);//用字符串的形式打印出來所有的元素
System.out.println(arrayList.size());//獲取當前有效數據的個數
System.out.println(arrayList.get(1));//獲取指定下標的元素

方法二的使用：

ArrayList<Integer> arrayList2 = new ArrayList<>(arrayList);
arrayList2.add(99);
arrayList2.add(199);
System.out.println(arrayList2);

arrayList2承接了arrayList1的數據（使用其他的集合 來構造當前的List，底層源碼實現是數組的拷貝）

方法三的使用：

ArrayList<Integer> arrayList3 = new ArrayList<>(15)

指定初始化數組容量大小

在源碼的實現里：
①：第一次add的時候，我們底層的數組才變成了10，如果只是調用了不帶參數的構造方法，默認還是0
②：grow函數就是擴容函數，擴容的方式是1.5倍的擴容

例如整體的舉例使用：

public static void main(String[] args) {// ArrayList創建，推薦寫法// 構造一個空的列表List<Integer> list1 = new ArrayList<>();// 構造一個具有10個容量的列表List<Integer> list2 = new ArrayList<>(10);list2.add(1);list2.add(2);list2.add(3);// list2.add("hello"); // 編譯失敗，List<Integer>已經限定了，list2中只能存儲整形元素// list3構造好之后，與list中的元素一致ArrayList<Integer> list3 = new ArrayList<>(list2);// 避免省略類型，否則：任意類型的元素都可以存放，使用時將是一場災難List list4 = new ArrayList();list4.add("111");list4.add(100);
}

🌿4.2 ArrayList常見操作

add方法

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(0,1);
arrayList.add(1,2);
arrayList.add(2,99);
System.out.println(arrayList);

需要注意的是：在我們實現元素插入賦值的時候,前驅必須存在

addAll方法：

ArrayList<Integer> arrayList2 = new ArrayList<>();
arrayList2.addAll(arrayList);
arrayList2.add(19);System.out.println(arrayList2);

remove方法：

public class Main{public static void main(String[] args) {MyArrayList array=new MyArrayList();ArrayList<Integer> list=new ArrayList<Integer>();list.add(0,1);list.add(1,2);list.add(2,3);list.add(3,4);list.add(4,5);ArrayList<Integer> list2=new ArrayList<Integer>();list2.addAll(list);list2.add(99999999);list2.remove(new Integer(5));System.out.println(list2);}
}

lastIndexOf方法:

int index = arrayList.lastIndexOf(new Integer(99));
System.out.println(index);

subList方法 和 set方法:

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(0,1);
arrayList.add(1,2);
arrayList.add(2,99);
arrayList.add(3,199);
arrayList.add(4,299);
System.out.println(arrayList);List<Integer> list = arrayList.subList(1,3);//區間左閉右開
System.out.println(list);

相當于字符串的截取，區間左閉右開
這里面我們如果把list里面的數值改變了，是否會影響原來的arraylist數組呢？-----會改變

🌿4.3 ArrayList的遍歷

ArrayList 可以使用三種方式遍歷：for循環+下標、foreach、使用迭代器

public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);// 使用下標+for遍歷for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();// 借助foreach遍歷for (Integer integer : list) {  //也可以用int 這個過程相當于拆箱System.out.print(integer + " ");}System.out.println();Iterator<Integer> it = list.listIterator();while(it.hasNext()){System.out.print(it.next() + " ");}System.out.println();}

兩種迭代器打印代碼如下:

注意：

1. ArrayList最常使用的遍歷方式是：for循環+下標 以及 foreach
2. 迭代器是設計模式的一種，后序容器接觸多了在仔細學一學,講一講

感興趣的同學可以在IDEA中點到源碼,讀源碼學習

🌿4.4 ArrayList的擴容機制（java8源碼實現講解)

我們這里用的是 java8 源碼,更好理解,java17 重寫了,但是效果并不影響

ArrayList是一個動態類型的順序表，即：在插入元素的過程中會自動擴容

Object[] elementData; // 存放元素的空間
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默認空間為0
private static final int DEFAULT_CAPACITY = 10; // 默認容量大小
public boolean add(E e) {ensureCapacityInternal(size + 1); // Increments modCount!!elementData[size++] = e;return true;
}
private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {// 獲取舊空間大小int oldCapacity = elementData.length;// 預計按照1.5倍方式擴容int newCapacity = oldCapacity + (oldCapacity >> 1);// 如果用戶需要擴容大小 超過 原空間1.5倍，按照用戶所需大小擴容if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果需要擴容大小超過MAX_ARRAY_SIZE，重新計算容量大小if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// 調用copyOf擴容elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {// 如果minCapacity小于0，拋出OutOfMemoryError異常if (minCapacity < 0)throw new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

總結：
檢測是否真正需要擴容，如果是調用grow準備擴容
預估需要庫容的大小
①初步預估按照1.5倍大小擴容
②如果用戶所需大小超過預估1.5倍大小，則按照用戶所需大小擴容
③真正擴容之前檢測是否能擴容成功，防止太大導致擴容失敗使用copyOf進行擴容
④.授予copeOf進行擴容

🌲5. ArrayList的具體使用

🌿5.1 刪除字符 (要求使用集合)

🌿5.2 楊輝三角

楊輝三角

我們把圖形抽象為一個直角三角形

要求的返回值是這樣的–二維數組

ret是整個數組

public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret=new ArrayList<>();//第一行List<Integer> list0=new ArrayList<>();list0.add(1);ret.add(list0);//從第2行開始求每個元素for (int i = 1; i <numRows ; i++) {List<Integer> curRow = new ArrayList<>();//每一行curRow.add(1);  //第一列//中間List<Integer> preRow = ret.get(i - 1);//獲得上一行for (int j = 1; j < i; j++) {int val1 = preRow.get(j);int val2 = preRow.get(j - 1);curRow.add(val1 + val2);}//尾巴curRow.add(1);ret.add(curRow);}return ret;//返回目標數組}
}

🌿5.3 撲克牌洗牌

自己寫一副撲克牌

①：完成剛買牌的順序打印出來
②：我們再完成洗牌隨機打亂順序
③：三個人輪流每個人揭5張牌
④：輸出最后剩余的牌

1.我們需要先單獨創建一個Card類，定義花色和數字，添加構造方法以及getter和setter方法，重寫ToString方法

class Card {private String suit;private int rank;public Card(String suit, int rank) {this.suit = suit;this.rank = rank;}public String getSuit() {return suit;}public void setSuit(String suit) {this.suit = suit;}public int getRank() {return rank;}public void setRank(int rank) {this.rank = rank;}@Overridepublic String toString() {return "[ " + suit+" "+rank+" ]";}
}

2.牌按照花色和順序打印出來，再把花色和序號拼接在一起組成每個牌每個花色

public static final String[] suits = {"?","?","?","?"};public static List<Card> buyCard() {List<Card> desk = new ArrayList<>();for (int i = 0; i < 4; i++) {for (int j = 1; j <= 13 ; j++) {String suit = suits[i];Card card = new Card(suit,j);desk.add(card);}}return desk;
}

3.洗牌使用random類中的nextInt函數并且交換每個元素的下標，讓它遍歷的時候隨機和其他元素下標交換,讓下標隨機數取元素長度里的任何一個下標，正向遍歷也可以,反向遍歷更好

public static void shuffle(List<Card> cardList) {for (int i = cardList.size()-1; i > 0 ; i--) {Random random = new Random();int index = random.nextInt(i);swap(cardList,i,index);}
}

private static void swap(List<Card> cardList,int i,int j) {Card tmp = cardList.get(i);cardList.set(i,cardList.get(j));cardList.set(j,tmp);
}

4.三個人每個人都輪流揭五張牌，最后揭的牌需要刪除，方便后面我們打印剩余的牌

for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {//每次揭牌都去獲取 cardList的0下標的數據【刪除】Card card = cardList.remove(0);List<Card> hand = hands.get(j);hand.add(i,card);//這里使用add 不能是set/*hands.get(j).add(card);*/}
}

5.當我們此時打印cardList就是剩余的牌了，然后把所有的代碼執行結果打印出來

附上代碼:

CardDemo

public class CardDemo {public static final String[] suits = {"?","?","?","?"};public List<Card> buyCard() {List<Card> cardList = new ArrayList<>();for (int i = 1; i <= 13; i++) {for (int j = 0; j < 4; j++) {int rank = i;String suit = suits[j];Card card = new Card(suit,rank);cardList.add(card);}}return cardList;}public void shuffle(List<Card> cardList) {Random random = new Random();for (int i = cardList.size()-1; i > 0 ; i--) {int index = random.nextInt(i);swap(cardList,i,index);}}private void swap(List<Card> cardList,int i,int j) {/*Card tmp =  cardList[i];cardList[i] = cardList[j];cardList[j] = tmp;*/Card tmp = cardList.get(i);cardList.set(i,cardList.get(j));cardList.set(j,tmp);}public List<List<Card>> play(List<Card> cardList) {List<Card> hand0 = new ArrayList<>();List<Card> hand1 = new ArrayList<>();List<Card> hand2 = new ArrayList<>();List<List<Card>> hand = new ArrayList<>();hand.add(hand0);hand.add(hand1);hand.add(hand2);for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {Card card = cardList.remove(0);//怎么把對應的牌 放到對應的人的手里面hand.get(j).add(card);}}return hand;}
}

Card

public class Card {private String suit;private int rank;public Card(String suit, int rank) {this.suit = suit;this.rank = rank;}@Overridepublic String toString() {/*return "Card{" +"suit='" + suit + '\'' +", rank=" + rank +'}';*/return "{"+suit + rank +"} ";}
}

Main

public static void main(String[] args) {CardDemo cardDemo = new CardDemo();//1. 買52張牌List<Card> cardList = cardDemo.buyCard();System.out.println(cardList);//2. 洗牌cardDemo.shuffle(cardList);System.out.println(cardList);//3. 3個人 每個人 輪流揭牌5張List<List<Card>> ret = cardDemo.play(cardList);for (int i = 0; i < ret.size(); i++) {System.out.println("第"+(i+1)+"個人的牌："+ret.get(i));}System.out.println("剩下的牌：");System.out.println(cardList);}

6.🌸ArrayList的問題

1. ArrayList底層使用連續的空間，任意位置插入或刪除元素時，需要將該位置后序元素整體往前或者往后搬移，故時間復雜度為O(N)
2. 增容需要申請新空間，拷貝數據，釋放舊空間。會有不小的消耗。
3. 增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以后增容到200，我們再繼續插入了5個數據，后面沒有數據插入了，那么就浪費了95個數據空間

這些問題該如何解決呢?

使用鏈表就可以解決

下一篇文章揭曉鏈表的神奇應用