bitfishxyz
commented
5 years ago Java实现
Java中就是原生数组，我们就以Java语言为例，来测试下上面的步骤
这是我们数组
String[] arr = new String[3];
arr[0] = "a";
arr[1] = "b";
arr[2] = "c";现在我们想把索引为1的元素的值设置为"d"，我们该怎么做呢？
很简单，利用数组的随机访问原理，我们可以直接修改
// 修改元素
arr[1] = "d";如果我们想删除索引为2的元素，我们该怎么办呢？ 显然，数组的创建，它的大小不能再修改，我们只能重新创建一个数组
// 删除索引为2的元素
String[] arr2 = new String[arr.length - 1];
arr2[0] = arr[0];
arr2[1] = arr[1];这样就行了。我们要创建一个新的数组，然后把原来数组的其他元素复制到新的数组中， 那么我们就是删除了原来的数组了。 现在我们可以把arr2看做是arr删除了一个元素后的新状态。
同理，如果我们想在索引为0的位置添加一个新的元素，我们可以
// 在索引为0的位置添加一个元素e
String[] arr3 = new String[arr2.length + 1];
arr3[0] = "e";
arr3[1] = arr2[0];
arr3[2] = arr2[1];长度为3的，如果想对它进行增删给查旧的按照我们执勤啊说的步骤， 所以我们可以写一个包装类，来包装上面的操作。
不过我们可以卡看到，Java的原生数组太底层了，用的时候不方便， 所以我们可以写一个包装类，来方便我们增删改查
通过Array类来包装
import lombok.Getter;
import lombok.ToString;
@ToString
public class Array<E> {
private static int increaseCapacityTimes = 2;
/**
* 实际的容量
*/
@Getter
private int size;
/**
* 底层数组
*/
private E[] data;
public Array(int capacity){
data = (E[])new Object[capacity];
}
public Array(){
this(10);
}
/**
* 底层数组的最大容量
*/
public int getCapacity(){
return data.length;
}
public boolean isEmpty(){
return size == 0;
}
/**
* 添加底层数组容量
*/
private void increaseCapacity(){
E[] newData = (E[])new Object[data.length * increaseCapacityTimes];
for (int i = 0; i < data.length; i++) {
newData[i] = data[i];
}
data = newData;
}
/**
* 降低底层数组容量
*/
private void decreaseCapacity(){
E[] newData = (E[])new Object[data.length / 2 + 1];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
/**
* 修改数组的容量
*/
private void resize(){
if (size == data.length){
increaseCapacity();
}
if (size <= data.length / 3 && data.length > 20){
decreaseCapacity();
}
}
/**
* 假设数组为 [11, 22, 33, 44]
* insert(99, 2)后，数组变为
* [11, 22, 99, 33, 44]
* 原始数组索引为[2, length)都要向后移动
* 新插入原始的索引为2
* @param e
* @param index: 可以取到size
*/
public void insert(E e, int index){
resize();
if (index > size || index < 0) {
throw new IllegalArgumentException("索引应该在[0, size]之间");
}
for (int i = size; i > index; i--) {
data[i] = data[i-1];
}
data[index] = e;
size++;
}
public void addLast(E e){
insert(e, size);
}
public void addFirst(E e){
insert(e, 0);
}
public boolean contains(E e){
for (int i = 0; i < size; i++) {
if (data[i].equals(e)){
return true;
}
}
return false;
}
/**
* 寻找当前元素的位置，如果不存在就返回-1
* @param e
* @return
*/
public int indexOf(E e){
for (int i = 0; i < size; i++) {
if (data[i].equals(e)){
return i;
}
}
return -1;
}
/**
* 删除指定索引位置的元素，并将这个元素的值返回
* @param index
* @return
*
* data[size]这个位置的值还在，但是没有关系的
*/
public E remove(int index){
assertIndex(index);
resize();
E currentValue = data[index];
for (int i = index; i < size - 1 ; i++) {
data[i] = data[i + 1];
}
size--;
// 释放资源
data[size] = null;
return currentValue;
}
public E removeLast(){
return remove(size - 1);
}
public E removeFirst(){
return remove(0);
}
public boolean removeElement(E e){
int index = indexOf(e);
if (index != -1) {
remove(index);
return true;
}
return false;
}
/**
* 获得底层数组索引为index的位置的元素
* @param index
* @return
*/
public E get(int index){
assertIndex(index);
return data[index];
}
public E getLast(){
return get(size - 1);
}
public E getFirst(){
return get(0);
}
public void set(E e, int index){
assertIndex(index);
data[index] = e;
}
private void assertIndex(int index){
if (index >= size || index < 0) {
throw new IllegalArgumentException("索引应该在[0, size)之间");
}
}
}
数组
我是学习Python和JS入门编程的，在学习数据结构的阶段，就在掉到坑里了。原因之一就是我很难理解数组这种数据结构。
在Python中的List或者JS中的Array，它们其实是一个非常复杂包装类，隐藏了真正的数组的特征，让我对数组这种结构产生了很多误解。
导致我在小白的时候一直有疑问：
好吧，现在看来这些想法有点可笑，为了避免有些同学有和我一样的误区，我们整理了数组这个结构的几个特点。
一个数组占用内存是连续的
这点很好理解，作为一种线性的数据结构，它需要占用连续的内存
数组中每个元素应该占用同样长度的内存
其实在C、Java这种偏底层的静态编程语言中，都是要求数组中的每个元素是同一个类型的。为什么有这样要求？
这是为了数组的随机访问。
假设一个数组中每个元素都是占用8个字节的内存，其中第一个元素在内存中的起始地址是
0000 aaaa，那么请问这个数组中第7个元素的内存起始地址是多少？很简单，应该是
0000 aaaa向后数56个字节， 是这个地址0000 aae2，就是这么简单。然是如果如果数组中允许每个元素占用不同大小的内存，会反生什么情况呢？ 但是你是我们就无法做到随机访问了。
这个有一个推论，一致第一个元素的第一，和某一元素的索引，就可以推断出 它的地址。
CPU访问内存中每个地址消耗的时间相同
这就是由计算机的构造原理决定了，访问
@0000 0000和@ffff ffff消耗的时间一样。 具体的原理我也不是很清楚，反正就是什么总线啊什么乱七八糟的概念。但是结论很很重要。这个就是说，我们访问数组中第一个元素和最后一个元素消耗的时间是一样。。。。
结合上面一点，我们就是说数组支持随机访问。
数组容量固定
一但创建了一个数组，它的容量就确定了。 [1, 2, 3], 那么它在内存中就是占用12个字节。不能变化。
如果我想删除2这个元素，怎么把？ 不能使不能直接删除，然后变成[1, 3]这样的，但是我们有三种办法
只有这三种方法。
小节
上面就是对数组这种数据结构的理解。然后就是学习数据结构的时候 建议使用C Java，不建议使用JS，Python