文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >数据结构与算法--ArrayList与线性表

数据结构与算法--ArrayList与线性表

作者头像
Han.miracle
发布于 2025-12-23 10:06:11
发布于 2025-12-23 10:06:11
1790
举报
文章被收录于专栏：Java核心技术图谱：原理·对比·避坑Java核心技术图谱：原理·对比·避坑

一.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个具有相同类型元素的有限序列，在该序列上可以执行增删 改查以及变量等操作

2、常见接口介绍

List中提供了好的方法，具体如下：

虽然方法比较多，但是常用方法如下：

3、List的使用

#注：List是个接口，并不能直接用来实例化。

就比如说是这样：是不对的

4.List 的五种遍历方法：

1.迭代器
代码语言：javascript
复制
import java.util.*;

public class IteratorExample {
    public static void main(String[] args) {
        List<String> fruits = Arrays.asList("Apple", "Banana", "Cherry", "Date", "Elderberry");
        
        System.out.println("=== 迭代器 (Iterator) 遍历 ===");
        
        // 创建迭代器对象
        Iterator<String> iterator = fruits.iterator();
        
        // 使用 hasNext() 和 next() 遍历
        System.out.print("遍历结果: ");
        while (iterator.hasNext()) {
            String fruit = iterator.next();
            System.out.print(fruit + " ");
        }
        
        System.out.println("\n");
    }
}

2.列表迭代器

代码语言：javascript
复制
import java.util.*;

public class ListIteratorExample {
    public static void main(String[] args) {
        List<String> fruits = Arrays.asList("Apple", "Banana", "Cherry", "Date", "Elderberry");
        
        System.out.println("=== 列表迭代器 (ListIterator) 遍历 ===");
        
        // 创建列表迭代器
        ListIterator<String> listIterator = fruits.listIterator();
        
        // 1. 正向遍历
        System.out.print("正向遍历: ");
        while (listIterator.hasNext()) {
            String fruit = listIterator.next();
            System.out.print(fruit + " ");
        }
        
        // 2. 反向遍历
        System.out.print("\n反向遍历: ");
        while (listIterator.hasPrevious()) {
            String fruit = listIterator.previous();
            System.out.print(fruit + " ");
        }
        
        System.out.println("\n");
    }
}

3.for each

代码语言：javascript
复制
import java.util.*;

public class ForEachExample {
    public static void main(String[] args) {
        List<String> fruits = Arrays.asList("Apple", "Banana", "Cherry", "Date", "Elderberry");
        
        System.out.println("=== for-each 循环遍历 ===");
        
        // 使用 for-each 循环
        System.out.print("遍历结果: ");
        for (String fruit : fruits) {
            System.out.print(fruit + " ");
        }
        
        System.out.println("\n");
    }
}

4.Lambda表达式

代码语言：javascript
复制
import java.util.*;

public class LambdaExample {
    public static void main(String[] args) {
        List<String> fruits = Arrays.asList("Apple", "Banana", "Cherry", "Date", "Elderberry");
        
        System.out.println("=== Lambda 表达式遍历 ===");
        
        // 方法1：直接使用 Lambda 表达式
        System.out.print("Lambda 遍历: ");
        fruits.forEach(fruit -> System.out.print(fruit + " "));
        
        System.out.println();
        
        // 方法2：使用方法引用（更简洁）
        System.out.print("方法引用: ");
        fruits.forEach(System.out::print);
        System.out.print(" ");
        
        System.out.println("\n");
    }
}
方法 2：使用方法引用（System.out::print）
1. 方法引用的本质

方法引用是「Lambda 表达式的进一步简化」—— 当 Lambda 表达式的代码体只是单纯调用一个已存在的方法，并且 Lambda 的参数「正好是这个方法的参数」时，就可以用方法引用替代 Lambda。

它的语法格式（这里是「对象：：实例方法」）：

  • System.out：是一个「对象」（PrintStream 类的实例，对应 System 类的静态变量 out）；
  • print：是 PrintStream 类的「实例方法」（void print(String s)，接收一个 String 参数，无返回值）。
2. 对应到代码的拆解
代码语言：javascript
复制
fruits.forEach(System.out::print);
  • 集合中的每个元素（比如 "Apple"），会直接作为参数传给 System.out.print() 方法；
  • 这等价于 Lambda 表达式：fruit -> System.out.print(fruit)（因为 Lambda 没有任何额外逻辑，只是把参数传给现有方法）。

5.普通for

代码语言：javascript
复制
import java.util.*;

public class NormalForExample {
    public static void main(String[] args) {
        List<String> fruits = Arrays.asList("Apple", "Banana", "Cherry", "Date", "Elderberry");
        
        System.out.println("=== 普通 for 循环遍历 ===");
        
        // 使用普通 for 循环
        System.out.print("遍历结果: ");
        for (int i = 0; i < fruits.size(); i++) {
            String fruit = fruits.get(i);
            System.out.print(fruit + " ");
        }
        
        System.out.println("\n");
    }
}

总结：

代码语言：javascript
复制
import java.util.*;

public class ListTraversalExample {
    public static void main(String[] args) {
        // 创建示例列表
        List<String> fruits = new ArrayList<>();
        Collections.addAll(fruits, "Apple", "Banana", "Cherry", "Date", "Elderberry");
        
        System.out.println("列表内容: " + fruits);
        System.out.println("=".repeat(50));
        
        // 1. 迭代器遍历 (Iterator)
        System.out.println("1. 迭代器遍历 (Iterator):");
        iteratorTraversal(fruits);
        System.out.println();
        
        // 2. 列表迭代器遍历 (ListIterator)
        System.out.println("2. 列表迭代器遍历 (ListIterator):");
        listIteratorTraversal(fruits);
        System.out.println();
        
        // 3. for-each 循环
        System.out.println("3. for-each 循环:");
        forEachLoopTraversal(fruits);
        System.out.println();
        
        // 4. Lambda 表达式遍历
        System.out.println("4. Lambda 表达式遍历:");
        lambdaTraversal(fruits);
        System.out.println();
        
        // 5. 普通 for 循环
        System.out.println("5. 普通 for 循环:");
        normalForLoopTraversal(fruits);
    }
    
    // 1. 迭代器遍历 (Iterator)
    public static void iteratorTraversal(List<String> list) {
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String fruit = iterator.next();
            System.out.print(fruit + " ");
            
            // 可以在遍历时删除元素（安全）
            if ("Banana".equals(fruit)) {
                iterator.remove();  // 删除当前元素
            }
        }
        System.out.println("\n删除Banana后列表: " + list);
    }
    
    // 2. 列表迭代器遍历 (ListIterator)
    public static void listIteratorTraversal(List<String> list) {
        // 正向遍历
        System.out.print("正向遍历: ");
        ListIterator<String> listIterator = list.listIterator();
        while (listIterator.hasNext()) {
            String fruit = listIterator.next();
            System.out.print(fruit + " ");
            
            // 可以在遍历时修改元素
            if ("Cherry".equals(fruit)) {
                listIterator.set("Cherry(Modified)");  // 修改当前元素
            }
        }
        
        // 反向遍历
        System.out.print("\n反向遍历: ");
        while (listIterator.hasPrevious()) {
            String fruit = listIterator.previous();
            System.out.print(fruit + " ");
        }
        
        // 获取索引
        System.out.print("\n遍历并显示索引: ");
        listIterator = list.listIterator();
        while (listIterator.hasNext()) {
            int index = listIterator.nextIndex();
            String fruit = listIterator.next();
            System.out.print("[" + index + "]" + fruit + " ");
        }
        System.out.println("\n修改Cherry后列表: " + list);
    }
    
    // 3. for-each 循环
    public static void forEachLoopTraversal(List<String> list) {
        System.out.print("for-each遍历: ");
        for (String fruit : list) {
            System.out.print(fruit + " ");
            
            // ❌ 注意：for-each循环中不能直接删除元素，会抛出ConcurrentModificationException
            // if ("Date".equals(fruit)) {
            //     list.remove(fruit);  // 会抛出异常
            // }
        }
        
        // 可以使用新集合记录要删除的元素，之后批量删除
        List<String> toRemove = new ArrayList<>();
        for (String fruit : list) {
            if ("Date".equals(fruit)) {
                toRemove.add(fruit);
            }
        }
        list.removeAll(toRemove);
        System.out.println("\n删除Date后列表: " + list);
    }
    
    // 4. Lambda 表达式遍历
    public static void lambdaTraversal(List<String> list) {
        // 方法1: forEach + Lambda表达式
        System.out.print("Lambda遍历: ");
        list.forEach(fruit -> {
            System.out.print(fruit + " ");
        });
        
        // 方法2: forEach + 方法引用
        System.out.print("\n方法引用遍历: ");
        list.forEach(System.out::print);
        System.out.print(" ");
        
        // 方法3: 使用Stream API
        System.out.print("\nStream遍历: ");
        list.stream()
            .filter(fruit -> fruit.length() > 5)
            .forEach(fruit -> System.out.print(fruit + "(长单词) "));
        
        System.out.println();
    }
    
    // 5. 普通 for 循环
    public static void normalForLoopTraversal(List<String> list) {
        // 方式1: 使用索引
        System.out.print("普通for循环(索引): ");
        for (int i = 0; i < list.size(); i++) {
            String fruit = list.get(i);
            System.out.print(fruit + " ");
            
            // 可以安全地删除元素（需要调整索引）
            if ("Elderberry".equals(fruit)) {
                list.remove(i);
                i--;  // 删除后索引回退
            }
        }
        
        // 方式2: 倒序遍历（删除元素时更方便）
        System.out.print("\n倒序遍历删除: ");
        List<String> tempList = new ArrayList<>(list);
        for (int i = tempList.size() - 1; i >= 0; i--) {
            String fruit = tempList.get(i);
            System.out.print(fruit + " ");
            // 倒序删除不需要调整索引
        }
        
        System.out.println("\n删除Elderberry后列表: " + list);
    }
}

二、线性表

线性表 （ linear list ） 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

三、顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

代码语言：javascript
复制
public class List {
     private int[] array;
     private int size;
 
    // 默认构造方法
     List(){
     }
 
     // 将顺序表的底层容量设置为initcapacity
     List(int initcapacity){
     }
 
     // 新增元素,默认在数组最后新增
    public void add(int data) {
        if(isFull()) {
            grow();
        }
        this.array[this.usedSize] = data;
        this.usedSize++;
    }
 
    private void grow() {
        this.array = Arrays.copyOf(this.array,
                2*this.array.length);
    }
 
    public boolean isFull() {
        return this.usedSize == array.length;
    }
 
 
    private void checkPos(int pos) throws PosIllegal{
        if(pos < 0 || pos > usedSize) {
            throw new PosIllegal("Pos位置不合法！！");
        }
    }
 
     // 在 pos 位置新增元素
    public void add(int pos, int data) {
        try {
            checkPos(pos);
            if(isFull()) {
                grow();
            }
            //挪动元素
            for(int i = usedSize-1;i >= pos; i--) {
                array[i+1] = array[i];
            }
 
            array[pos] = data;
 
            usedSize++;
        }catch (PosIllegal e) {
            System.out.println("插入元素pos位置不合法..");
            e.printStackTrace();
        }
    }
 
     // 判定是否包含某个元素
    public boolean contains(int toFind) {
        //array   usedSize
        for (int i = 0; i < usedSize; i++) {
            if(array[i] == toFind) {
                return true;
            }
        }
        return false;
    }
 
     // 查找某个元素对应的位置
     //否则返回-1
    public int indexOf(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if(array[i] == toFind) {
                return i;
            }
        }
        return -1;
    }
 
     // 获取 pos 位置的元素
     //否则返回-1
    public int get(int pos) {
        try {
            checkEmpty();
            checkPos2(pos);
            return array[pos];
        }catch (PosIllegal e) {
            e.printStackTrace();
        }catch (EmptyException e) {
            e.printStackTrace();
        }
        return -1;
    }
 
    private void checkEmpty() {
        if(isEmpty()) {
            throw new EmptyException("顺序表为空!");
        }
    }
 
    public boolean isEmpty() {
        return usedSize == 0;
    }
 
     // 给 pos 位置的元素设为 value
    public void set(int pos, int value) {
        try {
            checkEmpty();
            checkPos2(pos);
            array[pos] = value;
        }catch (PosIllegal e) {
            e.printStackTrace();
        }catch (EmptyException e) {
            e.printStackTrace();
        }
    }
 
     //删除第一次出现的关键字key
    public void remove(int toRemove) {
        try {
            checkEmpty();
            int pos = indexOf(toRemove);
            if(pos == -1) {
                return;
            }
            for (int i = pos; i < usedSize-1; i++) {
                array[i] = array[i+1];
            }
            usedSize--;
        }catch (EmptyException e) {
            e.printStackTrace();
        }
    }
 
     // 获取顺序表长度
    public int size() {
        return this.usedSize;
    }
 
     // 清空顺序表
    public void clear() {
       /* for (int i = 0; i < usedSize; i++) {
            array[i] = null;
        }*/
        usedSize = 0;
    }
 
     // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(array[i]+" ");
        }
       /*
       这里面所有都是 0
       for (int x : array) {
            System.out.print(x+" ");
        }*/
    }
 }

四、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底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

1、ArrayList的使用

1.1、ArrayList的构造
代码语言：javascript
复制
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);
}
2、ArrayList常见操作

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

代码语言：javascript
复制
public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("JavaSE");
    list.add("JavaWeb");
    list.add("JavaEE");
    list.add("JVM");
    list.add("测试课程");
    System.out.println(list);
    
    // 获取list中有效元素个数
    System.out.println(list.size());
    
    // 获取和设置index位置上的元素，注意index必须介于[0, size)间
    System.out.println(list.get(1));
    list.set(1, "JavaWEB");
    System.out.println(list.get(1));
    
    // 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置
    list.add(1, "Java数据结构");
    System.out.println(list);
    // 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置
    list.remove("JVM");
    System.out.println(list);
    // 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常
    list.remove(list.size()-1);
    System.out.println(list);
    // 检测list中是否包含指定元素，包含返回true，否则返回false
    if(list.contains("测试课程")){
        list.add("测试课程");
    }
    
    // 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找
    list.add("JavaSE");
    System.out.println(list.indexOf("JavaSE"));
    System.out.println(list.lastIndexOf("JavaSE"));
    
    // 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组
    List<String> ret = list.subList(0, 4);
    System.out.println(ret);
    
    list.clear();
    System.out.println(list.size());
3、ArrayList的遍历

ArrayList 可以使用种方式遍历：for循环+下标、foreach、使用迭代器，collection使用匿名内部类和Lambda遍历

常见的：for循环+下标、foreach、使用迭代器如下

代码语言：javascript
复制
 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) {
        System.out.print(integer + " ");
    }
    System.out.println();
    //使用迭代器
    Iterator<Integer> it = list.listIterator();
    while(it.hasNext()){
        System.out.print(it.next() + " ");
    }
    System.out.println();

注意：迭代器的遍历：

1.报错NoSuchElementException

原因：未通过hasNext()判断是否存在下一个元素，直接调用next()；当迭代器已无剩余元素时，next()会抛出此异常。

正确用法：遍历中需先通过hasNext()校验，再调用next()获取元素

代码语言：javascript
复制
Iterator<Integer> it = list.iterator();
while (it.hasNext()) { // 先判断是否有下一个元素
    Integer num = it.next(); // 再获取元素
}

2.遍历器遍历完毕，指针不会复位

原因：迭代器是 “一次性” 对象，遍历过程中指针会持续向后移动；遍历结束后指针停留在最后一个元素之后，无法自动回到起始位置。

正确用法：若需重新遍历集合，需重新获取新的迭代器实例

代码语言：javascript
复制
// 第一次遍历
Iterator<Integer> it1 = list.iterator();
while (it1.hasNext()) { ... }

// 重新获取迭代器以二次遍历
Iterator<Integer> it2 = list.iterator();
while (it2.hasNext()) { ... }

3.循环中只能使用一次next方法

原因：每次调用next()都会使指针向后移动一位；若循环内多次调用next()，会跳过元素或因无剩余元素抛出NoSuchElementException。

代码语言：javascript
复制
while (it.hasNext()) {
    Integer num = it.next(); // 仅调用一次next()
    System.out.println(num);
    // 基于num的其他操作
}

4.迭代器在进行遍历的时候，不能使用集合的方法进行增加或删除

原因：迭代器依赖集合的结构稳定性，直接调用集合的add()/remove()会触发ConcurrentModificationException（快速失败机制）。

正确用法：若需删除元素，使用迭代器自身的remove()方法：

代码语言：javascript
复制
while (it.hasNext()) {
    Integer num = it.next();
    if (num == 10) {
        it.remove(); // 用迭代器的remove()，而非集合的list.remove()
    }
}
代码语言：javascript
复制
// 完整语法
list.forEach(new Consumer<String>() {
    @Override
    public void accept(String s) {
        // 对每个元素执行的操作
        System.out.println(s);
    }
    
    @Override  // Consumer接口还有andThen方法，但通常不需要重写
    public Consumer<String> andThen(Consumer<? super String> after) {
        return Consumer.super.andThen(after);
    }
});
代码语言：javascript
复制
ArrayList<Integer> list = new ArrayList<>();
list.add(11);
list.add(17);

// 方式1：匿名内部类（对应你之前写的代码形式）
list.forEach(new Consumer<Integer>() {
    @Override
    public void accept(Integer s) {
        System.out.println(s); // 处理每个元素（如打印）
    }
});

匿名内部类：

代码语言：javascript
复制
ArrayList<Integer> list = new ArrayList<>();
list.add(11);
list.add(17);

// 方式1：匿名内部类（对应你之前写的代码形式）
list.forEach(new Consumer<Integer>() {
    @Override
    public void accept(Integer s) {
        System.out.println(s); // 处理每个元素（如打印）
    }
});

// 方式2：Lambda 表达式（更简洁，推荐）
list.forEach(s -> System.out.println(s));

ArrayList的扩容机制 请问：下面代码有缺陷吗？为什么？

代码语言：javascript
复制
 public static void main(String[] args) {
     List<Integer> list = new ArrayList<>();
     for (int i = 0; i < 100; i++) {
         list.add(i);
     }
 }
4、ArrayList的扩容机制
  • 若扩容后的 1.5 倍容量仍小于最小需求容量（如一次性添加多个元素，需要的容量更大），则新容量直接等于最小需求容量。
  • 若原容量为0（无参构造首次添加元素），则直接扩容至10（而非 1.5 倍，因为 0 的 1.5 倍还是 0）。
  • 默认情况下，扩容后的新容量为原容量的 1.5 倍

ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。以下是ArrayList源码中扩容方式：

代码语言：javascript
复制
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 code
     if (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的相关练习

五、ArrayList的相关练习

1、杨辉三角

（118. 杨辉三角 - 力扣（LeetCode））

这里就是外侧全是1，其他的分别是上面紧挨着的两个的加和。但是，显然我们不能像左图一样创建顺序表，可以转换成如右图所示的样式！！！如右图，最外侧都为1，若位置为（i，j）,则[i][j] = [i-1][j] + [i-1][j-1]

因此，我们创建一个空列表ret，用来存储所有的行（每行是一个整数列表）。

先处理第一行，元素为1；再循环生成一共numRows行，将每行的第一个元素添加为1。

利用上一行计算中间元素，最后添加上尾巴（1）。

代码语言：javascript
复制
class Solution {
    public static 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;
    }
}
2、简单的洗牌算法

（一副新牌，四种花色（♥，♦，♠，♣），数值分别为1--13，经过一系列的洗牌之后，分别发给三个人每人5张（轮流抓牌），最后展示剩余牌和三人手里的牌）

代码语言：javascript
复制
public class Card {
    private String suit;//花色
    private int rank;   //牌面值
 
    public Card(String suit, int rank) {
        this.suit = suit;
        this.rank = rank;
    }
 
    @Override
    public String toString() {
        /*return "Card{" +
                "suit='" + suit + '\'' +
                ", rank=" + rank +
                '}';*/
        return String.format("[%s %d]", suit, rank);
    }
}
代码语言：javascript
复制
import java.util.List;
import java.util.ArrayList;
import java.util.Random;
 
public class CardDemo {
 
    public static final String[] suits = {"♥","♠","♣","♦"};
    //买来一副新牌
    public List<Card> buyCard() {
        List<Card> cardList = new ArrayList<>(52);
        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;
    }
}
代码语言：javascript
复制
import java.util.*;
public class Test {
    public static void main(String[] args) {
        CardDemo cardDemo = new CardDemo();
        //1. 买52张牌
        List<Card> cardList = cardDemo.buyCard();
        System.out.println("刚买回来的牌：");
        System.out.println(cardList);
        //2. 洗牌
        cardDemo.shuffle(cardList);
        System.out.println("洗过的牌:");
        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);
    }
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-12-09，如有侵权请联系 cloudcommunity@tencent.com 删除
arraylist
system
遍历
接口
数据结构与算法

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

arraylist
system
遍历
接口
数据结构与算法
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 一.List的介绍
    • 2、常见接口介绍
    • 3、List的使用
    • 4.List 的五种遍历方法：
      • 1.迭代器
      • 方法 2：使用方法引用（System.out::print）
  • 二、线性表
  • 三、顺序表
  • 四、ArrayList的简介
    • 1、ArrayList的使用
      • 1.1、ArrayList的构造
      • 2、ArrayList常见操作
      • 3、ArrayList的遍历
      • 4、ArrayList的扩容机制
  • 五、ArrayList的相关练习
    • 五、ArrayList的相关练习
      • 1、杨辉三角
      • 2、简单的洗牌算法
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论