List与ArrayList

た入场券 2024-03-08 08:56 87阅读 0赞

**目录**

一、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。  
![aef16e308e614186b5b23c181f6ab9d2.png][]

Collection也是一个接口，该接口中规范了后序容器中常用的一些方法：  
![19e94ec6ac1b46e1a02b2159175ff859.png][]

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

![a19165f6975c42c3a188de49b16b9545.png][]

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

### 1.2 常见接口的介绍 ###

List中有许多方法：

![e7e54bb13a7a4631b84b10c0e4b497f0.png][]

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

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

### 1.3 List的使用 ###

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

## 二、线性表和顺序表 ##

### 2.1 线性表 ###

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

### 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);
>         //删除第一次出现的关键字key
>         public 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;
>         }
>     
>         //添加一个数据
>         @Override
>         public void add(int data) {
>             chackCapacity();
>             this.elem[usedSize]=data;
>             this.usedSize++;
>         }
>         //检查容量
>         private void chackCapacity(){
>             if(isFull()){
>                 elem= Arrays.copyOf(elem,elem.length*2);
>             }
>         }
>     
>         //在pos插入一个数据
>         @Override
>         public 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
>         @Override
>         public boolean contains(int toFind) {
>             if(isEmpty())
>                 return false;
>             for (int x:elem) {
>                 if(x==toFind)
>                     return true;
>             }
>             return false;
>         }
>         //获取toFing对应的下标
>         @Override
>         public int indexOf(int toFind) {
>             for (int i = 0; i < this.usedSize; i++) {
>                 if(elem[i]==toFind)
>                     return i;
>             }
>             return -1;
>         }
>         //获取pos下标对应的元素值
>         @Override
>         public int get(int pos) {
>             if(isEmpty())
>                 return -1;
>             chackPosOnAddOrGetOrSet(pos);
>             return this.elem[pos];
>         }
>         //设置下标为pos的元素值为value
>         @Override
>         public void set(int pos, int value) {
>             chackPosOnAddOrGetOrSet(pos);
>             elem[pos]=value;
>         }
>         //删除toRemove
>         @Override
>         public 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--;
>         }
>         //获取当前顺序表的大小
>         @Override
>         public int size() {
>             return this.usedSize;
>         }
>         //清空
>         @Override
>         public void clear() {
>             for (int i = 0; i < usedSize; i++) {
>                 set(i,0);
>             }
>         }
>         /*遍历顺序表当中的元素*/
>         @Override
>         public void display() {
>             if(isEmpty()){
>                 throw new MyArrayIsEmpty("顺序表是空的");
>             }
>             for(int i=0;i<elem.length;i++){
>                 System.out.println(this.elem[i]+" ");
>             }
>             System.out.println();
>         }
>         /*判断顺序表是否已满*/
>         @Override
>         public boolean isFull() {
>             /*if(usedSize==DEFAULT_Size)
>                     return true;
>             else
>                 return false;*/
>             return  usedSize==DEFAULT_Size;
>         }
>     
>         @Override
>         public 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接口，具体框架如下：  
![ea8e289828834c4f9830600d2fc8ae90.png][]

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

## 四、ArrayList的使用 ##

### 4.1 ArrayList构造 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:252px;">方法</td> 
   <td style="width:247px;">解释</td> 
  </tr> 
  <tr> 
   <td style="width:252px;">ArrayList()</td> 
   <td style="width:247px;">无参构造</td> 
  </tr> 
  <tr> 
   <td style="width:252px;">ArrayList(Collection&lt;? extends E&gt; c)</td> 
   <td style="width:247px;">利用其他 Collection 构建 ArrayList</td> 
  </tr> 
  <tr> 
   <td style="width:252px;">ArrayList(int initialCapacity)</td> 
   <td style="width:247px;">指定顺序表初始容量</td> 
  </tr> 
 </tbody> 
</table>

>     public static void main(String[] args) {
>         //创建一个空列表 ArrayList()  默认size为0
>         ArrayList<Integer> list1=new ArrayList<>();
>     
>         //创建一个容量为10的列表  ArrayList(int initialCapacity)创建指定容量的列表
>         //ArrayList<Integer> 指定存放的元素类型为Integer
>         ArrayList<Integer> list2=new ArrayList<>(10);
>         list1.add(1);//第一次add时，底层数组size为10
>         list1.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提供方法比较多，但常用方法如下所示：

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

>     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());//4
>     
>         System.out.println("====");
>         //获取和设置index位置的元素
>         System.out.println(list1.get(2));//3
>         list1.set(2,99);
>         System.out.println(list1.get(2));//99
>     
>         System.out.println("====");
>         //在index位置插入value
>         list1.add(2,88);
>         System.out.println(list1);//1 2 88 99 4
>     
>         System.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 4
>     
>         System.out.println("====");
>         //检查list1中是否包含value
>         System.out.println(list1.contains(99));//false
>         System.out.println(list1.contains(2));//true
>     
>         System.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));//4
>     
>         System.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 1
>         System.out.println(list2);//10  4
>     }

![2f6c7a1884d34a12853e47f53de6dea6.png][]

![18b6ed9dcc014a3baf139fde11dc118d.png][]

### 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()+" ");
>         }
>     }

![fa2f13a417cf4cffb3f0d763b9a51db8.png][]

### 4.4 ArrayList的扩容机制 ###

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

![3347cb17bdc04624a223eb996057680b.png][]

检测是否需要扩容，如果需要调用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;
>         }
>     
>         @Override
>         public 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 杨辉三角 ###

[ 杨辉三角题目链接][Link 1]

>     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个数据空间。

[aef16e308e614186b5b23c181f6ab9d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/369dfaa720464cb48273425aed375f30.png
[19e94ec6ac1b46e1a02b2159175ff859.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/b4c311e7872d4ccd977c5f3e880c81c1.png
[a19165f6975c42c3a188de49b16b9545.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/00c70ea82bc34cf59f9d904bc53b0f80.png
[e7e54bb13a7a4631b84b10c0e4b497f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/0dd34bd4fc7a42259f78ef55e239b536.png
[79fee97720394f3c8e02c39cafbf846a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/fefb4fc762e742ae81d073ca085890a3.png
[ea8e289828834c4f9830600d2fc8ae90.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/b3e13515576e4a40a01e5198bcb3df62.png
[2f6c7a1884d34a12853e47f53de6dea6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/de0de2affcaf4d3a8707160496a463b0.png
[18b6ed9dcc014a3baf139fde11dc118d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/85bdb5d932cf4530a3a1ee9fbd1b1040.png
[fa2f13a417cf4cffb3f0d763b9a51db8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/d24e3b671e584cce836b702d9fc81088.png
[3347cb17bdc04624a223eb996057680b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/8a5e98672e1245e2a228e072288a2d7d.png
[Link 1]: https://leetcode.cn/problems/pascals-triangle/