什么是ArrayList

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

ArrayList相關說明

1. ArrayList是以泛型方式實現的，使用時必須要先實例化

2. ArrayList實現了RandomAccess接口，表明ArrayList支持隨機訪問

3. ArrayList實現了Cloneable接口，表明ArrayList是可以clone的

4. ArrayList實現了Serializable接口，表明ArrayList是支持序列化的

5. 和Vector不同，ArrayList不是線程安全的，在單線程下可以使用，在多線程中可以選擇Vector或者CopyOnWriteArrayList

6. ArrayList底層是一段連續的空間，并且可以動態擴容，是一個動態類型的順序表

ArrayList使用

ArrayList的構造

ArrayList的構造有三種

無參構造

ArrayList創建，推薦寫法

// 構造一個空的列表
List<Integer> list1 = new ArrayList<>();

指定順序表初始容量

// 構造一個具有10個容量的列表
List<Integer> list2 = new ArrayList<>(10);
list2.add(1);
list2.add(2);
list2.add(3);

利用其他 Collection 構建 ArrayList

// list3構造好之后，與list2中的元素一致
ArrayList<Integer> list3 = new ArrayList<>(list2);

ArrayList常見操作

ArrayList雖然提供的方法比較多，但是常用方法如下所示

例如我們有以下代碼

List<String> list = new ArrayList<>();
list.add("JavaSE");
list.add("JavaWeb");
list.add("JavaEE");
list.add("遇事問春風乄");
list.add("數據結構");

獲取list有效元素個數

// 獲取list中有效元素個數
System.out.println(list.size());

獲取和設置index位置上的元素

注意：index必須介于[0, size)間

System.out.println(list.get(1));//獲取
list.set(1, "JavaWEB");//設置

在list的index位置插入指定元素

在list的index位置插入指定元素后，index及后續的元素統一往后搬移一個位置

list.add(1, "Java數據結構");

刪除指定元素

刪除指定元素，找到了就刪除，該元素之后的元素統一往前搬移一個位置

list.remove("JavaEE")

刪除list中index位置上的元素

注意:index不要超過list中有效元素個數,否則會拋出下標越界異常

list.remove(list.size()-1)

檢測list中是否包含指定元素

包含返回true，否則返回false

if(list.contains("遇事問春風乄")){list.add("遇事問春風乄");
}

查找指定元素第一次出現的位置

indexOf從前往后找，lastIndexOf從后往前找

//從前往后
System.out.println(list.indexOf("JavaSE"));
//從后往前
System.out.println(list.lastIndexOf("JavaSE"));

截取部分 list

使用list中[0, 4)之間的元素構成一個新的SubList返回,但是和ArrayList共用一個elementData數組

List<String> ret = list.subList(0, 4);

ArrayList的遍歷

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

for循環+下標

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) + " ");
}

foreach

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
// 借助foreach遍歷
for (Integer integer : list) {System.out.print(integer + " ");
}

使用迭代器

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
Iterator<Integer> it = list.listIterator();
while(it.hasNext()){System.out.print(it.next() + " ");
}

注意事項

1. ArrayList最長使用的遍歷方式是：for循環+下標 以及 foreach
2. 迭代器是設計模式的一種

ArrayList的擴容機制

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

以下是ArrayList源碼中擴容方式

 Object[] elementData; // 存放元素的空間private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默認空間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;}

小結

1. 檢測是否真正需要擴容，如果是調用grow準備擴容

2. 預估需要庫容的大小
   初步預估按照1.5倍大小擴容
   如果用戶所需大小超過預估1.5倍大小，則按照用戶所需大小擴容
   真正擴容之前檢測是否能擴容成功，防止太大導致擴容失敗

3. 使用copyOf進行擴容

ArrayList的具體使用

楊輝三角

題目描述

給定一個非負整數 numRows，生成「楊輝三角」的前 numRows 行。

題目解釋：

題中返回值為 List<List< Integer > >,意思為返回一個List，這個List里面的每一個元素也為List

解法思路：

List里面放List可以類似與我們的二維數組，而我們的楊輝三角也可以看成一個二維數組

比如我們現在有一個List實例為ret，ret里面存放的是List類型的元素；ret的每一個List元素里存放的是楊輝三角每一行的所有元素

通過觀察我們發現，楊輝三角的第一位總是1，并且每一行的最后一個與第一個都為1；其余的等于上面一行的兩個數相加

代碼實現：

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();List<Integer> row = new ArrayList<>();ret.add(row);row.add(1);for(int i = 1;i < numRows;i++) {List<Integer> row1 = ret.get(i-1);List<Integer> row2 = new ArrayList<>(i);ret.add(row2);row2.add(1);for(int j = 1;j < i;j++){int h = row1.get(j) + row1.get(j-1);row2.add(h);}row2.add(1);}return ret;}
}

簡單的洗牌算法

比如我們現在需要實現一個簡單的炸金花

Card類

那么我們首先第一步，我們得了解一下撲克，我們除開大小王，就剩下52張牌。每張牌都有相應的面額和花色

那么我們便可以建立一個Card類用于描述我們的撲克

class Card {public int rank; // 牌面值public String suit; // 花色@Overridepublic String toString() {return String.format("[%s %d]", suit, rank);}
}

買牌（初始化）

接下來我們需要買一副牌，其實也就是對我們的牌進行初始化

一共四個花色，每一種花色對應13張牌

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();//隨機數for (int i = deck.size() - 1; i > 0; i--) {int r = random.nextInt(i);swap(deck, i, r);}}

摸牌

三個人輪流摸牌，我悶這里采用二維數組的思想來實現，也就是List里面的元素是List

摸一張牌，排隊里就少一張牌，這里操作起來非常簡單，我們只需要將牌堆deck的0下標進行刪除就好

使用E remove(int index)刪除當前下標的元素，并返回該元素，將該元素添加到每一位玩家的手中

List<List<Card>> hands = new ArrayList<>();hands.add(new ArrayList<>());hands.add(new ArrayList<>());hands.add(new ArrayList<>());for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {hands.get(j).add(deck.remove(0));}}

效果展示：

完整代碼：

import java.util.ArrayList;
import java.util.List;
import java.util.Random;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();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 < 3; 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));}
}

總結

關于《【數據結構】 ArrayList簡介與實戰》就講解到這兒，感謝大家的支持，歡迎各位留言交流以及批評指正，如果文章對您有幫助或者覺得作者寫的還不錯可以點一下關注，點贊，收藏支持一下！