JAVA-顺序表ArrayList(实现ArrayList)

1.线性表

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

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

1.1 什么是List

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

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

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

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

1.2 List常用方法

List常用方法：

List所有方法：

 

1.3 List的使用

注意：List是个接口，并不能直接用来实例化。

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

2. 顺序表

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

2.1 ArrayList简介

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

【说明】

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

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

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

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

5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者 CopyOnWriteArrayList

6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

2.2 ArrayList的使用 

2.2.1 ArrayList的构造方法

ArrayList有三个构造方法

无参的构造方法 ：

 

参数为int的构造方法：

泛型参数构造方法:

由于这个方法：套了很多方法不好讲解，我就对参数和最终使用做讲解

 使用：

ArrayList推荐写法：

public static void main(String[] args) {// ArrayList创建，推荐写法// 构造一个空的列表List<Integer> list1 = new ArrayList<>();// 构造一个具有10个容量的列表List<Integer> list2 = new ArrayList<>(10);list2.add(1);list2.add(2);list2.add(3);// list2.add("hello");  // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素// list3构造好之后，与list中的元素一致ArrayList<Integer> list3 = new ArrayList<>(list2);// 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难List list4 = new ArrayList();list4.add("111");list4.add(100);}

 2.2.2 ArrayList常见方法

2.2.2.1 add或者addAll

一共有3种方法：

 

2.2.2.2  remove

 

2.2.2.3 get和set

这个很简单就不多说了

 

 2.2.2.4 contains

 判断是否有这个参数

2.2.2.5 indexOf和lastIndexOf

 

2.2.2.6 subList

注意：java中凡是区间都是左闭右开[ , )  也就是说上面代码只能截取到1和2下标 

2.2.2.7 clear

清空顺序表

2.3 ArrayList的遍历

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);//直接sout打印System.out.println("===sout===");System.out.println(list);// 使用下标+for遍历System.out.println("===for===");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();// 借助foreach遍历System.out.println("===foreach===");for (Integer integer : list) {System.out.print(integer + " ");}System.out.println();//迭代器System.out.println("===Iterator===");Iterator<Integer> it1 = list.iterator();while (it1.hasNext()) {System.out.print(it1.next() + " ");}System.out.println();System.out.println("===ListIterator===");//专门给List用的迭代器ListIterator<Integer> it2 = list.listIterator();while(it2.hasNext()){System.out.print(it2.next() + " ");}System.out.println();System.out.println("===ListIterator 倒着打印===");ListIterator<Integer> it3 = list.listIterator(list.size());while (it3.hasPrevious()) {System.out.print(it3.previous() + " ");}System.out.println();}

这里面迭代器可能大家看不懂我给大家说明一下：

那hasprevious其实是判断前面是否还有？是true否false

previous向前移一位，sout并打印

 

2.4 ArratList扩容机制

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

Object[] elementData;   // 存放元素的空间
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  // 默认空间
private static final int DEFAULT_CAPACITY = 10;  // 默认容量大小
public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private void grow(int minCapacity) {// 获取旧空间大小int oldCapacity = elementData.length;// 预计按照1.5倍方式扩容int newCapacity = oldCapacity + (oldCapacity >> 1);// 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容
比特就业课if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// 调用copyOf扩容elementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {// 如果minCapacity小于0，抛出OutOfMemoryError异常if (minCapacity < 0)throw new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}

【总结】

1. 检测是否真正需要扩容，如果是调用grow准备扩容

2. 预估需要库容的大小

• 初步预估按照1.5倍大小扩容
• 如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
• 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败

3. 使用copyOf进行扩容

 

3. 实现顺序表

简单实现一下顺序表的大概

把要实现的方法都放在接口中：

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

在用类去实现此接口，后面所有的方法都在此类中实现：

public class MyArrayList implements IList{private int[] array;//存放数据private int size;//用来记录元素个数//实现一个构造方法，默认初始化为大小为10public MyArrayList(){this.array = new int[10];}
}

size会默认为0，所有不用对他初始化

3.1 实现add

我们有size实现作为记录元素个数的下标，当刚好可以做为尾插的位置

 

但如果刚好满了，我们就需要扩容所以，可以用单独写一个方法判断一下

   @Overridepublic void add(int data) {if(isFull()){//拷贝原有元素并，扩容两倍this.array = Arrays.copyOf(array,size * 2);}this.array[size] = data;this.size++;}@Overridepublic boolean isFull() {if(array.length == size){return true;}return false;}

利用Arrays.copyOf进行扩容，他不仅可以拷贝原有的元素，还可以进行扩容操作。

 

那么在来做指定位置插入:

想要在指定位置插入，但是又不删除原位置的数据，就必须要移动

想要达到此效果，就需要从有效数据最后位置一个一个往后移动最终直接用给定的下标进行插入就可以了。

但是一旦有下标就需要进行判断下标是否合法：

    @Overridepublic void add(int pos, int data) {try {checkPosOfAdd(pos);//检查pos是否合法}catch (PosNotLegalException e) {e.printStackTrace();}//移动原数组for (int i = size-1; i >= pos; i--) {this.array[i + 1] = this.array[i];}this.array[pos] = data;this.size++;}private void checkPosOfAdd(int pos) {if(pos > size || pos < 0) {throw new PosNotLegalException("位置不合法");}}

注意：

尾插是可以做到的，所以判断pos合法性的时候 pos == size的位置可以不做判断

异常：

public class PosNotLegalException extends RuntimeException{public PosNotLegalException() {}public PosNotLegalException(String mag) {super(mag);}
}

3.2 实现contains

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

3.3 实现indexOf 

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

3.4 实现get

    @Overridepublic int get(int pos) {try {checkPosOfGetAndSet(pos);//检查pos位置是否合法}catch (PosNotLegalException e) {e.printStackTrace();}return this.array[pos];}private void checkPosOfGetAndSet(int pos) {if(pos >= size || pos < 0) {throw new PosNotLegalException("Get/Set位置不合法");}}

3.5 实现set

    @Overridepublic void set(int pos, int value) {try {checkPosOfGetAndSet(pos);}catch (PosNotLegalException e) {e.printStackTrace();}array[pos] = value;}

3.6 实现remove

直接用indexOf判断是否有这个数据,有就从pos后面的数据一个个向前移动，但是最后的那个元素还是会在原位置上，不用担心size-1就可以做到删除了，再次add数据就会覆盖到他

    @Overridepublic void remove(int toRemove) {int pos = indexOf(toRemove);if(pos == -1) {System.out.println("没有要删除的数字");return;}for (int i = pos; i < size; i++) {array[i] = array[i+1];}this.array[size] = 0;this.size--;}

 3.7 实现size

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

3.8 实现clear

    @Overridepublic void clear() {for (int i = 0; i < size; i++) {this.array[i] = 0;
//            this.array[i] = null;   如果顺序表是指针类型需要全部置为空
//        因为，只要没有引用这篇空间的引用，才会释放}this.size = 0;}

3.9 实现display

    @Overridepublic void display() {for (int i = 0; i < size; i++) {System.out.print(array[i] + " ");}System.out.println();}