【Java数据布局】---List（ArrayList）

乐观学习，乐观生存，才气不停进步啊！！！

我的主页：optimistic_chen
    我的专栏：c语言 ，Java
    接待各人访问~
创作不易，大佬们点赞鼓励下吧~

  

前言

在聚集框架中，List是一个接口，继续自Collection

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

这些是Collection下的方法：

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

由聚集框架，直接告知了我们精确的学习次序，团体由下到上学习。本日先开始我们熟悉的次序表(ArrayList)的具体内容。
线性表

之前C语言部分也学习过次序表，我们这里就简朴分析。
   线性表（linear list）是n个具有雷同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据布局，常见的线性表：次序表、链表、栈、队列…（之后都会学习到）
  线性表在逻辑上是线性布局，也就说是连续的一条直线。但是在物理布局上并不肯定是连续的，线性表在物理上存储时，通常以数组和链式布局的情势存储。
次序表（MyArrayList）

   次序表是**用一段物理地点连续的存储单元依次存储数据元素的线性布局**，一样寻常环境下采取数组存储。在数组上完成数据的增删查改
  由于ArrayList是聚集框架下的一个平凡的类，他的增删查改可以由编译器实现。我们要做的就是自主实现这些功能，增强对代码的明白。我们可以把这些功能先界说在一个接口IList中，再通过我们自己的MyArrayList类完成具体代码。

1. //接口
2. public interface IList {
3.     public void add(int data);
5.     public void add(int pos,int data);
7.     public boolean contains(int toFind);
9.     public int indexOf(int toFind);
11.     public int get(int pos);
13.     public void set (int pos,int value);
15.     public void remove(int toRemove);
17.     public int size();
19.     public void clear();
21.     public void display();
23. }

复制代码

具体功能代码

增长元素

1. @Override
2.     public void add(int data) {
3.     //判断数组空间大小
4.         if(isFull()){
5.         //扩容
6.             grow();
7.         }
8.         //增加元素
9.         this.array[this.usedSize]=data;
10.         //数组长度+1
11.         this.usedSize++;
12.     }
13.     private void grow(){
14.         this.array= Arrays.copyOf(this.array,2*this.array.length);
15.     }
16.     public boolean isFull(){
17.         return this.usedSize==array.length;
18.     }

复制代码

指定位置插入元素

1. @Override
2.     public void add(int pos, int data) {
3.     //预防异常
4.         try{
5.             checkPos(pos);
6.             if(isFull()){
7.                 grow();
8.             }
9.             //挪动元素
10.             for (int i = usedSize-1; i <=pos ; i--) {
11.                 array[i+1]=array[i];
12.             }
13.             array[pos]=data;
15.             usedSize++;
16.         }//捕获异常
17.         catch(PosIllegal e){
18.             System.out.println("插入元素位置不合法");
19.             e.printStackTrace();
20.         }
21.     }
22.     //检查异常
23.     private void checkPos(int pos){
24.         if(pos < 0 || pos > usedSize){
25.             throw new PosIllegal("Pos位置不合法");
26.         }
27.     }

复制代码

判定是否存在该元素

1. @Override
2.     public boolean contains(int toFind) {
3.         for (int i = 0; i < usedSize; i++) {
4.             if(array[i]==toFind){
5.                 return true;
6.             }
7.         }
8.         return false;
9.     }

复制代码

返回查找的该元素

1. @Override
2.     public int indexOf(int toFind) {
3.         for (int i = 0; i < usedSize; i++) {
4.             if(array[i]==toFind){
5.                 return i;
6.             }
7.         }
8.         return 0;
9.     }

复制代码

获取 pos 位置的元素

1. @Override
2.     public int get(int pos) {
4.         try{
5.             checkEmpty();
6.             checkPos2(pos);
7.             return array[pos];
8.         }catch(PosIllegal e) {
9.             e.printStackTrace();
10.         }catch(EmptyException e){
11.             e.printStackTrace();
12.         }
13.         return -1;
14.     }
15.     private void checkEmpty(){
16.         if(isEmpty()){
17.             throw new EmptyException("顺序表为空");
18.         }
19.     }
20.     public boolean isEmpty(){
21.         return usedSize==0;
22.     }
23.     private void checkPos2(int pos){
24.         if(pos < 0 || pos > usedSize){
25.             throw new PosIllegal("Pos位置不合法");
26.         }
27.     }

复制代码

将pos位置元素改为value

1. @Override
2.     public void set(int pos, int value) {
3.         try{
4.             checkEmpty();//检查顺序表是否为空
5.             checkPos2(pos);//检查pos位置是否为空
6.             array[pos]=value;
7.         }catch (PosIllegal e){
8.             e.printStackTrace();
9.         }catch (EmptyException e){
10.             e.printStackTrace();
11.         }
12.     }

复制代码

删除第一次出现的关键词

1. @Override
2.     public void remove(int toRemove) {
3.             try{
4.                 checkEmpty();
5.                 int pos = indexOf(toRemove);
6.                 if(pos==-1){
7.                     return;
8.                 }``
9.                 for (int i = 0; i < usedSize; i++) {
10.                     array[i]=array[i+1];
11.                 }
12.                 usedSize--;
13.             }catch (EmptyException e) {
14.                 e.printStackTrace();
15.             }
16.     }

复制代码

获取次序表长度

1. @Override
2.     public int size() {
3.         return this.usedSize;
4.     }

复制代码

清空次序表

1. @Override
2.     public void clear() {
3.         //引用类型释放空间
4.         /*for (int i = 0; i < usedSize; i++) {
5.             array[i] = null;
6.         }*/
7.         //基本类型直接清空
8.         usedSize=0;
9.     }

复制代码

ArrayList简介

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

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

由ArrayList的源码可以看到：
   

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

  ArrayList的使用

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

1. public static void main(String[] args) {
2.         ArrayList<Integer> list=new ArrayList<>();
3.         list.add(1);
4.         list.add(2);
5.         list.add(3);
6.         list.add(4);
7.         list.add(5);
8.         System.out.println(list);
10.         //截取数组
11.         List<Integer> list1=list.subList(0,3);
12.         System.out.println(list1);
13.         System.out.println("===========");
15.         list.set(0,99);
16.         System.out.println(list);
17.         System.out.println(list1);
18.     }

复制代码

1. // 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找
2.         list.add(2);
3.         list.add(6);
4.         list.add(4);
5.         list.add(5);
6.         list.add(9);
7.         list.add(78);
8.         list.add(66);
10.         System.out.println(list.indexOf(5));
11.         System.out.println(list.lastIndexOf(6));

复制代码

ArrayList的遍历

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

1. public static void main(String[] args) {
2.   List<Integer> list = new ArrayList<>();
3.   list.add(1);
4.   list.add(2);
5.   list.add(3);
6.   list.add(4);
7.   list.add(5);
8.   // 使用下标+for遍历
9.   for (int i = 0; i < list.size(); i++) {
10.     System.out.print(list.get(i) + " ");
11. }
12.   System.out.println();
13.   
14.   // 借助foreach遍历
15.   for (Integer x : list) {
16.     System.out.print(x + " ");
17. }
18.   System.out.println();
19.   
20.   //使用迭代器
21.   Iterator<Integer> it = list.listIterator();
22.   while(it.hasNext()){
23.     System.out.print(it.next() + " ");
24. }
25.   System.out.println();
26. }

复制代码

ArrayList扩容

• 检测是否真正必要扩容，假如是调用grow预备扩容
  
• 预估必要库容的巨细
  开端预估按照1.5倍巨细扩容
  假如用户所需巨细凌驾预估1.5倍巨细，则按照用户所需巨细扩容
  真正扩容之前检测是否能扩容乐成，防止太大导致扩容失败
  
• 使用copyOf举行扩容
  

1. private void grow(){
2.         this.array= Arrays.copyOf(this.array,2*this.array.length);
3.     }

复制代码

训练（洗牌算法）

   Test1

1. import java.util.ArrayList;
2. import java.util.List;
4. public class Test1 {
5.     public static void main(String[] args) {
6.         CardDemo cardDemo=new CardDemo();
8.         List<Card> cardList = CardDemo.buyCard();
9.         System.out.println(cardList);
11.         cardDemo.shuffle(cardList);
12.         System.out.println(cardList);
14.         List<List<Card>> ret = CardDemo.play(cardList);
15.         for (int i = 0; i < ret.size(); i++) {
16.             System.out.println("第"+(i+1)+"个人的牌： "+ret.get(i));
17.         }
18.     }
19. }

复制代码

  Card

1. public class Card {
2.     private String suit;
3.     private int rank;
5.     public Card(String suit,int rank){
6.         this.suit=suit;
7.         this.rank=rank;
8.     }
10.     @Override
11.     public String toString() {
12.         /*return "Card{" +
13.                 "suit='" + suit + '\'' +
14.                 ", rank=" + rank +
15.                 '}';*/
16.         return "{"+suit + rank+"} ";
17.     }
18. }

复制代码

  CardDemo

1. import java.util.ArrayList;
2. import java.util.List;
3. import java.util.Random;
4. import java.util.concurrent.Callable;
6. public class CardDemo {
7.     public static  final  String[] suits={"♥","♠","♣","♦"};
9.     //得到52张牌
10.     public static List<Card> buyCard(){
11.         List<Card> cardList=new ArrayList<>();
12.         for (int i = 1; i <= 13; i++) {
13.             for (int j = 0; j < 4; j++) {
14.                 int rank = i;
15.                 String suit=suits[j];
16.                 Card card=new Card(suit,rank);
17.                 cardList.add(card);
18.             }
19.         }
20.         return cardList;
21.     }
22.     //洗牌
23.     public void shuffle(List<Card> cardList){
24.         Random random=new Random();
25.         for (int i = cardList.size()-1; i >0 ; i--) {
26.             int index = random.nextInt(i);
27.             swap(cardList,i,index);
28.         }
29.     }
30.     private void swap(List<Card> cardList,int i,int j ){
31.         Card tmp=cardList.get(i);
32.         cardList.set(i,cardList.get(j));
33.         cardList.set(j,tmp);
34.     }
35.     //三人拿牌
36.     public static List<List<Card>> play(List<Card> cardList){
37.         List<Card> hand0 = new ArrayList<>();
38.         List<Card> hand1 = new ArrayList<>();
39.         List<Card> hand2 = new ArrayList<>();
41.         List<List<Card>> hand=new ArrayList<>();
42.         hand.add(hand0);
43.         hand.add(hand1);
44.         hand.add(hand2);
46.         for (int i = 0; i < 5; i++) {
47.             for (int j = 0; j < 3; j++) {
48.                 Card card = cardList.remove(0);
49.                 hand.get(j).add(card);
50.             }
51.         }
52.         return hand;
53.     }
55. }

复制代码

完结

好了，到这里Java语法部分就已经竣事了~
假如这个系列博客对你有资助的话，可以点一个免费的赞并收藏起来哟~
可以点点关注，制止找不到我~ ，我的主页：optimistic_chen
我们下期不见不散~~Java
下期预告: 【Java数据布局】- - - List