【数据结构】 ArrayList简介与实战

这篇具有很好参考价值的文章主要介绍了【数据结构】 ArrayList简介与实战。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

什么是ArrayList

在集合框架中,ArrayList是一个普通的类,实现了List接口,具体框架图如下
【数据结构】 ArrayList简介与实战,数据结构,数据结构,windows,ArrayList,开发语言,java

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简介与实战,数据结构,数据结构,windows,ArrayList,开发语言,java

无参构造

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虽然提供的方法比较多,但是常用方法如下所示
【数据结构】 ArrayList简介与实战,数据结构,数据结构,windows,ArrayList,开发语言,java
例如我们有以下代码

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 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的具体使用

杨辉三角

题目描述

给定一个非负整数 numRows,生成「杨辉三角」的前 numRows 行。
【数据结构】 ArrayList简介与实战,数据结构,数据结构,windows,ArrayList,开发语言,java

【数据结构】 ArrayList简介与实战,数据结构,数据结构,windows,ArrayList,开发语言,java

题目解释:

题中返回值为 List<List< Integer > >,意思为返回一个List,这个List里面的每一个元素也为List

解法思路:

List里面放List可以类似与我们的二维数组,而我们的杨辉三角也可以看成一个二维数组

比如我们现在有一个List实例为ret,ret里面存放的是List类型的元素;ret的每一个List元素里存放的是杨辉三角每一行的所有元素
【数据结构】 ArrayList简介与实战,数据结构,数据结构,windows,ArrayList,开发语言,java
通过观察我们发现,杨辉三角的第一位总是1,并且每一行的最后一个与第一个都为1;其余的等于上面一行的两个数相加
【数据结构】 ArrayList简介与实战,数据结构,数据结构,windows,ArrayList,开发语言,java

代码实现:

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;
    }
}

简单的洗牌算法

【数据结构】 ArrayList简介与实战,数据结构,数据结构,windows,ArrayList,开发语言,java
比如我们现在需要实现一个简单的炸金花

Card类

那么我们首先第一步,我们得了解一下扑克,我们除开大小王,就剩下52张牌。每张牌都有相应的面额和花色
【数据结构】 ArrayList简介与实战,数据结构,数据结构,windows,ArrayList,开发语言,java
那么我们便可以建立一个Card类用于描述我们的扑克

class Card {
    public int rank; // 牌面值
    public String suit; // 花色
    @Override
    public 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));
            }
        }

效果展示:

【数据结构】 ArrayList简介与实战,数据结构,数据结构,windows,ArrayList,开发语言,java

完整代码:

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

class Card {
    public int rank; // 牌面值
    public String suit; // 花色
    @Override
    public 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简介与实战》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!文章来源地址https://www.toymoban.com/news/detail-655510.html

到了这里,关于【数据结构】 ArrayList简介与实战的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [JAVA数据结构]顺序表ArrayList

    目录 1.线性表 2.顺序表 3.ArrayList简介 4.ArrayList的使用  4.1ArrayList的构造方法 4.2ArrayList的常用操作 4.3ArrayList的遍历方法 4.4ArrayList的扩容机制 5.ArrayList的具体运用 ArrayList是一种基于数组的数据结构,是线性表的一种,也是顺序表。 通俗来说,线性表是一种线性结构,在逻辑上

    2023年04月26日
    浏览(40)
  • 【数据结构(二)】顺序表与ArrayList

    ❣博主主页: 33的博客❣ ▶文章专栏分类:数据结构◀ 🚚我的代码仓库: 33的代码仓库🚚 🫵🫵🫵 关注我带你学更多数据结构知识 在计算机科学中,数据结构是处理和组织数据的方法和技术。顺序表是一种常见的线性表数据结构,它基于数组实现,提供了快速的随机访问能力

    2024年04月12日
    浏览(38)
  • 【数据结构】从顺序表到ArrayList类

    线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,

    2024年01月24日
    浏览(46)
  • Java 中数据结构ArrayList的用法

    ArrayList 类是一个可以动态修改的数组,与普通数组的区别就是它是没有固定大小的限制,我们可以添加或删除元素。 ArrayList 继承了 AbstractList ,并实现了 List 接口。 add() 将元素插入到指定位置的 arraylist 中 addAll() 添加集合中的所有元素到 arraylist 中 clear() 删除 arraylist 中的所

    2024年02月10日
    浏览(42)
  • 数据结构 之 顺序表 ArrayList (Java)

    🎉欢迎大家观看AUGENSTERN_dc的文章(o゜▽゜)o☆✨✨ 🎉感谢各位读者在百忙之中抽出时间来垂阅我的文章,我会尽我所能向的大家分享我的知识和经验📖 🎉希望我们在一篇篇的文章中能够共同进步!!! 🌈个人主页: AUGENSTERN_dc 🔥个人专栏: C语言  |  Java | 数据结构 ⭐个

    2024年03月17日
    浏览(34)
  • Collection与数据结构 顺序表与ArrayList

    线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表: 顺序表、链表、栈、队列… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,

    2024年04月13日
    浏览(42)
  • 数据结构(Java实现)-ArrayList与顺序表

    什么是List List是一个接口,继承自Collection。 List的使用 List是个接口,并不能直接用来实例化。 如果要使用,必须去实例化List的实现类。在集合框架中,ArrayList和LinkedList都实现了List接口。 线性表 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 常见的线性表

    2024年02月11日
    浏览(36)
  • 探索Java集合框架—数据结构、ArrayList集合

    Java集合的使用相信大家都已经非常得心应手,但是我们怎么做到知其然,更知其所以然这种出神入化的境界呢?我们揭开集合框架底层神秘面纱来一探究竟 目录 一、背景介绍 二、思路方案 数据结构是什么? 数据结构可以分为线性和非线性两种数据结构 线性数据结构: 非

    2024年02月10日
    浏览(39)
  • [java数据结构] ArrayList和LinkedList介绍与使用

    (一) 线性表 (二) ArrayList 1. ArrayList的介绍 2. ArrayList的常见方法和使用 3. ArrayList的遍历 4. ArrayList的模拟实现 5. ArrayList的优缺点 (三) LinkedList 1. LinkedList的介绍 2. LinkedList的常见方法和使用 3. LinkedList的遍历 4. LinkedList的模拟实现 5. LinkedList的优缺点 (四) ArrayList和LinkedList的区别

    2024年01月21日
    浏览(44)
  • 【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)

    🍃 数据结构是 计算机 存储 、 组织 数据的方式 🎉 线性 结构 线性表(数组、链表、栈、队列、哈希表) 🎉 树形 结构 二叉树 AVL 树 红黑树 B 树 堆 Trie 哈夫曼树 并查集 🎉 图形 结构 邻接矩阵 邻接表 🎁 线性表是具有 n 个 相同类型元素 的有限 序列 (n = 0) a1 是首节点

    2024年02月10日
    浏览(75)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包