devbox
菜鸟追梦旅行
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】动态数组

作者：菜鸟追梦旅行 | 2024-02-20 02:00:46

赞

踩

动态数组

目录

一、线性表接口

二、动态数组

2.1动态数组的变量和构造方法

2.2添加元素

2.3输出数组的字符串形式

2.4在索引为index的位置插入新元素

2.5查询线性表中是否包含指定元素

2.6返回索引为index的元素值

2.7修改索引为index位置的元素为新值，返回修改前的元素值

2.8删除线性表中索引为index的元素，返回删除前的元素值

2.9删除第一个值为val的元素

2.10在线性表中删除所有值为val的元素

三、JDK中动态数组的实现

3.1ArrayList的定义、继承或实现的接口

3.2ArrayList的具体常见使用

3.2.1构造方法

3.2.2常用操作方法

 3.2.3 ArrayList的三种遍历方式

3.3分析JDK中ArrayList

3.3.1 无参构造

 3.3.2添加以及扩容机制

 3.4ArrayList的特点

满足以下两个要求的数据结构称为线性表：

（1）保存在线性表中的元素都是相同类型的。

（2）元素之间线性排列，元素和元素之间逻辑上是连续的，索引为0的元素一定是逻辑上在索引为1的元素之前。

线性表有一个最大的特点，就是有明确的索引下标的概念。

线性表示一个比较抽象的感念，具体实现有很多，数组，链表，栈，队列，字符串都是具体的线性表。Java接口优先原则，无论具体是那种线性表，操作盒方法应该对外都是统一的，接口定义了所有实现子类所共同应当具备的行为和规范。

JDK中线性表的接口称为List，无论是数组实现还是链表实现，操作线性表的方法都已经在List接口中定义好了。

基本数组特点：保存的单个相同类型的元素，一旦声明一个原始数组，无论采用哪种实例化方式，最终数组一旦定义，长度固定。

由于原始数组存在定长问题，因此，需要将原始数组做扩充，将原始数组封装到自定义的类中，让他具备可扩展干的能力=>对使用者来说，用户无需关心数组的长度问题，提供给用户的数组是一个动态数组，用户只需要使用提供的数组进行增删改查即可，无需关心数组的越界问题。

本质：将原始的数组封装到类中，对用户淡化数组长度的概念，当数组长度不够时，类的内部自己进行扩容操作，对用户透明。

动态数组 = 基本数组封装到类中 + 对外提供一系列的方便进行增删改查的方法。 

无论是数组还是链表都属于线性表的一种，所以只要是线性表的子类，都应该具备基础的增删改查方法。

定义线性表的规范：一个类能称之为是线性表的子类，应该具备类似的行为（都是保存单个元素的集合，集合中元素的类型是相同的，元素之间逻辑上连续）

一、线性表接口

定义线性表接口Seqlist。定义接口带来的好处：就是可以以非常低的成本来更换具体的子类。

  1. public interface SeqList {
  2.     void add(int val);
  3.     // 在索引为index的位置插入新元素
  4.     void add(int index,int val);
  5.     // 查询线性表中是否包含指定元素val
  6.     boolean contains(int val);
  7.     // 返回索引为index的元素值
  8.     int get(int index);
  9.     // 修改索引为index位置的元素为新值，返回修改前的元素值
  10.     int set(int index,int newVal);
  11.     // 删除线性表中索引为index的元素，返回删除前的元素值
  12.     int removeByIndex(int index);
  13.     // 删除第一个值为val的元素
  14.     void removeByValueOnce(int val);
  15.     // 在线性表中删除所有值为val的元素
  16.     void removeAllValue(int val);
  17. }

二、动态数组

2.1动态数组的变量和构造方法

首先需要设置一个内部数组用来存储输入的数组，然后设置一个size用来记录add方法中插入的位置。再设置一个默认变量，在无参构造中使用。

创建两个构造方法，如果没有输入明确的数组长度，默认产生对象时，初始化长度为10。另一个构造方法则输入了数组长度，创建一个相应长度的数组。

  1. public class MyArray implements SeqList {
  2.      private int[] elementData;
  3.      private int size;
  4.     private static final int DEFAULT_CAPACITY = 10;
  5.     public MyArray() {
  6.         this(DEFAULT_CAPACITY);
  7.     }
  8.      public MyArray(int capacity){
  9.          this.elementData = new int[capacity];
  10.      }
  11. }

2.2添加元素

首先需要排除非法情况，就是数组长度为0时，需要抛出异常。

size的位置恰好就是当前数组中尾部插入元素的位置，完全插入后size就可以记录当前线性表中的实际元素个数。

如果整个数组都被填满了，需要让数组在下一次插入前进行扩容，扩容后的就是根据原数组的内容拷贝过来，长度变为原来的1.5倍，超过原数组长度的内容。改变了原数组的引用，指向了扩容后的数组。

在扩容这里有一个隐藏风险，当原先数组长度为奇数个的时候，扩容失败，如果oldLength == 1，1 + 1 / 2 = 1 + 0 = 1，扩容没有成功，所以需要将newLength赋值为oldLength+((oldLength+1)>>1)。

  1.     public void add(int val) {
  2.         if (elementData.length == 0) {
  3.             throw new IllegalArgumentException("arr length cannot be zero!");
  4.         }
  5.         this.elementData[size] = val;
  6.         size ++;
  7.         if (size == elementData.length) {
  8.             grow();
  9.         }
  10.     }
  11.     private void grow(){
  12.         int oldLength = this.elementData.length;
  13.         int newLength = oldLength+((oldLength+1)>>1);
  14.         this.elementData = Arrays.copyOf(elementData,newLength);
  15.     }

2.3输出数组的字符串形式

将数组输出成字符串形式，需要借用StringBuilder中的append方法，将每个数组中的元素按顺序添加，然后输出字符串形式。

  1.     public String toString(){
  2.         StringBuilder s = new StringBuilder("[");
  3.         for (int i = 0; i < size; i++) {
  4.             s.append(this.elementData[i]);
  5.             if(i<size-1){
  6.                 s.append(",");
  7.             }
  8.         }
  9.         s.append("]");
  10.         return s.toString();
  11.     }
  1.     public static void main(String[] args) {
  2.         SeqList list = new MyArray(4);
  3.         list.add(1);
  4.         list.add(3);
  5.         list.add(5);
  6.         list.add(9);
  7.         System.out.println(list.toString());
  8.     }

2.4在索引为index的位置插入新元素

首先需要判断index的合法性，小于index和大于size都不合法。

如果index==size就是尾插法，可以直接调用add方法。

排除过后就可以将指定元素插入到索引位置，然后将本来在该位置的元素向后移一位，后面的每一个元素都向后移动一位，最后需要判断是否需要扩容为了方便下一步的add。

  1.     public void add(int index, int val) {
  2.         if (index < 0 || index > size) {
  3.             throw new IllegalArgumentException("add index illegal!");
  4.         }
  5.         if (index == size) {
  6.             add(val);
  7.             return;
  8.         }
  9.         if(index==this.elementData.length){
  10.             grow();
  11.         }
  12.         size++;
  13.         for(int i = index;i<size;i++){
  14.             int tmp = this.elementData[i];
  15.             this.elementData[i] = val;
  16.             val = tmp;
  17.         }
  18.  
  19.         if (size == elementData.length) {
  20.             grow();
  21.         }
  22.     }
  1.     public static void main(String[] args) {
  2.         SeqList list = new MyArray(4);
  3.         list.add(1);
  4.         list.add(3);
  5.         list.add(5);
  6.         list.add(9);
  7.         System.out.println(list.toString());
  8.         list.add(3,7);
  9.         System.out.println(list.toString());
  10.         list.add(0,7);
  11.         System.out.println(list.toString());
  12.         list.add(6,7);
  13.         System.out.println(list.toString());
  14.     }

2.5查询线性表中是否包含指定元素

查找整个数组，当遇到指定元素则返回true，如果不包含指定元素则返回false。

  1.     public boolean contains(int val) {
  2.         for(int i = 0;i<size;i++){
  3.             if(this.elementData[i]==val){
  4.                 return true;
  5.             }
  6.         }
  7.         return false;
  8.     }
  1.     public static void main(String[] args) {
  2.         SeqList list = new MyArray(4);
  3.         list.add(1);
  4.         list.add(3);
  5.         list.add(5);
  6.         list.add(9);
  7.         System.out.println(list.toString());
  8.         System.out.println(list.contains(9));
  9.         System.out.println(list.contains(8));
  10.     }

2.6返回索引为index的元素值

 首先需要判断index是否合法，创建了rangeCheck方法，排除了index < 0和index >= size的情况。

然后直接返回当前位置的元素。

  1.     public int get(int index) {
  2.         if (!rangeCheck(index)) {
  3.             throw new IllegalArgumentException("get index illegal!");
  4.         }
  5.         return elementData[index];
  6.     }
  7.     private boolean rangeCheck(int index) {
  8.         if (index < 0 || index >= size) {
  9.             return false;
  10.         }
  11.         return true;
  12.     }
  1.     public static void main(String[] args) {
  2.         SeqList list = new MyArray(4);
  3.         list.add(1);
  4.         list.add(3);
  5.         list.add(5);
  6.         list.add(9);
  7.         System.out.println(list.toString());
  8.         System.out.println(list.get(0));
  9.     }

2.7修改索引为index位置的元素为新值，返回修改前的元素值

同样首先判断index是否合法。

然后将索引位置的元素改成新的值，返回旧的值。

  1.     public int set(int index, int newVal) {
  2.         if (!rangeCheck(index)) {
  3.             throw new IllegalArgumentException("get index illegal!");
  4.         }
  5.         int temp = this.elementData[index];
  6.         this.elementData[index] = newVal;
  7.         return temp;
  8.     }
  1.     public static void main(String[] args) {
  2.         SeqList list = new MyArray(4);
  3.         list.add(1);
  4.         list.add(3);
  5.         list.add(5);
  6.         list.add(9);
  7.         System.out.println(list.toString());
  8.         System.out.println(list.set(3,7));
  9.         System.out.println(list.toString());
  10.     }

2.8删除线性表中索引为index的元素，返回删除前的元素值

首先先判断index是否合法。

然后将index位置后的每一个元素都向前移动一位，然后把size的数值减一，返回原本在索引位置上的值。

  1.     public int removeByIndex(int index) {
  2.         if (!rangeCheck(index)) {
  3.             throw new IllegalArgumentException("get index illegal!");
  4.         }
  5.         int tmp = this.elementData[index];
  6.         for(int i = index;i<size-1;i++){
  7.             this.elementData[i] = this.elementData[i+1];
  8.         }
  9.         size--;
  10.         return tmp;
  11.     }
  1.     public static void main(String[] args) {
  2.         SeqList list = new MyArray(4);
  3.         list.add(1);
  4.         list.add(3);
  5.         list.add(5);
  6.         list.add(9);
  7.         System.out.println(list.toString());
  8.         System.out.println(list.removeByIndex(3));
  9.         System.out.println(list.toString());
  10.     }

2.9删除第一个值为val的元素

直接遍历整个数组，当第一次遇到值为val的元素就调用removeByIndex方法，然后返回。

  1.     public void removeByValueOnce(int val) {
  2.         for(int i = 0;i<size;i++){
  3.             if(this.elementData[i]== val){
  4.                 removeByIndex(i);
  5.                 return ;
  6.             }
  7.         }
  8.     System.err.println("当前集合中不存在元素" + val);
  9.     }
  1.  public static void main(String[] args) {
  2.         SeqList list = new MyArray(4);
  3.         list.add(1);
  4.         list.add(9);
  5.         list.add(5);
  6.         list.add(9);
  7.         System.out.println(list.toString());
  8.         list.removeByValueOnce(9);
  9.         System.out.println(list.toString());
  10.         list.removeByValueOnce(2);
  11.         System.out.println(list.toString());
  12.     }

2.10在线性表中删除所有值为val的元素

直接遍历整个数组，当第一次遇到值为val的元素就调用removeByIndex方法，然后不返回，继续遍历。

这个时候有一个特殊情况，调用removeByIndex时可能补上来的元素值也是val，所以判断数组当前位置值是否为val需要用while循环。

  1.     public void removeAllValue(int val) {
  2.         boolean isRemoved = false;
  3.         for(int i = 0;i<size;i++){
  4.             while(this.elementData[i]== val){
  5.                 isRemoved = true;
  6.                 removeByIndex(i);
  7.             }
  8.         }
  9.         if (!isRemoved) {
  10.             System.err.println("当前集合中不存在元素" + val);
  11.         }
  12.     }
  1.     public static void main(String[] args) {
  2.         SeqList list = new MyArray(4);
  3.         list.add(1);
  4.         list.add(9);
  5.         list.add(5);
  6.         list.add(9);
  7.         System.out.println(list.toString());
  8.         list.removeAllValue(9);
  9.         System.out.println(list.toString());
  10.         list.removeAllValue(2);
  11.         System.out.println(list.toString());
  12.     }

三、JDK中动态数组的实现

3.1ArrayList的定义、继承或实现的接口

 RandomAccess：实现了整个接口就具备了随机访问的能力，给一个索引下标可以立即O（1）取得该位置的元素。

Cloneable：可复制的能力。

List：线性表接口。

Seriallizable：序列化接口，ArrayList这个类就可以方便的转为字节数组进行输入输出。

List下关于动态数组的实现有两个子类，ArrayList和Vector都是基于动态数组的实现，ArrayList式异步操作，线程不安全，效率高。Vector是同步操作（对整个数组进行加锁操作）线程安全，效率比较低。

3.2ArrayList的具体常见使用

3.2.1构造方法

ArrayList()
          构造一个初始容量为 10 的空列表。
ArrayList(Collection<? extends E> c)
          构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
ArrayList(int initialCapacity)
          构造一个具有指定初始容量的空列表。

 前两种构造方法都没有传入数值，l3传入了数值，但是也产生了新的对象，改变l3，link不会发生改变。

  1.     public static void main(String[] args) {
  2.         List<Integer> l1 = new ArrayList<>();
  3.         List<Integer> l2 = new ArrayList<>(5);
  4.         List<Integer> link = new LinkedList<>();
  5.         link.add(1);
  6.         link.add(3);
  7.         link.add(5);
  8.         List<Integer> l3 = new ArrayList<>(link);
  9.         System.out.println(l1);
  10.         System.out.println(l2);
  11.         System.out.println(l3);
  12.     }

3.2.2常用操作方法

（1）添加

 booleanadd(E e)
          将指定的元素添加到此列表的尾部。
 voidadd(int index, E element)
          将指定的元素插入此列表中的指定位置。
 booleanaddAll(Collection<? extends E> c)
          按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。

在第三个方法中将link的所有元素添加到l1的尾部，但是对l1进行操作，并不会影响到list。 

  1.     public static void main(String[] args) {
  2.         List<Integer> l1 = new ArrayList<>();
  3.         // 尾插
  4.         l1.add(1);
  5.         l1.add(3);
  6.         l1.add(5);
  7.         l1.add(1,10);
  8.         List<Integer> link = new LinkedList<>();
  9.         link.add(2);
  10.         link.add(4);
  11.         link.add(6);
  12.         l1.addAll(link);
  13.         System.out.println(l1);
  14.     }

（2）删除

 Eremove(int index)
          移除此列表中指定位置上的元素。
 booleanremove(Object o)
          移除此列表中首次出现的指定元素（如果存在）。
 voidclear()
          移除此列表中的所有元素。

当调用List集合保存的就是整型，调用remove方法默认会调用按照索引删除。

如果想用移除此列表中首次出现的指定元素，需要先获取值对应的索引，然后调用remove。

而clear清空则调用了就把集合中所有元素都删除。

  1.     public static void main(String[] args) {
  2.         List<Integer> l1 = new ArrayList<>();
  3.         l1.add(1);
  4.         l1.add(3);
  5.         l1.add(5);
  6.         l1.add(7);
  7.         System.out.println(l1.remove(1));
  8.         System.out.println(l1);
  9.         System.out.println(l1.remove(l1.indexOf(7)));
  10.         System.out.println(l1);
  11.         l1.clear();
  12.         System.out.println(l1);
  13.     }

 （3）截取

 List<E>subList(int fromindex, int toIndex)
          截取部分list。

截取的区间是左闭右开的，并且截取是产生新的集合，并不影响被截取的原集合。 

  1.     public static void main(String[] args) {
  2.         List<Integer> l1 = new ArrayList<>();
  3.         l1.add(1);
  4.         l1.add(3);
  5.         l1.add(5);
  6.         l1.add(7);
  7.         System.out.println(l1);
  8.         List<Integer> ret = l1.subList(1,3);
  9.         System.out.println(ret);
  10.         System.out.println(l1);
  11.     }

 （4）指定元素有关的方法。

 booleancontains(Object o)
          如果此列表中包含指定的元素，则返回 true。
 Eget(int index)
          返回此列表中指定位置上的元素。
 intindexOf(Object o)
          返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。
 intlastIndexOf(Object o)
          返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 -1。
 Eset(int index, E element)
          用指定的元素替代此列表中指定位置上的元素。
  1.      public static void main(String[] args) {
  2.         List<Integer> l1 = new ArrayList<>();
  3.         l1.add(1);
  4.         l1.add(3);
  5.         l1.add(5);
  6.         l1.add(7);
  7.         l1.add(7);
  8.         System.out.println(l1.contains(7));
  9.         System.out.println(l1.get(2));
  10.         System.out.println(l1.indexOf(3));
  11.         System.out.println(l1.lastIndexOf(7));
  12.         System.out.println(l1.set(2,9));
  13.         System.out.println(l1);
  14.     }

 3.2.3 ArrayList的三种遍历方式

什么是遍历：就是按照一定的规则将集合中的所有元素全部访问一遍，做到不重复，不遗漏。

（1）普通for循环+get方法进行遍历。

（2）for-each循环（lterable接口的子类都可使用for-each循环）。

（3）使用集合的迭代器。

迭代器是专门为了遍历一个集合产生的，对于List集合的子类，有一个接口；terator接口，从前向后遍历，hasNext()=> 判断集合是否还有元素没有遍历，next()=> 取出当前要遍历的元素。

  1.     public static void main(String[] args) {
  2.         List<Integer> list = new ArrayList<>();
  3.         list.add(1);
  4.         list.add(3);
  5.         list.add(5);
  6.         list.add(7);
  7.         for (int i = 0; i < l1.size(); i++) {
  8.             System.out.print(l1.get(i)+" ");
  9.         }
  10.         System.out.println();
  11.         for (int i :l1) {
  12.             System.out.print(i+" ");
  13.         }
  14.         System.out.println();
  15.         Iterator<Integer> iterator = list.listIterator();
  16.         while (iterator.hasNext()) {
  17.             System.out.print(iterator.next() + " ");
  18.         }
  19.     }

 这三种遍历方式，如果只是普通遍历的话，不牵扯到集合内容的修改时，用哪一种都行。但是在遍历的过程中，修改了集合的内容需要使用的迭代器方式。

  1.     public static void main(String[] args) {
  2.         List<Integer> list = new ArrayList<>();
  3.         list.add(1);
  4.         list.add(3);
  5.         list.add(5);
  6.         list.add(7);
  7.         for (int i :list) {
  8.             System.out.print(i+" ");
  9.         }
  10.         System.out.println();
  11.     }

 如果没有使用迭代器就会报错，这个错误叫集合的并发修改异常。假设这个集合是由多个用户同时访问的，其中一个用户修改了集合的内容，那么其他用户就看看到不一样的结果。

 以下为采用迭代器的方法。

  1.     public static void main(String[] args) {
  2.         List<Integer> list = new ArrayList<>();
  3.         list.add(1);
  4.         list.add(3);
  5.         list.add(5);
  6.         list.add(7);
  7.         Iterator<Integer> iterator = list.listIterator();
  8.         while (iterator.hasNext()) {
  9.             int num = iterator.next();
  10.             if (num == 3) {
  11.                 iterator.remove();
  12.             }
  13.             System.out.println(iterator.next());
  14.         }

3.3分析JDK中ArrayList

3.3.1 无参构造

ArrayList的无参构造并没有初始化elementData。只有在第一次add时才会真正将数组进行实例化。是懒加载。懒加载就是产生对象时，内部保存的元素的集合并不初始化，只有在第一次真正添加元素之前在进行内部空间的初始化，尽可能的避免空间浪费。

 Vector的无参构造就默认初始化了长度为10的Object数组。

 3.3.2添加以及扩容机制

ArrayList中size是有效元素个数，默认为零。在add方法中首先要判断size加一判断是否越界，确保空间够用再进行尾插操作。

 若此时data为空，返回默认长度10和size+1的最大值，若数组不为空直接返回size+1整个长度，也就是说如果数组还没有初始化，第一次调用add时，就将数组长度赋值为10。

 当前有效元素的个数首先要+1，然后和data的长度进行比较，在添加元素之前先扩容。

 在grow中也是将新数组长度变为1.5倍。第一个if循环中如果data还没初始化，newCap为默认长度10，同时还有一种情况，当data长度已经接近整形最大值还要翻倍处理，只要新增一个长度元素即可。

 而Vector的grow方法前面不太一样，capacityIncrement为自定义扩容参数，并且扩容为原数组的两倍。

 3.4ArrayList的特点

动态数组仍然是数组，因此支持随机访问的能力，在O(1)时间内根据索引取得对应索引的元素。

不能简单的说，动态数组的插入和删除效率较低，只有在数组的任意位置的插入和删除（尤其是数组头部）需要进行元素的搬移。默认的尾插其实效率特别高，甚至比链表还快。

扩容需要开辟新的空间，旧的空间需要JVM来进行垃圾回收，此时需要频繁添加数据频繁导致扩容触发，空间的申请和释放都是不小的性能消耗。因此在频繁的进行元素插入和删除时，考虑用链表进行。

一般的扩容都是扩容为原数组的1.5倍或者两倍，假设当前元素100个，为了多放一个元素需要多申请50个或者100个单位，会造成空间的浪费。

所以若需要频繁进行元素的插入和删除，此时选择链表最优，若需要频繁按照索引查询元素，使用数组更优。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/117860
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号