备案控制台
开发者社区 安全 文章 正文

【顺序表ArrayList】

2024-01-19 23
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【顺序表ArrayList】

顺序表

含义：物理上连续，逻辑上也连续的线性结构。


应用于对数组的数据进行增删查改。


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


ArrayList常见操作

  1. boolean add(E e) 尾插 e
  2. void add(int index, E element) 将 e 插入到 index 位置
  3. boolean addAll(Collection<? extends E> c) 尾插 c 中的元素
  4. E remove(int index) 删除 index 位置元素
  5. boolean remove(Object o) 删除遇到的第一个 o
  6. E get(int index) 获取下标 index 位置元素
  7. E set(int index, E element) 将下标 index 位置元素设置为 element
  8. void clear() 清空
  9. boolean contains(Object o) 判断 o 是否在线性表中
  10. int indexOf(Object o) 返回第一个 o 所在下标
  11. int lastIndexOf(Object o) 返回最后一个 o 的下标
  12. List subList(int fromIndex, int toIndex) 截取部分 list


顺序表的优缺点

缺点：


1.插入数据必须要移动其他数据，最坏情况下，是插入到0位置，时间复杂度为O（N）。

2.删除数据也需要移动数据，就坏情况下，是删除0位置，时间复杂度为O（N）。


优点：


在给定下标查找时，时间复杂度为O（1）。


所以什么时候适合用顺序表？


就是给定下表查找时的场景。


ArrayList的扩容机制

ArrayList是一个动态类型的顺序表，在插入元素的过程中会自动扩容。


  1. 按照1.5倍扩容
  2. 第一次Add时，会分配大小为10的内存


1.练习 ：杨辉三角


代码如下

class Solution {
    public List<List<Integer>> generate(int numRows) {
        //二维数组
        List<List<Integer>> ret= new ArrayList<>();
        //第一行
        ArrayList<Integer> list = new ArrayList<>();
        //第一行的第一个元素
        list.add(1);
        //把第一行的元素放到二维数组里
        ret.add(list);
        //第二行的每个元素由前一行所得
        for (int i = 1; i <numRows ; i++) {
            //实例化当前行
            List<Integer> curRow = new ArrayList<Integer>();
            //当前行第一个元素是1
            curRow.add(1);
            //获取一维数组中上一行的元素。get方法是获取pos位置的元素
            List<Integer> prevRow = ret.get(i - 1);
            //当前行的中间元素
            for (int j = 1; j < i; j++) {
                int val = prevRow.get(j) + prevRow.get(j - 1);
                curRow.add(val);
            }
            //当前行的最后一个数据
            curRow.add(1);
            //把当前行数组放到二维数组里
            ret.add(curRow);
        }
        return ret;
    }
}


2.顺序表的实现

//定义一个接口
public interface IList {
        //新增元素，默认在数组最后新增
        public void add(int data) ;
        // 在 pos 位置新增元素
        public void add(int pos, int data) ;
        // 判定是否包含某个元素
        public boolean contains(int toFind);
        // 查找某个元素对应的位置
        public int indexOf(int toFind) ;
        // 获取 pos 位置的元素
        public int get(int pos) ;
        // 给 pos 位置的元素设为 value
        //(修改pos位置上的值)
        public void set(int pos, int value);
        //删除第一次出现的关键字key
        public void remove(int toRemove) ;
        // 获取顺序表长度
        public int size() ;
        // 清空顺序表
        public void clear() ;
        // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
        public void display() ;
        public boolean isEmpty();
}
//类实现接口
public class MyArrayList implements IList {
    //定义一个数组
    public int[] elem;
    private int usedSize;
    public static final int DEFAUL_SIZE = 5;
    public MyArrayList() {
        //初始化数组
        this.elem = new int[DEFAUL_SIZE];
    }
    public MyArrayList(int capacity){
        this.elem = new int[capacity];
    }
    //遍历顺序表方法
    public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+" ");
        }
        System.out.println();
    }
    //判断数组满了没有
    public boolean isFull(){
        if (usedSize == elem.length){
            return true;
        }
        return false;
    }
    @Override
    public void add(int data) {
        //判断满没满才能放
        cheakCapacity();
        this.elem[this.usedSize] = data;
        this.usedSize++;
    }
    //扩容方法
    //private封装，只为当前类使用
    private  void cheakCapacity(){
        if (isFull()){
            //满了扩容
            elem = Arrays.copyOf(elem,elem.length*2);
        }
    }
    /*
    检查pos的合法性
     */
    private void cheakPosOnGetAndSet(int pos) throws  PosIllegality {
        if (pos < 0 || pos >usedSize){
            System.out.println("pos位置不合法!");
            //抛异常，以便能找到哪一行错误
            throw new PosIllegality("插入元素下标异常：" + pos);
        }
    }
    //指定位置放元素
    @Override
    public void add(int pos, int data) {
        try{
            cheakPosOnGetAndSet(pos);
        }catch(PosIllegality e){
            e.printStackTrace();
            return ;
        }
        cheakCapacity();
        for (int i = usedSize-1; i >= pos ; i--) {
            elem[i+1] = elem[i];
        }
        elem[pos] = data;
        usedSize ++;
    }
    //是否包含某个元素
    @Override
    public boolean contains(int toFind) {
        if(isEmpty()) {
            return false;
        }
        for (int i = 0; i < usedSize; i++) {
            //如果是查找引用数据类型，一定记住要重写方法
            if (elem[i] == toFind){
                return true;
            }
        }
        return false;
    }
    @Override
    public int indexOf(int toFind) {
        if(isEmpty()) {
            return -1;
        }
        for (int i = 0; i < usedSize; i++) {
            //如果是查找引用数据类型，一定记住要重写方法
            if (elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }
    @Override
    public int get(int pos) throws MyArrayEmpty{
        cheakPosOnGetAndSet(pos);
       if (isEmpty()){
           throw new  MyArrayEmpty("获取顺序表下标位置时"+
                   "顺序表为空！");
       }
       return elem[pos];
    }
    @Override
    public void set(int pos, int value) {
        //先检查pos的合法性，
        cheakPosOnGetAndSet(pos);
        //修改pos上的值
        elem[pos] = value ;
    }
    @Override
    public void remove(int toRemove) {
        int index = indexOf(toRemove);
        if (index == -1){
            System.out.println("没有这个数字！");
            return;
        }
        for (int i = index; i < usedSize-1; i++) {
            elem[i] = elem[i+1];
        }
        usedSize--;
    }
    @Override
    public int size() {
        return this.usedSize;
    }
    @Override
    public void clear() {
        this.usedSize = 0;
        //如果是引用数据类型,可以用for循环一个一个置为null
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }
}
public class MyArrayEmpty extends RuntimeException {
    public MyArrayEmpty(String msg){
        super(msg);
    }
}
public class PosIllegality extends RuntimeException {
    //构造方法
    public  PosIllegality(String msg){
        super(msg);
    }
}
public class Test{
    public static void main1(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(1);//下标0
        myArrayList.add(2);//下标1
        myArrayList.add(199);//下标2
        myArrayList.display();
        //删除元素2
        myArrayList.remove(2);
        myArrayList.display();
}


3.简单的洗牌算法

package card;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
52张牌 1-k
  J   Q   K
 11  12  13
 */
public class CardDemo {
    //定义花色
    private  final String[] suits = {"♥","♠","♦","♣"};
    //买的牌
    public  List<Card> buyCard(){
        //产生52张牌
        List<Card> cardList = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 13; j++) {
                Card card = new Card(suits[i],j);
                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 a,int b) {
        //把a和b交换
        Card tmp = cardList.get(a);
        cardList.set(a, cardList.get(b));
        cardList.set(b, tmp);
    }
    public void  getCard(List<Card> cardList){
       List<Card> hand1 = new ArrayList<>();
       List<Card> hand2 = new ArrayList<>();
       List<Card> hand3 = new ArrayList<>();
       List<List<Card>> hands = new ArrayList<>();
       hands.add(hand1);
       hands.add(hand2);
       hands.add(hand3);
       //每个人轮流抓5张牌
       for (int i = 0; i <5 ; i++) {
           for (int j = 0; j < 3; j++) {
               Card card = cardList.remove(0);
               hands.get(j).add(card);
           }
        }
        System.out.println("第1个揭牌如下：");
        System.out.println(hand1);
        System.out.println("第2个揭牌如下：");
        System.out.println(hand2);
        System.out.println("第3个揭牌如下：");
        System.out.println(hand3);
        System.out.println("剩下的牌：");
        System.out.println(cardList);
    }
}
package card;
import java.sql.SQLOutput;
import java.util.List;
public class Test {
    public static void main(String[] args) {
        CardDemo cardDemo = new CardDemo();
        List<Card> cardList = cardDemo.buyCard();
        System.out.println("买的牌如下：");
        System.out.println(cardList);
        System.out.println("洗牌：");
        cardDemo.shuffle(cardList);
        System.out.println(cardList);
        System.out.println("揭牌：");
        cardDemo.getCard(cardList);
    }
}
文章标签：
安全
算法
小小啾啾
目录
相关文章
念君思宁
|
7月前
|
机器学习/深度学习 Java
泛型使用 && 包装类 && 顺序表与ArrayList &&顺序表和链表
泛型使用 && 包装类 && 顺序表与ArrayList &&顺序表和链表
念君思宁
28 0
Manggo
|
8月前
|
存储 设计模式 算法
【数据结构】ArrayList和顺序表
【数据结构】ArrayList和顺序表
Manggo
35 0
Leader_TBlog
|
9月前
LinkedList
LinkedList
Leader_TBlog
23 0
Kuo-Teng
|
11月前
|
Java
ArrayList与LinkedList的遍历删除元素方法
ArrayList与LinkedList的遍历删除元素方法
Kuo-Teng
197 0
是小辰
|
11月前
|
存储 安全 索引
顺序表 ArrayList
顺序表 ArrayList
是小辰
57 0
s:103
|
11月前
|
存储 Java C语言
【Java数据结构】ArrayList顺序表
我们平时很喜欢使用的数组，就是顺序表！ 下面我们将以 “模拟ArrayList” 的视角来盘一盘顺序表吧！
s:103
59 0
hsfxuebao
|
测试技术 索引
链表LinkedList介绍
链表LinkedList介绍
hsfxuebao
64 0
游离111
|
存储 Java
ArrayList与顺序表
ArrayList与顺序表
游离111
120 1
如风暖阳
|
存储 Java 容器
LinkedList与链表
这篇文章我们来了解LinkedList，该部分涵盖内容较多，分多篇文章来完成，在下边的内容中有跳转链接。
如风暖阳
68 0
LinkedList与链表
署前街的少年
|
存储 安全 Java
Java集合-- Array List 与顺序表
Array List 与顺序表详解
署前街的少年
149 0