数组 Array
1 数组基础
-
数据类型一致
-
为什么数组只能存储一种类型的数据？
每种数据类型所占空间大小不同，比如char占两个字节，int占4个字节，如果数组里面存了多种数据类型，那就不方便根据索引去计算地址偏移量了，实现不了
Random Access[1]。如果你存放了多种该数据类型，那么你必须用其他的数据结构去记录哪个位置是什么类型，比如你数组的第一位放了一个
byte,如果你不记录，当你取用的时候，你怎么知道他是byte类型呢，而不是char呢。所以说只存一种数据简单纯粹。-
特例：存储不同类型的数据
Object[] arr = new Object[3]; arr[0] = 1; arr[1] = "aa"; arr[2] = true;
-
-
数组是对象
- string[] s = {"1","2","3"};中存在4个对象，数组s也是一个对象
- int[] arr = {1,2,3};中存在1个对象，因为基本数据类型不是对象
-
索引
索引是从0开始的
-
索引可以有语意（比如索引代表学号，元素是分数）
也可以无语意
并非所有有语意的索引都适用于数组（身份证号不能为索引，浪费太多空间）
-
优点：
1、按照索引查询元素速度快 时间复杂度O(1)
2、能存储大量数据
3、按照索引遍历数组方便 时间复杂度O(1)缺点：
1、根据内容查找元素速度慢 时间复杂度O(n)
2、数组的大小一经确定不能改变。
3、数组只能存储一种类型的数据
4、增加、删除元素效率慢 时间复杂度O(n)
5、未封装任何方法，所有操作都需要用户自己定义。
-
随机访问是说你可以随意访问该数据结构中的任意一个节点，假设该数据结构有10个节点，你可以随意访问第1个到第10个节点。 +对于链表而言，如果其存在10个节点，如果你要访问第5个节点，你只能从列表的头或者尾，依次遍历相邻的每一个节点；对于vector而言，你可以直接利用[]操作符，直接访问[4]，不需要遍历其他的节点，这就是随机访问。 +*比如first是第一个元素的地址，现在想访问第N个元素。 随机访问：直接first+N，便可以得到第N个元素的地址，因为这些相邻元素是按顺序连续存储的。 **+比如普通数组就是可随机访问的。而链表不支持随机访问，链表存储的元素，它们的存储地址也不是连续的，是随机的。 要想访问第N个元素，只能从second = first->next遍历第2个元素，然后再three = first->next遍历第3个元素… 这样一直到第N个元素。所以这样的访问速度就没有随机访问快。
2 基于java的数组，二次封装我们自己的数组类（增删改查）
-
使用泛型
让我们的数据结构可以放置“任何”数据类型
-
不可以是基本数据类型，只能是类对象，可以使用包装类
基本数据类型 包装类 boolean Boolean char Character byte Byte short Short int Integer long Long float Float double Double
-
数组类中的变量语意
- E[] data 代表该数组
- int capacity 容量：该数组
最多可以存储多少元素(可以用data.length表示) - int size 索引：数据中
实际有多少元素- 数组中没有元素时，size为0，可表示为索引
public class Array<E> {
private E[] data;
private int size;
//获取数组的大小
public int getCapacity(){return data.length; }
//构造函数，传入数组容量capacity 构造Array
public Array(int capacity){
data = (E[])new Object[capacity];
size = 0;
}
//无参构造函数，默认数组容量是10
public Array(){ this(10);}
//获取数组中的元素个数
public int getSize(){ return size; }
public boolean isEmpty(){ return size==0; }
...
-
向数组中添加元素
//向所有元素后添加一个新元素 public void addLast(E e){ add(size,e); } //向数组开始处添加一个新元素 public void addFirst(E e){ add(0,e); } //在第index个位置插入一个新元素e public void add(int index,E e){ if(index < 0 || index > size) throw new IllegalArgumentException("Add failed . Require index>=0 and index <=size"); if(size == data.length) resize(2*data.length);//resize解析在文章之后，为扩容操作 for(int i= size-1; i>= index; i--){ data[i+1] = data[i];//将index之后元素向后移一位，index位置依然包含原来的元素 } data[index] = e; size++; }- 在数组后添加一个元素
在第index个位置插入一个新元素e
-
在数组中查询元素和修改元素
重写toString
@Override public String toString(){ StringBuilder res = new StringBuilder(); res.append(String.format("Array:size= %d , capacity = %d\n",size,data.length)); res.append('['); for (int i = 0; i < size; i++) { res.append(data[i]); if(i != size -1) res.append(","); } res.append(']'); return res.toString(); }-
获取index索引位置的元素 O（1）
//获取index索引位置的元素（隐藏data），通过get可以防止用户访问data中的空位置 public E get(int index){ if(index < 0 || index > size) throw new IllegalArgumentException("Add failed . Index is illegal."); return data[index]; }
-
更新index位置的元素 O（1）
//修改index索引位置的元素为e void set(int index,E e){ if(index < 0 || index > size) throw new IllegalArgumentException("Add failed . Index is illegal."); data[index] = e; } -
包含，搜索和删除
-
包含
//查找数组中是否有元素为e public boolean contains(E e){ for (int i = 0; i < size; i++) { if (data[i].equals(e)) return true; } return false; } -
搜索
//查找数组中元素e所在的索引，如果不存在元素e,则返回 -1 public int find(E e){ for (int i = 0; i < size; i++) { if (data[i].equals(e)) return i; } return -1; } -
删除
//从数组中删除index位置的元素，返回删除的元素 public E remove(int index){ if(index < 0 || index > size) throw new IllegalArgumentException("Add failed . Require index>=0 and index <=size"); E ret = data[index]; for(int i= index+1; i< size; i++){ data[i-1] = data[i]; } size--; data[size] = null; //loitering objects 闲逛的对象 ！= memeory leak 内存泄漏 if(size == data.length/4 && data.length/2 != 0) resize(data.length/2); return ret; } public E removeFirst(){return remove(0);} public E removeLast() { return remove(size-1);} //从数组中删除元素e public void removeElement(E e){ int index = find(e); if(index != -1){ remove(index); } }
-
3 动态数组
-
扩容（ArrayList扩容为1.5倍）
//自动扩容 private void resize(int newCapacity){ E[] newData = (E[])new Object[newCapacity]; for(int i= 0;i < size; i++){ newData[i] = data[i]; } data = newData; }
4 简单的时间复杂度分析
从中分析可知，数组不适合增删操作
-
均摊复杂度(amortized time complexity)
- resize的复杂度分析（基于addLast（O(1)复杂度）方法）
平均，每次addLast操作，平均进行2次基本操作
假设capacity = n, n+1次addLast,触发resize,总共进行2n+1次基本操作
平均，每次addLast操作，平均进行2次基本操作
这样均摊，时间复杂度是O(1)的
同理，removeLast操作，均摊复杂度也为O(1)
-
复杂度震荡
-
问题：当我们addLast操作和removeLast操作交替运行时，某些时候可能O(n)
1、此时capacity=n,数组为满状态，进行addLast操作，需要进行一次resize操作(此时扩容为2n)
此时addLast O(n) 容量为2n
2、接下来,数组中有n+1个元素，数组容量为2n，此时进行一次removeLast操作会触发一次resize操作（此时缩容为n）
此时removeLast O(n) 容量为n
3、不断交替运行。。。。。
-
-出现问题的原因：removeLast时resize过于着急（Eager(激进)）
-解决方案：Lazy
当size==capacity/4时，才将capacity减半
//从数组中删除index位置的元素，返回删除的元素
public E remove(int index){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed . Require index>=0 and index <=size");
E ret = data[index];
for(int i= index+1; i< size; i++){
data[i-1] = data[i];
}
size--;
data[size] = null; //loitering objects 闲逛的对象 ！= memeory leak 内存泄漏
if(size == data.length/4 && data.length/2 != 0)//data.length==1(容量)时/2==0
resize(data.length/2);
return ret;
}
此文章为学习《玩转数据结构》所总结，如有问题望请指正
尊重版权，这里贴一个此课程链接https://coding.imooc.com/class/207.html
-
随机访问是说你可以随意访问该数据结构中的任意一个节点，假设该数据结构有10个节点，你可以随意访问第1个到第10个节点。 +对于链表而言，如果其存在10个节点，如果你要访问第5个节点，你只能从列表的头或者尾，依次遍历相邻的每一个节点；对于vector而言，你可以直接利用[]操作符，直接访问[4]，不需要遍历其他的节点，这就是随机访问。 +*比如first是第一个元素的地址，现在想访问第N个元素。 随机访问：直接first+N，便可以得到第N个元素的地址，因为这些相邻元素是按顺序连续存储的。 **+比如普通数组就是可随机访问的。而链表不支持随机访问，链表存储的元素，它们的存储地址也不是连续的，是随机的。 要想访问第N个元素，只能从second = first->next遍历第2个元素，然后再three = first->next遍历第3个元素… 这样一直到第N个元素。所以这样的访问速度就没有随机访问快。 ↩
