【Java数据结构】---List（ArrayList）

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

我的主页：optimistic_chen

我的专栏：c语言 ，Java

欢迎大家访问~
创作不易，大佬们点赞鼓励下吧~

前言

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

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

这些是Collection下的方法：

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

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

线性表

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

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

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

顺序表（MyArrayList）

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

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

//接口
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();}

具体功能代码

增加元素

 @Overridepublic void add(int data) {//判断数组空间大小if(isFull()){//扩容grow();}//增加元素this.array[this.usedSize]=data;//数组长度+1this.usedSize++;}private void grow(){this.array= Arrays.copyOf(this.array,2*this.array.length);}public boolean isFull(){return this.usedSize==array.length;}

指定位置插入元素

@Overridepublic 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位置不合法");}}

判断是否存在该元素

@Overridepublic boolean contains(int toFind) {for (int i = 0; i < usedSize; i++) {if(array[i]==toFind){return true;}}return false;}

返回查找的该元素

@Overridepublic int indexOf(int toFind) {for (int i = 0; i < usedSize; i++) {if(array[i]==toFind){return i;}}return 0;}

获取 pos 位置的元素

@Overridepublic 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

@Overridepublic void set(int pos, int value) {try{checkEmpty();//检查顺序表是否为空checkPos2(pos);//检查pos位置是否为空array[pos]=value;}catch (PosIllegal e){e.printStackTrace();}catch (EmptyException e){e.printStackTrace();}}

删除第一次出现的关键词

@Overridepublic 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();}}

获取顺序表长度

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

清空顺序表

 @Overridepublic void clear() {//引用类型释放空间/*for (int i = 0; i < usedSize; i++) {array[i] = null;}*///基本类型直接清空usedSize=0;}

ArrayList简介

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

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

由ArrayList的源码可以看到：

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

ArrayList的使用

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

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

 // 查找指定元素第一次出现的位置：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、使用迭代器

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扩容

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

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;}@Overridepublic String toString() {/*return "Card{" +"suit='" + suit + '\'' +", rank=" + rank +'}';*/return "{"+suit + rank+"} ";}
}

CardDemo

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.Callable;public class CardDemo {public static  final  String[] suits={"♥","♠","♣","♦"};//得到52张牌public static List<Card> buyCard(){List<Card> cardList=new ArrayList<>();for (int i = 1; i <= 13; i++) {for (int j = 0; j < 4; j++) {int rank = i;String suit=suits[j];Card card=new Card(suit,rank);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 i,int j ){Card tmp=cardList.get(i);cardList.set(i,cardList.get(j));cardList.set(j,tmp);}//三人拿牌public static List<List<Card>> play(List<Card> cardList){List<Card> hand0 = new ArrayList<>();List<Card> hand1 = new ArrayList<>();List<Card> hand2 = new ArrayList<>();List<List<Card>> hand=new ArrayList<>();hand.add(hand0);hand.add(hand1);hand.add(hand2);for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {Card card = cardList.remove(0);hand.get(j).add(card);}}return hand;}}

完结

好了，到这里Java语法部分就已经结束了~
如果这个系列博客对你有帮助的话，可以点一个免费的赞并收藏起来哟~
可以点点关注，避免找不到我~ ，我的主页：optimistic_chen
我们下期不见不散~~Java

下期预告: 【Java数据结构】- - - List