ArrayList与顺序表

阳光穿透心脏的1/2处 2023-10-09 16:31 12阅读 0赞

## ![f1e183c05b5d484eb3a727481ac40b15.jpeg][] ##

**目录**

编辑

一、线性表

二、顺序表

1、接口的实现

（1）打印顺序表

（2）新增元素

（3）判定是否包含某个元素

（4）查找某个元素对应的位置下标

（5）获取 pos 位置的元素

（6）获取顺序表长度

（7）给 pos 位置的元素设为 value【更新的意思 】

（8）在 pos 位置新增元素

（9）删除第一次出现的关键字key

（10）清空顺序表

三、ArrayList简介

四、ArrayList使用

1、ArrayList的构造

2、ArrayList常见操作

3、ArrayList的遍历

4、ArrayList的扩容机制

五、ArrayList的具体使用

六、ArrayList的问题及思考

--------------------

## **一、线性表** ##

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

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

--------------------

## **二、顺序表** ##

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

### **1、接口的实现** ###

#### **（1）打印顺序表** ####

注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的

public void display() {
            for (int i = 0; i < this.usedSize; i++) {
                System.out.print(this.elem[i] +" ");
            }
            System.out.println();
        }

#### **（2）新增元素** ####

默认在数据 最后新增

public void add(int data) {
            //首先得判断满的情况
            if(isFull()) {
                resize();
            }
            this.elem[usedSize] = data;
            usedSize++;
        }
        public boolean isFull() {
            return usedSize == elem.length;
        }

#### **（3）判定是否包含某个元素** ####

public boolean contains(int toFind) {
            for (int i = 0; i < this.usedSize; i++) {
                if(elem[i] == toFind) {
                    return true;
                }
            }
            return false;
        }

#### **（4）查找某个元素对应的位置下标** ####

public int indexOf(int toFind) {
            for (int i = 0; i < this.usedSize; i++) {
                if(elem[i] == toFind) {
                    return i;
                }
            }
            return -1;
        }

#### **（5）获取 pos 位置的元素** ####

public int get(int pos) {
            if(!checkPos(pos)) {
                throw new PosOutBoundsException("get 获取数据时，位置不合法！");
            }
            return elem[pos];
        }

#### **（6）获取顺序表长度** ####

public int size() {
            return this.usedSize;
        }

#### **（7）给 pos 位置的元素设为 value【更新的意思 】** ####

public void set(int pos, int value) {
            if(!checkPos(pos)) {
                throw new PosOutBoundsException("set 数据时，位置不合法！");
            }
            this.elem[pos] = value;
        }
    
        private boolean checkPos(int pos) {
            if(pos < 0 || pos >= usedSize) {
                return false;
            }
            return true;
        }

#### **（8）在 pos 位置新增元素** ####

public void add(int pos, int data) {
            if(pos < 0 || pos > this.usedSize) {
                throw new PosOutBoundsException("add 元素的时候，pos位置不合法！");
            }
            if(isFull()) {
                resize();
            }
            //挪数据
            for (int i = this.usedSize-1; i >= pos ; i--) {
                this.elem[i+1] = this.elem[i];
            }
            //存数据
            this.elem[pos] = data;
            this.usedSize++;
        }

#### **（9）删除第一次出现的关键字key** ####

public void remove(int toRemove) {
            if(isEmpty()) {
                return;
            }
            int index = indexOf(toRemove);
            if(index == -1) {
                return;//没有你要删除的数字
            }
            for (int i = index; i < usedSize-1; i++) {
                this.elem[i] = this.elem[i+1];
            }
            usedSize--;
            //elem[us] = null;
        }

#### **（10）清空顺序表** ####

public void clear() {
            /*for (int i = 0; i < usedSize; i++) {
                this.elem[i] = null;
            }*/
            usedSize = 0;
        }

--------------------

## **三、ArrayList简介** ##

在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：![1214e2b0e95741c9b35d9f14c4245098.png][]

【**说明**】

> 1. ArrayList 是以 **泛型** 方式实现的， **使用时必须要先实例化** 
> 
> 2. ArrayList 实现了 RandomAccess 接口，表明 ArrayList 支持随机访问
> 
> 3. ArrayList 实现了 Cloneable 接口，表明 ArrayList 是可以 clone 的 
> 
> 4. ArrayList 实现了 Serializable 接口，表明 ArrayList 是支持序列化的 
> 
> 5.  和 Vector 不同， **ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者 CopyOnWriteArrayList** 
> 
> 6. ArrayList 底层是一段连续的空间，并且可以动态扩容，是一个 **动态** 类型的顺序表

--------------------

##  **四、ArrayList使用** ##

### **1、****ArrayList****的构造**  ###

<table style="width:700px;"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="text-align:center;"> 
     <span style="color:#333333;"><strong>方法 </strong></span> 
    </div> </td> 
   <td> 
    <div style="text-align:center;"> 
     <span style="color:#333333;"><strong>解释</strong></span> 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div style="text-align:center;"> 
     <span style="color:#4183c4;">ArrayList</span> 
     <span style="color:#333333;">()</span> 
    </div> </td> 
   <td> 
    <div style="text-align:center;"> 
     <span style="color:#333333;">无参构造 </span> 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div style="text-align:center;"> 
     <span style="color:#4183c4;">ArrayList</span> 
     <span style="color:#333333;">(Collection&lt;? extends E&gt; c) </span> 
    </div> </td> 
   <td> 
    <div style="text-align:center;"> 
     <span style="color:#333333;">利用其他</span> 
     <span style="color:#333333;"> Collection </span> 
     <span style="color:#333333;">构建</span> 
     <span style="color:#333333;"> ArrayList </span> 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div style="text-align:center;"> 
     <span style="color:#4183c4;">ArrayList</span> 
     <span style="color:#333333;">(int initialCapacity) </span> 
    </div> </td> 
   <td> 
    <div style="text-align:center;"> 
     <span style="color:#333333;">指定顺序表初始容量 </span> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

现在，让我们来尝试创建一个顺序表:

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 虽然提供的方法比较多，但是常用方法如下所示，需要用到其他方法时，可以自行查看 ArrayList 的帮助文档。

![4cca703def87407e921d7fadbe53c0be.png][]

现在，我们来试着使用一下这些方法来完成一段代码的编写：

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 循环 \+ 下标、 for each 、使用迭代器

**使用for循环遍历：**

for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
            }
            System.out.println();

**使用for each遍历：**

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. ArrayList 最常使用的遍历方式是： for 循环 \+ 下标 以及  fo reach 
> 
> 2.  迭代器是设计模式的一种。

--------------------

### **4、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;
            }

那么现在，我们对ArrayList源码中扩容的部分进行一个总结:

**【总结】**

> 1.  检测是否真正需要扩容，如果是调用 grow 准备扩容 
> 
> 2.  预估需要扩容的大小 
> 
>  初步预估按照1.5 倍大小扩容 
> 
>  如果用户所需大小超过预估1.5 倍大小，则按照用户所需大小扩容 
> 
>  真正扩容之前检测是否能扩容成功，防止太大导致扩容失败 
> 
> 3.  使用 copyOf 进行扩容

--------------------

## **五、ArrayList的具体使用** ##

在学习完ArrayList之后，我们可以使用ArrayList来完成对一些特定情况的使用，现在，我们来尝试使用ArrayList来编写一个简单的洗牌算法

大致思路如下：

我们可以先创建一个Card类，其中属性为牌的花色和牌面的数值，然后再将一整副牌都存进一个借用ArrayList创建的顺序表中，其次借用Random将扑克牌进行打乱处理，此时为了能够将牌顺利的发给三个人，我们可以在为每个人单独创建一个顺序表，并且再用一个顺序表来存储它们三个人分别的顺序表

代码的具体实现如下：

public class Card {
        public int rank; // 牌面值
        public String suit; // 花色
        @Override
        public String toString() {
            return String.format("[%s %d]", suit, rank);
        }
    }
    import java.util.List;
            import java.util.ArrayList;
            import java.util.Random;
    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(20190905);
            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 < 5; 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的问题及思考** ##

1. ArrayList 底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N)

2.  增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3.  增容一般是呈 2 倍的增长，势必会有一定的空间浪费。例如当前容量为 100 ，满了以后增容到 200 ，我们再继续插入了5 个数据，后面没有数据插入了，那么就浪费了 95 个数据空间。

那么如何来解决这些问题呢？这就将与我们后面即将学到的链表有关了！

欢迎阅读下一期的链表博客

[f1e183c05b5d484eb3a727481ac40b15.jpeg]: https://img-blog.csdnimg.cn/f1e183c05b5d484eb3a727481ac40b15.jpeg
[0e74676f4edb40f8a6877659273964d6.png]: https://img-blog.csdnimg.cn/0e74676f4edb40f8a6877659273964d6.png
[1214e2b0e95741c9b35d9f14c4245098.png]: https://img-blog.csdnimg.cn/1214e2b0e95741c9b35d9f14c4245098.png
[4cca703def87407e921d7fadbe53c0be.png]: https://img-blog.csdnimg.cn/4cca703def87407e921d7fadbe53c0be.png