本文介绍: 一个高端的程序员,往往都是数据结构学的很好,判断一个程序的优劣也是看数据结构学的好与坏.顺序表,数据结构中最简单部分之一,让我们一起学习吧~~~

目录

前言

顺序表

​编辑

顺序表和数组

ArrayList简介

说明

ArrayList使用​编辑

ArrayList常见操作

 ArrayList实现二维数组

ArrayList的遍历

 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使用

public static void main(String[] args) {
    // ArrayList创建推荐写法
    // 构造一个空的列表
    List<Integer&gt; list1 = new ArrayList<&gt;();
    // 构造一个具有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);
}

ArrayList常见操作

 ArrayList实现二维数组

ArrayList<ArrayList<Integer>> test = new ArrayList<>();

ArrayList的遍历

ArrayList 可以使用三方方式遍历:for循环+下标foreach、使用迭代

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();
    //list的迭代器
    Iterator<Integer> it = list.listIterator();
    while(it.hasNext()){
        System.out.print(it.next() + " ");
    } 
    System.out.println();
}

 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)预估按照1.5倍大小扩容

                (2)如果用户所需大小超过预估1.5倍大小,则按照用户所需大小扩容

                (3)真正扩容之前检测是否能扩容成功,防止太大导致扩容失败

3. 使用copyOf进行扩容

原文地址:https://blog.csdn.net/qq_48858380/article/details/134781789

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_47994.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注