顺序表
Anthony_Stark_Li Anthony_Stark_Li 0 评论 programming 15 阅读

顺序表

一、模拟实现 MyArrayList

核心设计思路

模拟 ArrayList 的核心是「基于普通数组 + 有效元素计数器」，关键实现以下功能：

  1. 初始化数组（默认容量 + 指定容量构造）
  2. 数组满时自动扩容（通常扩容为原容量的 2 倍或 1.5 倍）
  3. 增删改查等基本操作（保证有效元素计数器 count 正确更新）
  4. 合法性校验（下标、数组为空/已满等场景）

完整实现代码

import java.util.Arrays;

/**
 * 模拟实现 ArrayList（存储 int 类型元素，简化核心逻辑）
 * 核心：普通数组 + count 有效元素计数器，支持动态扩容和基本操作
 */
public class MyArrayList {
    // 底层存储元素的普通数组
    public int[] arr;
    // 记录有效元素个数（区别于数组容量，避免遍历未赋值的默认值）
    public int count = 0;
    // 默认初始容量（JDK 8 中 ArrayList 默认初始容量为 10，此处简化为 3）
    public static final int DEFAULT_CAPACITY = 3;

    /**
     * 无参构造：创建默认容量的数组
     */
    public MyArrayList() {
        this.arr = new int[DEFAULT_CAPACITY];
    }

    /**
     * 有参构造：创建指定容量的数组
     * @param capacity 初始数组容量
     */
    public MyArrayList(int capacity) {
        // 合法性校验：避免传入负数容量
        if (capacity < 0) {
            throw new IllegalArgumentException("数组容量不能为负数：" + capacity);
        }
        this.arr = new int[capacity];
    }

    /**
     * 下标合法性检测（仅检测是否为负数）
     * @param pos 待检测的下标
     * @return 合法返回 1，非法返回 -1
     */
    public int indexDetection(int pos) {
        if (pos < 0) {
            return -1;
        }
        return 1;
    }

    /**
     * 检测数组是否已满（有效元素个数 = 数组容量）
     * @param count 有效元素个数
     * @return 已满返回 true，未满返回 false
     */
    public boolean isArrayFull(int count) {
        return count == arr.length;
    }

    /**
     * 数组扩容：扩容为原容量的 2 倍（JDK 源码中为 1.5 倍）
     * @param oldArr 原数组
     */
    public void expandArray(int[] oldArr) {
        this.arr = Arrays.copyOf(oldArr, oldArr.length * 2);
    }

    /**
     * 检测数组是否为空（无有效元素）
     * @param count 有效元素个数
     * @return 为空返回 -1，非空返回 1
     */
    public int isArrayEmpty(int count) {
        if (count == 0) {
            return -1;
        }
        return 1;
    }

    /**
     * 尾插元素：在数组末尾新增元素（最常用，效率最高）
     * @param data 待新增的元素
     */
    public void add(int data) {
        // 数组已满，先扩容再插入
        if (isArrayFull(count)) {
            expandArray(this.arr);
        }
        // 尾插元素并更新有效元素个数
        this.arr[this.count++] = data;
    }

    /**
     * 指定位置插入元素（需移动元素，效率较低）
     * @param pos  插入位置下标
     * @param data 待插入的元素
     */
    public void add(int pos, int data) {
        // 1. 检测下标是否为负数
        if (indexDetection(pos) == -1) {
            throw new IllegalArgumentException("输入下标非法：不能为负数");
        }
        // 2. 检测插入位置是否超出有效元素范围（允许插入到 count 位置，即尾插）
        if (pos > this.count) {
            throw new IllegalArgumentException("输入下标非法：超出有效元素范围");
        }
        // 3. 数组已满，先扩容
        if (isArrayFull(count)) {
            expandArray(this.arr);
        }
        // 4. 从后往前移动元素，腾出插入位置（避免覆盖元素）
        for (int i = this.count - 1; i >= pos; i--) {
            this.arr[i + 1] = this.arr[i];
        }
        // 5. 插入元素并更新有效元素个数
        this.arr[pos] = data;
        this.count++;
    }

    /**
     * 判断是否包含某个元素
     * @param data 待查找的元素
     * @return 包含返回 true，不包含返回 false
     */
    public boolean contains(int data) {
        // 仅遍历有效元素，无需遍历整个数组（优化效率，避免访问默认值 0）
        for (int i = 0; i < this.count; i++) {
            if (this.arr[i] == data) {
                return true;
            }
        }
        return false;
    }

    /**
     * 查找元素第一次出现的下标
     * @param data 待查找的元素
     * @return 找到返回对应下标，未找到返回 -1
     */
    public int indexOf(int data) {
        for (int i = 0; i < this.count; i++) {
            if (this.arr[i] == data) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 获取指定下标对应的元素
     * @param pos 待查找的下标
     * @return 对应下标的元素
     */
    public int get(int pos) {
        // 1. 检测下标是否为负数
        if (indexDetection(pos) == -1) {
            throw new IllegalArgumentException("输入下标非法：不能为负数");
        }
        // 2. 检测数组是否为空
        if (isArrayEmpty(this.count) == -1) {
            throw new RuntimeException("空数组，无法查询");
        }
        // 3. 检测下标是否超出有效元素范围
        if (pos >= this.count) {
            throw new IllegalArgumentException("输入下标非法：超出有效元素范围");
        }
        // 4. 返回对应元素
        return this.arr[pos];
    }

    /**
     * 删除第一次出现的指定元素
     * @param data 待删除的元素
     */
    public void remove(int data) {
        // 1. 查找元素对应的下标
        int targetIndex = indexOf(data);
        if (targetIndex == -1) {
            System.out.println("未出现该数据，无需删除");
            return;
        }
        // 2. 从前往后移动元素，覆盖待删除元素
        for (int i = targetIndex; i < this.count - 1; i++) {
            this.arr[i] = this.arr[i + 1];
        }
        // 3. 更新有效元素个数（避免脏数据被访问）
        this.count--;
    }

    /**
     * 获取有效元素的个数
     * @return 有效元素个数
     */
    public int size() {
        return this.count;
    }

    /**
     * 清空数组（仅重置有效元素个数，无需修改数组内容，效率更高）
     */
    public void clear() {
        this.count = 0;
    }

    /**
     * 重写 toString 方法，优化展示效果（仅打印有效元素）
     * @return 格式化的字符串
     */
    @Override
    public String toString() {
        // 仅复制有效元素，避免打印未赋值的默认值 0
        int[] validArr = Arrays.copyOf(this.arr, this.count);
        return "MyArrayList{arr=" + Arrays.toString(validArr) + ", count=" + count + "}";
    }
}

关键注意点

  1. count 计数器的重要性：count 记录有效元素个数，所有操作（增、删、查）都应围绕 count 展开，而非数组长度 arr.length，避免访问未赋值的默认值。
  2. 扩容逻辑：数组满时需先扩容再插入元素，Arrays.copyOf() 是简化扩容的关键方法，底层会创建新数组并复制原数组元素。
  3. 指定位置插入/删除：插入需「从后往前」移动元素，删除需「从前往后」移动元素，避免元素覆盖。
  4. 合法性校验：下标不能为负数、不能超出有效元素范围，空数组不能执行查询操作，这些校验能提高程序的健壮性。

二、顺序表使用

手动模拟是为了理解原理，实际开发中我们直接使用 JDK 提供的 ArrayList，下面介绍其核心用法。

三种构造方法

推荐「面向接口 List 编程」，提高代码可扩展性，三种构造方法满足不同场景需求。

import java.util.ArrayList;
import java.util.List;

/**
 * ArrayList 构造方法演示
 */
public class ArrayListConstructorDemo {
    public static void main(String[] args) {
        // 1. 无参构造：默认初始容量 10（JDK 8），后续扩容为 1.5 倍
        List<Integer> arrayList1 = new ArrayList<>();

        // 2. 有参构造：指定初始容量，避免频繁扩容，提高效率（大数据量场景推荐）
        List<Integer> arrayList2 = new ArrayList<>(10);
        arrayList2.add(1);
        arrayList2.add(2);
        arrayList2.add(3);

        // 3. 有参构造：利用其他集合构建 ArrayList（复制其他集合的元素）
        List<Integer> arrayList3 = new ArrayList<>(arrayList2);

        // 打印结果
        System.out.println("arrayList1：" + arrayList1);
        System.out.println("arrayList2：" + arrayList2);
        System.out.println("arrayList3：" + arrayList3);
    }
}

常用核心方法

增、删、改、查是 ArrayList 的核心操作，重点注意「删除元素时的装箱问题」（避免与下标删除混淆）。

import java.util.ArrayList;
import java.util.List;

/**
 * ArrayList 常用方法演示
 */
public class ArrayListCommonMethodDemo {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();

        // 1. 增：添加元素
        list.add(1); // 尾插元素（效率最高）
        list.add(1, 2); // 指定下标插入元素（下标不能超出有效元素范围）
        System.out.println("添加元素后：" + list);

        // 2. 删：删除元素（注意装箱，避免与下标删除混淆）
        list.remove(1); // 删除指定下标的元素
        list.add(2);
        list.remove((Integer) 2); // 删除第一个出现的指定元素（需装箱为 Integer）
        System.out.println("删除元素后：" + list);

        // 3. 改：修改指定下标的元素
        list.set(0, 100);
        System.out.println("修改元素后：" + list);

        // 4. 查：获取元素/查找元素
        int element = list.get(0); // 获取指定下标的元素
        boolean isContain = list.contains(100); // 判断是否包含指定元素
        int index = list.indexOf(100); // 查找元素第一次出现的下标
        System.out.println("指定下标元素：" + element + "，是否包含 100：" + isContain + "，100 的下标：" + index);

        // 5. 其他常用方法
        List<Integer> subList = list.subList(0, 1); // 截取子集合 [0,1)，左闭右开
        int size = list.size(); // 获取有效元素个数
        boolean isEmpty = list.isEmpty(); // 判断是否为空集合
        list.clear(); // 清空集合所有元素
        System.out.println("子集合：" + subList + "，集合大小：" + size + "，是否为空：" + isEmpty + "，清空后：" + list);
    }
}

四种遍历方式

ArrayList 支持四种遍历方式，不同场景选择不同方式，重点注意「迭代器遍历的并发修改问题」。

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 * ArrayList 遍历方式演示
 */
public class ArrayListTraversalDemo {
    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);

        // 方式 1：普通 for 循环（支持反向遍历，可通过下标修改元素）
        System.out.print("普通 for 循环：");
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();

        // 方式 2：增强 for 循环（语法简洁，无法通过下标修改元素，底层是迭代器）
        System.out.print("增强 for 循环：");
        for (Integer num : list) {
            System.out.print(num + " ");
        }
        System.out.println();

        // 方式 3：Iterator 迭代器（支持删除元素，仅能正向遍历，避免并发修改异常）
        System.out.print("Iterator 迭代器：");
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
        System.out.println();

        // 方式 4：ListIterator 列表迭代器（支持正向/反向遍历，支持添加、修改、删除元素）
        System.out.print("ListIterator 正向遍历：");
        ListIterator<Integer> lit1 = list.listIterator();
        while (lit1.hasNext()) {
            System.out.print(lit1.next() + " ");
        }
        System.out.println();

        System.out.print("ListIterator 反向遍历：");
        ListIterator<Integer> lit2 = list.listIterator(list.size());
        while (lit2.hasPrevious()) {
            System.out.print(lit2.previous() + " ");
        }
        System.out.println();
    }
}

三、顺序表实战：扑克牌游戏

为了巩固 ArrayList 的使用，我们来实现一个简单的扑克牌游戏，包含「买牌、洗牌、发牌」三个核心功能。

卡牌类 Card（封装卡牌属性）

/**
 * 卡牌类：封装卡牌的花色和点数
 */
public class Card {
    // 卡牌点数
    public int rank;
    // 卡牌花色
    public String suit;

    /**
     * 构造方法：初始化卡牌的点数和花色
     * @param rank 点数
     * @param suit 花色
     */
    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }

    /**
     * 重写 toString 方法，优化卡牌展示效果
     * @return 格式化的卡牌字符串
     */
    @Override
    public String toString() {
        // 特殊处理大小王
        if (rank == 0) {
            return suit;
        }
        return rank + suit;
    }
}

扑克牌游戏核心 CardGame（买牌 + 洗牌）

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 扑克牌游戏核心类：负责买牌、洗牌
 */
public class CardGame {
    // 卡牌花色数组（常量，不可修改）
    private static final String[] SUITS = {"♥", "♦", "♠", "♣"};

    /**
     * 交换集合中两个位置的元素（用于洗牌）
     * @param list 卡牌集合
     * @param i 位置 1
     * @param j 位置 2
     */
    private void swap(List<Card> list, int i, int j) {
        Card tmp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, tmp);
    }

    /**
     * 买牌：生成一副完整的扑克牌（54 张：4 种花色×13 个点数 + 大小王）
     * @return 完整的扑克牌集合
     */
    public List<Card> buyCard() {
        List<Card> cardList = new ArrayList<>(54);

        // 生成 4 种花色、1-13 点的卡牌
        for (String suit : SUITS) {
            for (int rank = 1; rank <= 13; rank++) {
                cardList.add(new Card(rank, suit));
            }
        }

        // 添加大小王
        cardList.add(new Card(0, "小王"));
        cardList.add(new Card(0, "大王"));

        return cardList;
    }

    /**
     * 洗牌：打乱卡牌集合的顺序（从后往前交换，提高随机性）
     * @param list 待洗牌的卡牌集合
     */
    public void shuffle(List<Card> list) {
        // 空集合或只有一个元素，无需洗牌
        if (list == null || list.size() <= 1) {
            return;
        }

        Random random = new Random();
        // 从后往前遍历，每次交换当前元素与前面随机一个元素
        for (int i = list.size() - 1; i > 0; i--) {
            int randomIndex = random.nextInt(i); // 生成 [0, i) 之间的随机下标
            swap(list, i, randomIndex);
        }
    }

    /**
     * 构建洗好的扑克牌（买牌 + 洗牌）
     * @return 洗好的扑克牌集合
     */
    public List<Card> buildShuffledCard() {
        List<Card> cardList = buyCard();
        shuffle(cardList);
        return cardList;
    }
}

测试类 TestCardGame（发牌 + 打印结果）

import java.util.ArrayList;
import java.util.List;

/**
 * 扑克牌游戏测试类：负责发牌、打印结果
 */
public class TestCardGame {
    public static void main(String[] args) {
        // 1. 生成洗好的扑克牌
        CardGame cardGame = new CardGame();
        List<Card> cardList = cardGame.buildShuffledCard();

        // 2. 初始化 3 个玩家的手牌集合
        List<List<Card>> playerHands = new ArrayList<>(3);
        playerHands.add(new ArrayList<>());
        playerHands.add(new ArrayList<>());
        playerHands.add(new ArrayList<>());

        // 3. 发牌：3 个玩家轮流抓牌，每人 18 张（54 张 ÷ 3 人 = 18 张/人）
        for (int i = 0; i < 18; i++) {
            for (int j = 0; j < 3; j++) {
                // 移除集合第一个元素（模拟发牌），并添加到对应玩家的手牌中
                Card card = cardList.remove(0);
                playerHands.get(j).add(card);
            }
        }

        // 4. 打印玩家手牌
        System.out.println("第一个人的牌：" + playerHands.get(0));
        System.out.println("第二个人的牌：" + playerHands.get(1));
        System.out.println("第三个人的牌：" + playerHands.get(2));
    }
}

运行结果

第一个人的牌：[6♥, 13♥, 2♠, 9♣, 3♠, 2♦, 12♠, 4♦, 12♦, 9♦, 5♠, 8♠, 11♠, 1♣, 4♣, 7♣, 10♣, 13♣]
第二个人的牌：[3♦, 3♥, 8♥, 11♥, 1♦, 11♦, 8♦, 10♦, 6♠, 13♠, 2♥, 9♠, 4♥, 2♣, 5♣, 8♣, 11♣, 小王]
第三个人的牌：[7♦, 5♥, 1♥, 12♥, 10♥, 5♦, 9♥, 13♦, 1♠, 4♠, 7♠, 10♠, 7♥, 3♣, 6♣, 6♦, 12♣, 大王]
文章标签
#Datastructure#Java
许可协议
本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。
泛型&反射&枚举&lambda表达式 2025-07-24
链表 2025-08-04

评论区