List与ArrayList

目录

一、List及其使用

        1.1 List的概念

        1.2 常见接口的介绍

        1.3 List的使用

二、线性表和顺序表

        2.1 线性表

        2.2 顺序表

三、ArrayList介绍

四、ArrayList的使用

        4.1 ArrayList构造

        4.2 ArrayList的常用方法

        4.3 ArrayList的遍历

        4.4 ArrayList的扩容机制

五、ArrayList的具体使用

        5.1 简单洗牌算法

        5.2 杨辉三角

六、ArrayList的问题

---

一、List及其使用

        1.1 List的概念

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

        Collection也是一个接口，该接口中规范了后序容器中常用的一些方法：
                

        Iterable也是一个接口，表示实现该接口的类是可以逐个元素进行遍历的：

                 

        从数据结构角度看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。

        1.2 常见接口的介绍

        List中有许多方法：

        

        虽然方法多，但常用方法如下：

方法	解释
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入 index 位置
boolean addAll(Collection<? extends E> c)	尾插 c 中的元素
E remove(int index)	删除 index 位置元素
boolean remove(Object o)	删除遇到的第一个 o
E get(int index)	获取下标 index 位置的元素
E set(int index, E element)	将 index 位置的元素设置为element
void clear()	清空
boolean contains(Object o)	判断 o 是否包含在线性表中
int indexOf(Object o)	返回第一个 o 的下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List<E> subList(int fromIndex, int toIndex)	截取部分list

        1.3 List的使用

                List是个接口，并不能直接用来实例化。如果要使用，必须去实例化List的实现类。在集合框架中，ArrayList和LinkedList都实现了List接口。

二、线性表和顺序表

        2.1 线性表

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

        2.2 顺序表

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

public interface IList {//新增元素,默认在数组最后新增public void add(int data);// 在 pos 位置新增元素public void add(int pos, int data);// 判定是否包含某个元素public boolean contains(int toFind) ;// 查找某个元素对应的位置public int indexOf(int toFind);// 获取 pos 位置的元素public int get(int pos);// 给 pos 位置的元素设为 value  更新public void set(int pos, int value);//删除第一次出现的关键字keypublic void remove(int toRemove) ;// 获取顺序表长度public int size();// 清空顺序表public void clear() ;// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display();boolean isFull();public boolean isEmpty();
}

public class MyArrayList implements IList{private  int[] elem;private  int usedSize;//顺序表默认大小private static  int DEFAULT_Size=10;public MyArrayList(){elem=new int[DEFAULT_Size];}public  MyArrayList(int capacity){elem=new int[capacity];DEFAULT_Size=capacity;}//添加一个数据@Overridepublic void add(int data) {chackCapacity();this.elem[usedSize]=data;this.usedSize++;}//检查容量private void chackCapacity(){if(isFull()){elem= Arrays.copyOf(elem,elem.length*2);}}//在pos插入一个数据@Overridepublic void add(int pos, int data) {try {chackPosOnAddOrGetOrSet(pos);}catch (PosError e){e.printStackTrace();return;}chackCapacity();for (int i = usedSize; i >pos ; i++) {elem[i]=elem[i-1];}elem[pos]=data;usedSize++;}/*检查pos的合法性*/private void chackPosOnAddOrGetOrSet(int pos) throws PosError{if(pos<0||pos>=this.usedSize)throw new PosError("下标异常"+pos);}//判断顺序表是否包含toFind@Overridepublic boolean contains(int toFind) {if(isEmpty())return false;for (int x:elem) {if(x==toFind)return true;}return false;}//获取toFing对应的下标@Overridepublic int indexOf(int toFind) {for (int i = 0; i < this.usedSize; i++) {if(elem[i]==toFind)return i;}return -1;}//获取pos下标对应的元素值@Overridepublic int get(int pos) {if(isEmpty())return -1;chackPosOnAddOrGetOrSet(pos);return this.elem[pos];}//设置下标为pos的元素值为value@Overridepublic void set(int pos, int value) {chackPosOnAddOrGetOrSet(pos);elem[pos]=value;}//删除toRemove@Overridepublic void remove(int toRemove) {int index=indexOf(toRemove);if(index<0){System.out.println("要删除的数不存在");return;}for(int i=index;i<this.usedSize-1;i++){this.elem[i]=this.elem[i+1];}this.usedSize--;}//获取当前顺序表的大小@Overridepublic int size() {return this.usedSize;}//清空@Overridepublic void clear() {for (int i = 0; i < usedSize; i++) {set(i,0);}}/*遍历顺序表当中的元素*/@Overridepublic void display() {if(isEmpty()){throw new MyArrayIsEmpty("顺序表是空的");}for(int i=0;i<elem.length;i++){System.out.println(this.elem[i]+" ");}System.out.println();}/*判断顺序表是否已满*/@Overridepublic boolean isFull() {/*if(usedSize==DEFAULT_Size)return true;elsereturn false;*/return  usedSize==DEFAULT_Size;}@Overridepublic boolean isEmpty() {return elem.length==0;}
}

public class MyArrayIsEmpty extends RuntimeException{public MyArrayIsEmpty(String massage){super(massage);}
}

public class PosError extends RuntimeException{public PosError(String massage){super(massage);}
}

三、ArrayList介绍

        在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架如下：
        

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

四、ArrayList的使用

        4.1 ArrayList构造

方法	解释
ArrayList()	无参构造
ArrayList(Collection<? extends E> c)	利用其他 Collection 构建 ArrayList
ArrayList(int initialCapacity)	指定顺序表初始容量

public static void main(String[] args) {//创建一个空列表 ArrayList()  默认size为0ArrayList<Integer> list1=new ArrayList<>();//创建一个容量为10的列表  ArrayList(int initialCapacity)创建指定容量的列表//ArrayList<Integer> 指定存放的元素类型为IntegerArrayList<Integer> list2=new ArrayList<>(10);list1.add(1);//第一次add时，底层数组size为10list1.add(2);list1.add(3);//ArrayList(Collection<? extends E> c)//参数c必须实现了Collection接口，是E的子类或E本身类型//list3的元素与list2相同ArrayList<Integer> list3=new ArrayList<>(list2);
}

        使用不带参数newArrayList对象时，默认size为0，当第一次add时，底层数组size为10，当数组需要扩容时，是以当前数组size的1.5倍进行扩容。

        4.2 ArrayList的常用方法

        ArrayList提供方法比较多，但常用方法如下所示：

方法	解释
boolean add(E e)	尾插 e
void add(int index, E e)	将 e 插入到 index位置
boolean addAll(Collection<? extends E> c)	尾插 c 中的元素
E remove(int index)	删除 index位置的元素
boolean remove(Object o)	删除遇到的第一个 o
E get(int index)	获取下标 index 位置的元素
E set(int index, E e)	将下标 index位置元素设为 e
void clear()	清空
boolean contains(Object o)	判断 o是否在线性表中
int indexOf(Object o)	返回第一个 o所在下标
int lastIndexOf(Object o)	返回最后一个 o所在下标
List<E> subList(int fromIndex, int toIndex)	截取部分list

public static void main(String[] args) {ArrayList<Integer> list1=new ArrayList<>(10);list1.add(1);list1.add(2);list1.add(3);list1.add(4);System.out.println(list1);// 1 2 3 4//获取list1中有效元素的个数并打印System.out.println(list1.size());//4System.out.println("====");//获取和设置index位置的元素System.out.println(list1.get(2));//3list1.set(2,99);System.out.println(list1.get(2));//99System.out.println("====");//在index位置插入valuelist1.add(2,88);System.out.println(list1);//1 2 88 99 4System.out.println("====");//删除指定元素list1.remove(new Integer(88));System.out.println(list1);//1 2 99 4//删除index位置的元素   index不能超过list1的有效元素个数list1.remove(2);System.out.println(list1);// 1 2 4System.out.println("====");//检查list1中是否包含valueSystem.out.println(list1.contains(99));//falseSystem.out.println(list1.contains(2));//trueSystem.out.println("====");list1.add(2);list1.add(1);System.out.println(list1);//1 2 4 2 1//获取第一次出现value的下标System.out.println(list1.indexOf(1));//0//获取最后一次出现value的下标System.out.println(list1.lastIndexOf(1));//4System.out.println("====");//截取list1   List<E> subList(int fromIndex, int toIndex)List<Integer> list2=list1.subList(1,3);System.out.println(list2);//2 4//截取的list2并没有分配内存，只是list2这个引用指向下标为1~2的元素list2.set(0,10);System.out.println(list1);// 1 10 4 2 1System.out.println(list2);//10  4
}

        

        4.3 ArrayList的遍历

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

public static void main(String[] args) {ArrayList<Integer> list=new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);//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.iterator();while (it.hasNext()){System.out.print(it.next()+" ");}
}

        4.4 ArrayList的扩容机制

        ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。以下是ArrayList源码中扩容方式：

        检测是否需要扩容，如果需要调用grow函数；估计容量大小，初步估计按1.5倍扩容，若用户所需超过估计的1.5倍大小，按用户所需大小扩容；扩容前进行检测是否能扩容；使用copyOf进行扩容。

五、ArrayList的具体使用

        5.1 简单洗牌算法

public class Card {//花色private String design_and_color;//数值private int value;public Card(String design_and_color, int value) {this.design_and_color = design_and_color;this.value = value;}@Overridepublic String toString() {return "花色："+design_and_color+" 数值："+value;}public String getDesign_and_color() {return design_and_color;}public void setDesign_and_color(String design_and_color) {this.design_and_color = design_and_color;}public int getValue() {return value;}public void setValue(int value) {this.value = value;}
}

public class CardText {//花色集合  红桃 ♥   黑桃  ♠   方块♦  梅花 ♣public static final String[] design_and_colors= {"♥", "♣", "♠", "♦"};//买一副牌public static List<Card> buyCard(){/*没有大小王，共52张牌，J Q K 分别用11 12 13代替*/List<Card> card=new ArrayList<>(52);for (int i = 0; i < 4; i++) {for(int j=1;j<=13;j++){Card card1=new Card(design_and_colors[i],j);card.add(card1);}}return card;}//洗牌public static  void brushCard(List<Card> cards){for (int i = 51; i >0 ; i--) {Random random=new Random(i);int j=random.nextInt(i);swap(cards,i,j);}}//交换两张牌public  static <j> void swap(List<Card> cards, int i,int j){Card tmp=cards.get(i);cards.set( i,cards.get(j));cards.set( j,tmp);}public static void main(String[] args) {//取一副牌List<Card> card=buyCard();System.out.println("拿到一副牌：");System.out.println(card);//洗牌brushCard(card);System.out.println("洗牌后：");System.out.println(card);//发牌 三人轮流拿牌，每人五张List<List<Card>> hands=new ArrayList<>();//hands代表三人各自取的牌hands.add(new ArrayList<>());//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(card.remove(0));}}System.out.println("第一个人手中的牌：");System.out.println(hands.get(0));System.out.println("第二个人手中的牌：");System.out.println(hands.get(1));System.out.println("第三个人手中的牌：");System.out.println(hands.get(2));System.out.println("剩余的牌：");System.out.println(card);}
}

        5.2 杨辉三角

               杨辉三角题目链接

public List<List<Integer>> generate(int numRows) {List<List<Integer>> list=new ArrayList<>();//设置第一行List<Integer> list2=new ArrayList<>();list2.add(1);list.add(list2);//设置剩余行for(int i=1;i<numRows;i++){//设置当前行List<Integer> tmp=new ArrayList<>();//设置当前行第一个数tmp.add(1);//获取前一行List<Integer> preRow=list.get(i-1);//设置当前行其他数for(int j=1;j<i;j++){int a=preRow.get(j-1)+preRow.get(j);tmp.add(a);}//设置当前行最后一个数tmp.add(1);list.add(tmp);}return list;
}

六、ArrayList的问题

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

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

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