数据结构：ArrayList简单实现与常见操作实例详解

目录

1.顺序表概念

2.自己实现

1.准备工作

接口

MyArrayList的定义

2.具体接口实现 

添加

判满

扩容

查找

获得pos位置的值 和 更改pos位置的值

判空

删除

得到数组长度

清空数组

打印

3.ArrayList

1.简介

2.使用

1.ArrayList的构造

无参构造 

有参构造：参数为initialCapacity

有参构造：参数为参数为Collection c

2.常见操作

3.遍历

4.ArrayList具体使用实例

杨辉三角

解题思路

代码 

简单洗牌算法

规则

 5.顺序表复杂度分析

---

1.顺序表概念

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

2.自己实现

为了方便学习jdk原生类ArrayList，我们通过自己实现部分接口，帮助我们理解和更好的使用它。

1.准备工作

先创建一个类MyArrayList和一个接口ILIst。接口中的抽象方法实际就是为了解决数据结构增删查改的功能。

接口

public interface IList {//尾部添加public void add(int data);//在pos位置添加public void add(int data,int pos );//判满boolean isFull();//判断是否包含某元素public boolean contains(int toFind);//返回找到元素下标，找不到返回-1public int indexOf(int toFind);//得到pos位置的值public int get(int pos);//替换pos位置的值为valuepublic void set(int pos,int value);//删除remove第一次出现的值public void remove(int toRemove);//返回顺序表长度public int size();//清空顺序表public void claer();//打印public void display();
}

通过实现接口中的方法，完成MyArrayList的编写。

MyArrayList的定义

 顺序表的是指就是数组。所以MyArrayList的成员变量就是数组array，数组的大小和实际使用的空间。

    private int[] array;//顺序表本质是控制数组private int useSize;//实际使用的空间private final int DEFINE_CAPACITY = 10;//默认容量public MyArrayList() {this.array = new int[DEFINE_CAPACITY];}

2.具体接口实现 

添加

对于数组的添加元素的操作其实是很简单的，不过我们需要在添加元素之前判断数组元素是否已满。

判满

public boolean isFull() {return this.useSize == this.array.length;}

判满有两个结果，一个是已满需要扩容，另一个是未满。 

扩容

private void grow(){this.array = Arrays.copyOf(this.array,this.array.length * 2);}
//2倍扩容

经过判满和扩容，数组已经有空间来添加新的元素。

    //尾插@Overridepublic void add(int data) {if(isFull()){grow();}this.array[this.useSize++] = data;}//在pos位置添加data，需要挪动数据@Overridepublic void add(int data, int pos) {try {Checkpos2(pos);if(isFull()){grow();}for (int i = this.useSize - 1; i >= pos; i--) {this.array[i+1] = this.array[i];}this.array[pos] = data;this.useSize++;}catch(PositionOutOfBoundsException e){e.printStackTrace();}}

 添加的业务逻辑就不再赘述了，在pos位置添加data的时候，需要注意检查pos的合法性。对于数组的下标，编译器的检查是十分严格的，我们不希望也不允许数组发生越界的情况。所以写了一个异常类PositionOutOfBoundsException来帮我们捕捉错误。

 private void Checkpos2(int pos){if(pos < 0 || pos > this.useSize){throw new PositionOutOfBoundsException("pos位置不合法");}}public class PositionOutOfBoundsException extends RuntimeException{public PositionOutOfBoundsException() {super();}public PositionOutOfBoundsException(String message) {super(message);}
}

查找

遍历数组即可。

    //找到返回true，找不到返回false@Overridepublic boolean contains(int toFind) {for (int i = 0; i < this.useSize; i++) {if(toFind == this.array[i]){return true;}}return false;}//找到返回下标，找不到返回-1@Overridepublic int indexOf(int toFind) {for (int i = 0; i < this.useSize; i++) {if(toFind == this.array[i]){return i;}}return -1;}

获得pos位置的值 和 更改pos位置的值

//获得
@Overridepublic int get(int pos) {try {isEmpty();Checkpos1(pos);return this.array[pos];}catch (PositionOutOfBoundsException e){e.printStackTrace();}catch (ListEmptyException e){e.printStackTrace();}return -1;}//更改@Overridepublic void set(int pos, int value) {if(pos == 0){this.array[pos] = value;}try {isEmpty();Checkpos1(pos);this.array[pos] = value;}catch (PositionOutOfBoundsException e){e.printStackTrace();}catch (ListEmptyException e){e.printStackTrace();}}private void Checkpos1(int pos){if(pos < 0 || pos >= this.useSize){throw new PositionOutOfBoundsException("pos位置不合法");}}//与Checkpos2不同的是此场景pos等于useSize也是不允许的

 通过上面添加的介绍，我们可以明白这两个方法也需要检查pos的合法性(和上面pos的检查稍有不同，具体场景集体分析)。同时对于这两个方法，如果数组为空，那么获得pos位置的值就变的毫无意义。所以我们需要判断数组是否为空。同时写一个异常类ListEmptyException来协助检查。

判空

private void isEmpty(){if(this.useSize == 0){throw new ListEmptyException("当前顺序表为空！");}}public class ListEmptyException extends  RuntimeException{public ListEmptyException() {super();}public ListEmptyException(String message) {super(message);}
}

删除

@Overridepublic void remove(int toRemove) {try {isEmpty();int pos = indexOf(toRemove);for (int i = pos; i < this.useSize - 1; i++) {this.array[i] = this.array[i + 1];}this.useSize--;}catch (ListEmptyException e){e.printStackTrace();}}

删除也需要判空，删除的业务逻辑是找到删除的位置，再挪动数据覆盖。 

得到数组长度

@Overridepublic int size() {return this.useSize;}

清空数组

    @Overridepublic void claer() {//如果是引用类型，需要把每个位置都置null
//        for (int i = 0; i < this.useSize; i++) {
//            array[i] = null;
//        }this.useSize = 0;}

打印

    @Overridepublic void display() {for (int i = 0; i < this.useSize; i++) {System.out.print(this.array[i] + " ");}System.out.println();}
}

3.ArrayList

1.简介

ArrayList​​ 是 Java 中基于动态数组实现的列表类，属于 java.util 包的核心集合类。

1. ArrayList是以泛型方式实现的，使用时必须要先实例化

2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问     

3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的

4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的

5.ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

2.使用

1.ArrayList的构造

我们在对ArrayList对象实例化的时候可以观察到IDEA对其的代码补全，会有三种不同的构造，如下图：

我们来看看ArrayList的源码，更深一层次的理解ArrayList的构造。看源码！（只看有关的部分，画图比较容易讲解，所以通过画图来看）

这里面有两个空数组对于刚学习的人来说是比较陌生的。暂且已知的只是它们是空的数组，并不知道它们的用处。了解了下面就明白了。

无参构造 

通过add一步一步找到扩容的源码。我们就只看帮助理解空数组2的部分。

 

所以得出结论：在无参构造被触发的时候并没有立即分配容量为10的空间，只是把一个空数组给到类元素数组，分配空间是在add里发生的。

有参构造：参数为initialCapacity

 

有参构造：参数为参数为Collection<? extends E> c

首先需要理解参数Collection<? extends E> c是什么意思？

Collection代表参数 c 必须是一个集合（Collection 类型），<？ extends E>代表集合元素类型是E或是E的子类。

那么就意味着ArrayList可以传入像List<Interger>这样的集合：

ArrayList<Integer> arrayList = new ArrayList<>(3);arrayList.add(1);arrayList.add(1);arrayList.add(1);//有参：参数为Collection<? extends E> cArrayList<Integer> List3 = new ArrayList<>(arrayList);List3.add(4);System.out.println(List3);//运行结果
//[1, 1, 1, 4]

源码：

 

2.常见操作

ArrayList提供的方法很多，我演示常见的一些。

public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();//boolean add(E e) 尾插elist.add(1);list.add(2);list.add(3);list.add(4);list.add(5);// void add(int index, E element) 在index 插 elist.add(1,999);System.out.println("list"+list);// boolean addAll(Collection<? extends E> c) 尾插c中的元素ArrayList<Integer> list2 = new ArrayList<>();list2.add(1);list2.addAll(list);System.out.println("list2:"+list2);}//运行结果
//list[1, 999, 2, 3, 4, 5]
//list2:[1, 1, 999, 2, 3, 4, 5]

 

 

    public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(2);System.out.println(list);
//        E remove(int index)  删除index的值list.remove(3);System.out.println(list);
//        boolean remove(Object o)  删除遇到的第一个olist.remove(Integer.valueOf(2));//注意：参数是Object oSystem.out.println(list);
//        E get(int index)     获得index的值System.out.println(list.get(2));
//        E set(int index, E element)   更改index的值为elementlist.set(3,1000);System.out.println(list);}//运行结果
//[1, 2, 3, 4, 5, 2]
//[1, 2, 3, 5, 2]
//[1, 3, 5, 2]
//5
//[1, 3, 5, 1000]

 

 public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(2);System.out.println(list);//boolean contains(Object o)  判断o是否在表中System.out.println(list.contains(new Integer(4)));System.out.println(list.contains(new Integer(100)));// int indexOf(Object o)   返回第一个o的下标System.out.println(list.indexOf(new Integer(2)));// int lastIndexOf(Object o)  返回最后一个o的下标System.out.println(list.lastIndexOf(new Integer(2)));// List<E> subList(int fromIndex, int toIndex)   截取部分List，左闭右开List<Integer> list2 = list.subList(3,5);System.out.println(list2);list2.set(0,999);System.out.println("list" + list);System.out.println("list2" + list2);//可以发现对list2的元素更改对list也产生了影响，说明subList方法并没有产生新的对象}//运行结果
//[1, 2, 3, 4, 5, 2]
//true
//false
//1
//5
//[4, 5]
//list[1, 2, 3, 999, 5, 2]
//list2[999, 5]

3.遍历

直接上代码

public static void main(String[] args) {//ArrayList的遍历ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(6);list.add(7);System.out.println(list);//forifor (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();//foreachfor (Integer element:list) {System.out.print(element + " ");}System.out.println();//迭代器iteratorIterator<Integer> it = list.iterator();while(it.hasNext()){System.out.print(it.next() + " ");}System.out.println();//迭代器listIterator（是iterator的子接口，可以实现双向遍历）ListIterator<Integer> it2 = list.listIterator(list.size());while(it2.hasPrevious()){System.out.print(it2.previous() + " ");}System.out.println();}//运行结果
//[1, 2, 3, 4, 6, 7]
//1 2 3 4 6 7 
//1 2 3 4 6 7 
//1 2 3 4 6 7 
//7 6 4 3 2 1 

4.ArrayList具体使用实例

杨辉三角

题目链接

题目分析

解题思路

代码 

public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();//第0行List<Integer> list0 = new ArrayList<>();list0.add(1);ret.add(list0);//后面的行for (int i = 1; i < numRows; i++) {//第一个元素List<Integer> curRow = new ArrayList<>();curRow.add(1);//中间元素List<Integer> perRow = ret.get(i-1);//获得上一行数组for (int j = 1; j < i; j++) {int val1 = perRow.get(j);int val2 = perRow.get(j-1);curRow.add(val1 + val2);}//最后一个元素curRow.add(1);ret.add(curRow);}return ret;}

 

简单洗牌算法

规则

一副扑克牌(除了大小王)，三个人，每个人轮流抓 5 张牌。可以显示三个人的手牌和牌堆剩余的牌。 

业务逻辑包括：获取扑克、打乱扑克和发牌。看代码实现：

package card.dealing;public class Card {private String suit;//花色private int rank;//牌的大小public Card(String suit, int rank) {this.suit = suit;this.rank = rank;}@Overridepublic String toString() {return "{" + suit + rank + "} ";}
}

package card.dealing;import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class CardDemo {public static final String[] suits = {"♥","♣","♦","♠"};//产生一副牌public List<Card> BuyCard(){List<Card> cards = new ArrayList<>();for (int i = 0; i < 13; i++) {for (int j = 0; j < 4; j++) {String suit = suits[j];//获取花色int rank = j + 1;//牌的数字Card card = new Card(suit,rank);cards.add(card);}}return cards;}//打乱一副牌public List<Card> MixCard(List<Card> cards){Random random = new Random();for (int i = cards.size()-1; i > 0; i--) {int index = random.nextInt(i);swap(cards, index, i);}return cards;}private void swap(List<Card> cards,int j,int i){Card tmp = cards.get(j);cards.set(j,cards.get(i));cards.set(i,tmp);}//发牌：三个人，依次发五张public List<List<Card>>  play(List<Card> cards){//三个人List<Card> hand0 = new ArrayList<>();List<Card> hand1 = new ArrayList<>();List<Card> hand2 = new ArrayList<>();List<List<Card>> ret = new ArrayList<>();ret.add(hand0);ret.add(hand1);ret.add(hand2);for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {Card card = cards.remove(0);//从牌堆顶拿牌ret.get(j).add(card);}}return ret;}
}

package card.dealing;import java.util.List;public class test {public static void main(String[] args) {CardDemo cardDemo = new CardDemo();//获取牌List<Card> cradList =  cardDemo.BuyCard();System.out.println(cradList);cardDemo.MixCard(cradList);System.out.println(cradList);//发牌List<List<Card>> ret = cardDemo.play(cradList);for (int i = 0; i < ret.size(); i++) {System.out.println("这是第"+(i+1)+ "的牌" +ret.get(i));}System.out.println("剩下的牌"+ cradList);}
}

 5.顺序表复杂度分析

通过索引访问元素的时间复杂度为 ​​O(1)​​。

中间插入或删除元素需要移动后续元素，时间复杂度为 ​​O(n)​​。