乐观学习，乐观生活，才能不断前进啊！！！

我的主页：optimistic_chen

我的专栏：c语言 ，Java

欢迎大家访问~

创作不易，大佬们点赞鼓励下吧~

文章目录

前言线性表顺序表（MyArrayList）具体功能代码

ArrayList简介ArrayList的使用ArrayList的遍历ArrayList扩容

练习（洗牌算法）完结

前言

在集合框架中，List是一个接口，继承自Collection

这些方法都是List接口下的方法：

这些是Collection下的方法：

根据这些方法数量我们可以推断，List接口扩展了Collection接口。

由集合框架，直接告知了我们正确的学习顺序，整体由下到上学习。今天先开始我们熟悉的顺序表(ArrayList)的具体内容。

线性表

之前C语言部分也学习过顺序表，我们这里就简单说明。

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

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

顺序表（MyArrayList）

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

因为ArrayList是集合框架下的一个普通的类，他的增删查改可以由编译器实现。我们要做的就是自主实现这些功能，增强对代码的理解。我们可以把这些功能先定义在一个接口IList中，再通过我们自己的MyArrayList类完成具体代码。

<code>//接口

public interface IList { -- -->

public void add(int data);

public void add(int pos,int data);

public boolean contains(int toFind);

public int indexOf(int toFind);

public int get(int pos);

public void set (int pos,int value);

public void remove(int toRemove);

public int size();

public void clear();

public void display();

}

具体功能代码

增加元素

<code> @Override

public void add(int data) { -- -->

//判断数组空间大小

if(isFull()){

//扩容

grow();

}

//增加元素

this.array[this.usedSize]=data;

//数组长度+1

this.usedSize++;

}

private void grow(){

this.array= Arrays.copyOf(this.array,2*this.array.length);

}

public boolean isFull(){

return this.usedSize==array.length;

}

指定位置插入元素

@Override

public void add(int pos, int data) {

//预防异常

try{

checkPos(pos);

if(isFull()){

grow();

}

//挪动元素

for (int i = usedSize-1; i <=pos ; i--) {

array[i+1]=array[i];

}

array[pos]=data;

usedSize++;

}//捕获异常

catch(PosIllegal e){

System.out.println("插入元素位置不合法");

e.printStackTrace();

}

}

//检查异常

private void checkPos(int pos){

if(pos < 0 || pos > usedSize){

throw new PosIllegal("Pos位置不合法");

}

}

判断是否存在该元素

@Override

public boolean contains(int toFind) {

for (int i = 0; i < usedSize; i++) {

if(array[i]==toFind){

return true;

}

}

return false;

}

返回查找的该元素

@Override

public int indexOf(int toFind) {

for (int i = 0; i < usedSize; i++) {

if(array[i]==toFind){

return i;

}

}

return 0;

}

获取 pos 位置的元素

@Override

public int get(int pos) {

try{

checkEmpty();

checkPos2(pos);

return array[pos];

}catch(PosIllegal e) {

e.printStackTrace();

}catch(EmptyException e){

e.printStackTrace();

}

return -1;

}

private void checkEmpty(){

if(isEmpty()){

throw new EmptyException("顺序表为空");

}

}

public boolean isEmpty(){

return usedSize==0;

}

private void checkPos2(int pos){

if(pos < 0 || pos > usedSize){

throw new PosIllegal("Pos位置不合法");

}

}

将pos位置元素改为value

@Override

public void set(int pos, int value) {

try{

checkEmpty();//检查顺序表是否为空

checkPos2(pos);//检查pos位置是否为空

array[pos]=value;

}catch (PosIllegal e){

e.printStackTrace();

}catch (EmptyException e){

e.printStackTrace();

}

}

删除第一次出现的关键词

@Override

public void remove(int toRemove) {

try{

checkEmpty();

int pos = indexOf(toRemove);

if(pos==-1){

return;

}``

for (int i = 0; i < usedSize; i++) {

array[i]=array[i+1];

}

usedSize--;

}catch (EmptyException e) {

e.printStackTrace();

}

}

获取顺序表长度

@Override

public int size() {

return this.usedSize;

}

清空顺序表

@Override

public void clear() {

//引用类型释放空间

/*for (int i = 0; i < usedSize; i++) {

array[i] = null;

}*/

//基本类型直接清空

usedSize=0;

}

ArrayList简介

ctrl+鼠标左键进入ArrayList源码，

也可以看到编译器中add等功能的源码，具体再次不一一展示，感兴趣的大佬可以去编译器看看。

由ArrayList的源码可以看到：

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

ArrayList的使用

因为前面说了MyArrayList的各种功能，相当于自主实现了ArrayList。这里只写了没有说到的部分功能

<code>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);

System.out.println(list);

//截取数组

List<Integer> list1=list.subList(0,3);

System.out.println(list1);

System.out.println("===========");

list.set(0,99);

System.out.println(list);

System.out.println(list1);

}

<code> // 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找

list.add(2);

list.add(6);

list.add(4);

list.add(5);

list.add(9);

list.add(78);

list.add(66);

System.out.println(list.indexOf(5));

System.out.println(list.lastIndexOf(6));

ArrayList的遍历

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

<code>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 x : list) {

System.out.print(x + " ");

}

System.out.println();

//使用迭代器

Iterator<Integer> it = list.listIterator();

while(it.hasNext()){

System.out.print(it.next() + " ");

}

System.out.println();

}

ArrayList扩容

检测是否真正需要扩容，如果是调用grow准备扩容预估需要库容的大小

初步预估按照1.5倍大小扩容

如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容

真正扩容之前检测是否能扩容成功，防止太大导致扩容失败使用copyOf进行扩容

<code>private void grow(){ -- -->

this.array= Arrays.copyOf(this.array,2*this.array.length);

}

练习（洗牌算法）

Test1

import java.util.ArrayList;

import java.util.List;

public class Test1 {

public static void main(String[] args) {

CardDemo cardDemo=new CardDemo();

List<Card> cardList = CardDemo.buyCard();

System.out.println(cardList);

cardDemo.shuffle(cardList);

System.out.println(cardList);

List<List<Card>> ret = CardDemo.play(cardList);

for (int i = 0; i < ret.size(); i++) {

System.out.println("第"+(i+1)+"个人的牌： "+ret.get(i));

}

}

}

Card

public class Card {

private String suit;

private int rank;

public Card(String suit,int rank){

this.suit=suit;

this.rank=rank;

}

@Override

public String toString() {

/*return "Card{" +

"suit='" + suit + '\'' +code>

", rank=" + rank +

'}';*/

return "{"+suit + rank+"} ";code>

}

}

CardDemo