数据结构-ArrayList和顺序表

1.线性表

线性表是n个具有相同类型的数据元素所组成的有限序列，当n=0时，线性表为一个空表。

常见的线性表：顺序表，链表，栈和队列...

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

2.顺序表

2.1 什么是顺序表

顺序表是一段连续的存储单元来依次存储线性表中的数据元素。一般情况下采用数组存储。

2.2 顺序表的特点

1.存储连续：顺序表的存储单元在内存中是连续的，这意味着每个元素的地址都是相邻连续的

2.随机访问：由于存储单元是连续的，可以通过元素的下标直接访问该位置的元素，时间复杂度为O(1)

3.存储密度高：顺序表的存储单元只存储数据元素本身，没有额外的存储开销

2.3 实现一个顺序表

public class MySequentialList{private int[] array;private int size;//默认构造方法MySequentialList(){}//将顺序表的容量设为initCapacityMySequentialList(int initCapacity){}//在数组末尾新增一个元素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位置上的元素设置为valuepublic void set(int pos,int value){}//删除第一次出现的关键字keypublic void remove(int toRemove){}//获取顺序表的长度public int size(){}//清空顺序表public void clear(){}
}

实现的思路：

1.MySequentialList(int initCapacity)

只需要将数组初始化大小为initCapacity即可

2.add(int data)

在数组最后的位置新增元素，要注意数组是否已满，如果已满，就要对数组进行扩容操作

3.add(int pos,int data)

首先要判断插入位置pos是否合法，如果pos小于0或pos大于数组的长度，则位置不合法要进行异常处理。如果位置合法，还要判断数组是否已满，进行插入操作时，要注意先将原pos以及pos后面的元素全都向后移动一位，再进行插入操作，如果直接插入，则只是单纯的元素覆盖。插入后，数组的长度加1

4.contains(int toFind)

判断是否包含某个元素，只需要遍历数组并进行比较，看数组中是否有存在要查找的元素，如果有，则返回true，没有则返回false

5.indexOf(int toFind)

遍历数组，看数组中是否存在要查找的元素，如果存在，则返回给元素位置的下标，如果不存在，则返回-1

6.get(int pos)

获取pos位置的元素，首先要判断pos位置是否合法，如果pos小于0或者pos大于数组的长度，则pos不合法，返回-1。如果合法，直接返回下标为pos的元素

7.set(int pos,int value)

给pos位置的元素设置为value，单纯的进行对应下标元素覆盖即可

8.remove(int toRemove)

删除第一次出现关键字key，遍历数组，看key是否存在。如果不存在，则返回-1。如果存在，只需要将该位置后面的所有元素先前移动一位即可

9.size()

直接返回数组的有效长度，有效长度指的是数组中有效元素的个数，不是单纯的数组长度

10.clear()

清空顺序表，重新初始化数组，并将数组的长度置为0

我们后续以ArrayList的实现为例。

3.ArrayList

3.1 什么是ArrayList

在集合框架中，ArrayList是 Java 标准库中的一个非常常用的类，它实现了 List接口，提供了动态数组的功能。 ArrayList内部使用数组来存储元素，因此它具备顺序表的所有特点，是顺序表的一种实现。

说明：

1.ArrayList 是以泛型的方式实现的，使用时必须要先实例化

2.ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问

3.ArrayList实现了Cloneable接口，表明ArrayList是可以clone的

4.ArrayList实现了Serializable接口，表面ArrayList是支持序列化的

5.ArrayList是线程不安全的，在单线程下可以使用

6.ArrayList是通过动态的数组实现的，是一段连续的空间，并且可以进行扩容

3.2 ArrayList的构造方法

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

代码演示：

public class Test {public static void main(String[] args) {//无参构造List<Integer> list1=new ArrayList<>();//利用其他Collection构建ArrayListArrayList<Integer> arrayList=new ArrayList<>();List<Integer> list2=new ArrayList<>(arrayList);//指定顺序表容量List<Integer> list3=new ArrayList<>(10);}
}

3.3 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

代码演示：

import java.util.ArrayList;
import java.util.List;public class Test {public static void main(String[] args) {List<Integer> list=new ArrayList<>();System.out.println(list);//在尾部插入元素list.add(1);list.add(5);list.add(3);list.add(5);list.add(10);System.out.println(list);//在下标为2的位置增加元素list.add(2,4);System.out.println(list);//删除下标为2的元素list.remove(2);System.out.println(list);//删除遇到的第一个5元素Integer a=5;list.remove(a);System.out.println(list);//获取下标为1的元素int e=list.get(1);System.out.println(e);//将下标为1的元素设置为99list.set(1,99);System.out.println(list);//判断5是否在线性表中System.out.println(list.contains(5));//返回第一个5所在的下标e=list.indexOf(5);System.out.println(e);//返回最后一个5所在的下标e= list.lastIndexOf(5);System.out.println(e);//截取部分list,左闭右开List<Integer> newList=new ArrayList<>();newList=list.subList(1,3);System.out.println(newList);//将newList中的元素全部添加入list中list.addAll(newList);System.out.println(list);//清空listlist.clear();System.out.println(list);}
}

3.4 ArrayList的遍历

ArrayList的遍历方式主要分为3种：

1.for循环搭配下标

2.foreach

3.使用迭代器

public class Test {public static void main(String[] args) {List<String> list=new ArrayList<>();list.add("hajimi");list.add("is");list.add("a");list.add("cat");//使用for循环搭配下标for(int i=0;i<list.size();i++){System.out.print(list.get(i)+" ");}System.out.println();//使用foreach遍历for(String s:list){System.out.print(s+" ");}System.out.println();//使用迭代器遍历Iterator<String> it=list.listIterator();while(it.hasNext()){System.out.print(it.next()+" ");}}
}

4.深度理解ArrayList 的扩容机制

观察原码：

int DEFAULT_CAPACITY表示默认的容量大小

Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA表示默认的空间

Object[] elementData表示存放元素的空间

ArrayList的无参构造函数，将elementData初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，这是一个空数组，用于创建一个具有默认容量为 10的空ArrayList

ArrayList的add方法首先调用ensureCapacityInternal(size+1)，size表示当前顺序表的有效长度，size+1表示添加元素后应有的长度

size+1的值传递给ensureCapacityInternal的形参minCapacity，ensureCapacityInternal先调用calculateCapacity(Object[] element,int minCapacity)传入存放元素的空间elementData和minCapacity

calculateCapacity(Object[] elementData,int minCapacity)用来计算ArrayList需要增长到的最小容量。判断elementData是否等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，如果相等则意味着ArrayList当前没有分配任何容量，是空的。在这种情况下，方法返回DEFAULT_CAPACITY(10)和minCapacity中的较大值。如果element不是空数组，则意味着ArrayList已经有了一些容量，这种情况下，直接返回minCapacity，可以保证它至少增长到minCapacity即可

calculateCapacity的返回值传递给ensureExplicitCapacity的形参minCapacity，判断当前是否需要扩容，如果minCapacity大于数组的长度，则表示需要进行扩充

ArrayList的扩容函数grow(int minCapacity)用于增加ArrayList的内部数组elementData的容量，使其至少容纳minCapacity个元素。

int newCapacity=oldCapacity+(oldCapacity >> 1)计算新的容量，通常是当前容量的1.5倍

if(newCapacity - minCapacity < 0)判断新容量是否满足最小的需求，如果计算出的容量仍然小于最小的容量，则将newCapacity设置为minCapacity

if(newCapacity-MAX_ARRAY_SIZE > 0)检查新容量是否超出最大数组的大小，如果超过了调用hugeCapacity处理这种情况(将新容量设为Integer.MAX_VALUES)

elementData = Arrays.copyOf(elementData,newCapacity)使用copyOf创建一个新的数组，并将就数组中的元素复制到新数组中。

总结：

1.首先判断是否需要进行扩容，如果需要进行扩容，调用grow方法

2.计算扩容所需的最小的容量

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

如果用户所需大小大于预估的1.5倍，则按照用户所需大小进行扩容

扩容前检查是否可以扩容成功，防止太大导致扩容失败

3.使用Arrays.copyOf进行扩容

5.实现一个ArrayList

package datastructure;import java.util.Arrays;public class MyArrayList {public int[] elem;public int usedSize;//0//默认容量private static final int DEFAULT_SIZE = 2;public MyArrayList() {this.elem = new int[DEFAULT_SIZE];}/*** 打印顺序表:*   根据usedSize判断即可*/public void display() {for(int i=0;i<this.usedSize;i++){System.out.print(elem[i]+" ");}System.out.println();}// 新增元素,默认在数组最后新增public void add(int data) {if(isFull()){//扩容this.elem=Arrays.copyOf(this.elem,2*this.elem.length);}this.elem[this.usedSize]=data;this.usedSize++;}/*** 判断当前的顺序表是不是满的！* true:满   false代表空*/public boolean isFull() {if(this.usedSize==this.elem.length){return true;}return false;}private boolean checkPosInAdd(int pos) {if(pos<0||pos>usedSize){System.out.println("位置不合法");return false;}return true;//合法}// 在 pos 位置新增元素//移动数据，从后向前防止数值被覆盖public void add(int pos, int data) {if(pos<0||pos>this.usedSize){System.out.println("位置不合法");return;}if(isFull()){//扩容this.elem=Arrays.copyOf(this.elem,2*this.elem.length);}for(int i=this.usedSize-1;i>=pos;i--){this.elem[i+1]=this.elem[i];}this.elem[pos]=data;usedSize++;}// 判定是否包含某个元素public boolean contains(int toFind) {for(int i=0;i<this.usedSize;i++){if(elem[i]==toFind){return true;}}return false;}// 查找某个元素对应的位置public int indexOf(int toFind) {if(isEmpty()){System.out.println("表中没有元素");return -1;}for(int i=0;i<usedSize;i++){if(elem[i]==toFind){return i;}}System.out.println("没找到");return -1;}// 获取 pos 位置的元素public int get(int pos) {if(pos<0&&pos>=usedSize){System.out.println("输入不合法！");return -1;}if(!isEmpty()){return elem[pos];}return -1;}private boolean isEmpty() {if(usedSize==0){return true;}return false;}// 给 pos 位置的元素设为【更新为】 valuepublic void set(int pos, int value) {if(pos<0||pos>=usedSize)return;elem[pos]=value;}/*** 删除第一次出现的关键字key* @param key*/public void remove(int key) {int index=indexOf(key);if(index==-1){return;}for(int i=index;i<usedSize-1;i++){this.elem[i]=this.elem[i+1];}this.usedSize--;}// 获取顺序表长度public int size() {return this.usedSize;}// 清空顺序表public void clear() {this.usedSize=0;}
}