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保举写法：

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

复制代码

 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的遍历

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.         //直接sout打印
9.         System.out.println("===sout===");
10.         System.out.println(list);
11.         // 使用下标+for遍历
12.         System.out.println("===for===");
13.         for (int i = 0; i < list.size(); i++) {
14.             System.out.print(list.get(i) + " ");
15.         }
16.         System.out.println();
17.         // 借助foreach遍历
18.         System.out.println("===foreach===");
19.         for (Integer integer : list) {
20.             System.out.print(integer + " ");
21.         }
22.         System.out.println();
23.         //迭代器
24.         System.out.println("===Iterator===");
25.         Iterator<Integer> it1 = list.iterator();
26.         while (it1.hasNext()) {
27.             System.out.print(it1.next() + " ");
28.         }
29.         System.out.println();
31.         System.out.println("===ListIterator===");
32.         //专门给List用的迭代器
33.         ListIterator<Integer> it2 = list.listIterator();
34.         while(it2.hasNext()){
35.             System.out.print(it2.next() + " ");
36.         }
37.         System.out.println();
38.         System.out.println("===ListIterator 倒着打印===");
39.         ListIterator<Integer> it3 = list.listIterator(list.size());
40.         while (it3.hasPrevious()) {
41.             System.out.print(it3.previous() + " ");
42.         }
43.         System.out.println();
44.         
45.     }

复制代码

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

那hasprevious其实是判断前面是否另有？是true否false
previous向前移一位，sout并打印
 
2.4 ArratList扩容机制

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

1. Object[] elementData;   // 存放元素的空间
2. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  // 默认空间
3. private static final int DEFAULT_CAPACITY = 10;  // 默认容量大小
4. public boolean add(E e) {
5.      ensureCapacityInternal(size + 1);  // Increments modCount!!
6.      elementData[size++] = e;
7.      return true;
8. }
9. private void ensureCapacityInternal(int minCapacity) {
10.      ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
11. }
12. private static int calculateCapacity(Object[] elementData, int minCapacity) {
13.      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
14.          return Math.max(DEFAULT_CAPACITY, minCapacity);
15.      }
16.      return minCapacity;
17. }
18. private void ensureExplicitCapacity(int minCapacity) {
19.      modCount++;
20. // overflow-conscious code
21.      if (minCapacity - elementData.length > 0)
22.          grow(minCapacity);
23. }
25. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
27. private void grow(int minCapacity) {
28. // 获取旧空间大小
29.     int oldCapacity = elementData.length;
30. // 预计按照1.5倍方式扩容
31.     int newCapacity = oldCapacity + (oldCapacity >> 1);
32. // 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容
33. 比特就业课
34.     if (newCapacity - minCapacity < 0)
35.        newCapacity = minCapacity;
36. // 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小
37.     if (newCapacity - MAX_ARRAY_SIZE > 0)
38.          newCapacity = hugeCapacity(minCapacity);
39. // 调用copyOf扩容
40.     elementData = Arrays.copyOf(elementData, newCapacity);
41. }
42. private static int hugeCapacity(int minCapacity) {
43. // 如果minCapacity小于0，抛出OutOfMemoryError异常
44.     if (minCapacity < 0)
45.         throw new OutOfMemoryError();
47.      return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
48. }

复制代码

  【总结】
  1. 检测是否真正必要扩容，假如是调用grow预备扩容
  2. 预估必要库容的大小
  

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

  3. 使用copyOf举行扩容
   
3. 实现顺序表

简单实现一下顺序表的大概
把要实现的方法都放在接口中：

1. public interface IList {
2.     // 新增元素,默认在数组最后新增
3.     void add(int data);
4.     // 在 pos 位置新增元素
5.     void add(int pos, int data);
6.     // 判定是否包含某个元素
7.     boolean contains(int toFind);
8.     // 查找某个元素对应的位置
9.     int indexOf(int toFind);
10.     // 获取 pos 位置的元素
11.     int get(int pos);
12.     // 给 pos 位置的元素设为 value -> 更新
13.     void set(int pos, int value);
14.     //删除第一次出现的关键字key
15.     void remove(int toRemove);
16.     // 获取顺序表长度
17.     int size();
18.     // 清空顺序表
19.     void clear();
20.     // 打印顺序表，
21.     // 注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
22.     void display();
23. }

复制代码

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

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

复制代码

size会默以为0，全部不消对他初始化

3.1 实现add

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

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

1.    @Override
2.     public void add(int data) {
3.         if(isFull()){
4.             //拷贝原有元素并，扩容两倍
5.             this.array = Arrays.copyOf(array,size * 2);
6.         }
7.         this.array[size] = data;
8.         this.size++;
9.     }
11.     @Override
12.     public boolean isFull() {
13.         if(array.length == size){
14.             return true;
15.         }
16.         return false;
17.     }

复制代码

利用Arrays.copyOf举行扩容，他不但可以拷贝原有的元素，还可以举行扩容操纵。
   

那么在来做指定位置插入:
想要在指定位置插入，但是又不删除原位置的数据，就必须要移动
想要达到此效果，就必要从有用数据末了位置一个一个往后移动终极直接用给定的下标举行插入就可以了。
但是一旦有下标就必要举行判断下标是否合法：

1.     @Override
2.     public void add(int pos, int data) {
3.        try {
4.            checkPosOfAdd(pos);//检查pos是否合法
5.        }catch (PosNotLegalException e) {
6.            e.printStackTrace();
7.        }
8.         //移动原数组
9.         for (int i = size-1; i >= pos; i--) {
10.             this.array[i + 1] = this.array[i];
11.         }
12.         this.array[pos] = data;
13.         this.size++;
15.     }
17.     private void checkPosOfAdd(int pos) {
18.         if(pos > size || pos < 0) {
19.             throw new PosNotLegalException("位置不合法");
20.         }
21.     }

复制代码

  注意：
  尾插是可以做到的，以是判断pos合法性的时间 pos == size的位置可以不做判断
  异常：

1. public class PosNotLegalException extends RuntimeException{
2.     public PosNotLegalException() {
4.     }
6.     public PosNotLegalException(String mag) {
7.         super(mag);
8.     }
9. }

复制代码

3.2 实现contains

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

复制代码

3.3 实现indexOf 

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

复制代码

3.4 实现get

1.     @Override
2.     public int get(int pos) {
3.         try {
4.             checkPosOfGetAndSet(pos);//检查pos位置是否合法
5.         }catch (PosNotLegalException e) {
6.             e.printStackTrace();
7.         }
9.         return this.array[pos];
11.     }
12.     private void checkPosOfGetAndSet(int pos) {
13.         if(pos >= size || pos < 0) {
14.             throw new PosNotLegalException("Get/Set位置不合法");
15.         }
16.     }

复制代码

3.5 实现set

1.     @Override
2.     public void set(int pos, int value) {
3.         try {
4.             checkPosOfGetAndSet(pos);
5.         }catch (PosNotLegalException e) {
6.             e.printStackTrace();
7.         }
8.         array[pos] = value;
9.     }

复制代码

3.6 实现remove

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

1.     @Override
2.     public void remove(int toRemove) {
3.         int pos = indexOf(toRemove);
4.         if(pos == -1) {
5.             System.out.println("没有要删除的数字");
6.             return;
7.         }
10.         for (int i = pos; i < size; i++) {
11.             array[i] = array[i+1];
12.         }
13.         this.array[size] = 0;
14.         this.size--;
15.     }

复制代码

 3.7 实现size

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

复制代码

3.8 实现clear

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

复制代码

3.9 实现display

1.     @Override
2.     public void display() {
3.         for (int i = 0; i < size; i++) {
4.             System.out.print(array[i] + " ");
5.         }
6.         System.out.println();
7.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。