ArrayList与顺序表详解

目录

一、线性表：数据结构的基石

二、顺序表的实现原理

三、ArrayList：增强版顺序表

四、实战应用场景

---

一、线性表：数据结构的基石

想象一下，我们有一排书架，每本书依次排列，这就是​​线性表​​的直观体现。在计算机世界里，线性表是一种最基础的数据结构，它的特点是元素像糖葫芦一样串成一串，每个元素都有唯一的前后邻居（除了头尾）。

​​举个例子​​：

• 日常生活中的排队买票
• 程序中的待办任务列表
• 数学里的数列概念

线性表有两种存储方式：

1. ​​顺序存储​​（顺序表）：用连续的内存空间保存元素，就像把书一本本紧挨着放在书架上
2. ​​链式存储​​（链表）：用指针连接分散的内存块，像用绳子串起珠子

---

二、顺序表的实现原理

顺序表就像一个可伸缩的数组盒子。当我们往盒子里放东西时：

1. ​​初始状态​​：盒子容量固定（比如默认10个格子）
2. ​​装满时​​：自动扩容（通常是翻倍容量，就像给盒子加层隔板）

// 往指定位置插入元素的底层原理
public void insert(int index, int data) {// 1. 检查位置合法性（不能超过当前元素个数）// 2. 如果空间不够，先扩容// 3. 把index之后的元素集体往后挪一位System.arraycopy(array, index, array, index+1, size-index);// 4. 放入新元素array[index] = data;size++;
}

为什么插入慢？​​
因为每次插入都要移动后续元素，就像排队时有人插队，后面的人都得往后退一步。

三、ArrayList：增强版顺序表

ArrayList就像是给顺序表装上了智能引擎：

• ​​自动扩容​​：当元素装满时，悄悄扩容1.5倍（JDK1.8的优化策略）
• ​​随机访问​​：直接通过索引定位元素，速度堪比查字典
• ​​泛型支持​​：可以存放任何类型的对象（比如String、自定义的Card类）

​​扩容机制揭秘​​：

// JDK源码中的扩容魔法
private void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍扩容// 确保新容量足够存放新元素if (newCapacity - minCapacity < 0) newCapacity = minCapacity;// 创建新数组并复制数据elementData = Arrays.copyOf(elementData, newCapacity);
}

为什么选1.5倍？​​

• 平衡内存浪费和扩容频率
• 1.5倍近似黄金分割比例，能减少多次扩容的累计空间浪费

四、实战应用场景

​​场景1：过滤敏感词​

// 从字符串中移除特定字符
public String filterBadWords(String text, String badChars) {List<Character> cleanList = new ArrayList<>();for (char c : text.toCharArray()) {if (!badChars.contains(c)) {cleanList.add(c);}}return cleanList.stream().map(String::valueOf).collect(Collectors.joining());
}

场景2：生成杨辉三角​

// 动态构建二维数组结构
public List<List<Integer>> generateYanghui(int rows) {List<List<Integer>> triangle = new ArrayList<>();for (int i = 0; i < rows; i++) {List<Integer> row = new ArrayList<>(i+1);row.add(1); // 每行首元素for (int j = 1; j < i; j++) {row.add(triangle.get(i-1).get(j-1) + triangle.get(i-1).get(j));}if (i > 0) row.add(1); // 每行尾元素triangle.add(row);}return triangle;
}

场景3：洗牌发牌

public class Card {private String suit;private int rank;public Card() {}public Card(String suit, int rank) {this.suit = suit;this.rank = rank;}@Overridepublic String toString() {return "{"+this.suit+this.rank+"} ";}
}public class CardDemo {public static final String[] suits = {"♣","♠","♦","♥"};private static void swarp(List<Card> list,int currentIndex,int randomIndex) {Card tmp = list.get(currentIndex);list.set(currentIndex,list.get(randomIndex));list.set(randomIndex,tmp);}public static void main(String[] args) {Card c = new Card();List<Card> cards = new ArrayList<>();//生成52张牌for (int i = 1; i <= 13; i++) {for (int j = 0; j < suits.length; j++) {c = new Card(suits[j],i);cards.add(c);}}System.out.println("洗牌前：");System.out.println(cards);//洗牌Random r = new Random();for (int i = cards.size()-1; i > 0 ; i--) {//randomIndex的范围是0~i-1;int randomIndex = r.nextInt(i);swarp(cards,i,randomIndex);}System.out.println("洗牌后：");System.out.println(cards);//3人抽牌,每轮每人抽一张，抽5轮//二维数组List<Card> hand0 = new ArrayList<>();List<Card> hand1 = new ArrayList<>();List<Card> hand2 = new ArrayList<>();List<List<Card>> players = new ArrayList<>();players.add(hand0);players.add(hand1);players.add(hand2);for (int i = 0; i < 5; i++) {for (int j = 0; j < players.size(); j++) {//每次都从牌的第一张开始抽，抽完了，第二张就变成了第一张Card select = cards.remove(0);players.get(j).add(select);}}for (int i = 0; i < players.size(); i++) {System.out.println("第"+(i+1)+"个人的牌:"+players.get(i));}System.out.println("剩余的牌："+cards);}
}

运行结果：