关于java:cs61b-week3The-AList

前言:

之前咱们实现了双端队列，这是一种比拟完满的数据结构，在两端进行插入和删除都十分迅速，然而，当咱们须要拜访队列中的第 i 项时，总是须要从哨兵结点开始，先遍历前 i - 1 项，能力找到第 i 项，最坏的状况是 i 位于两头，此时咱们须要遍历链表长度 n 的一半 n /2，假如 n 十分大时，工夫的消耗就会比拟大(O(n) )，思考到数组能够间接拜访下标的个性，实现第 i 项的查找简直是 O(1)，因而本次课决定应用数组实现 List

1.AList 的抽象数据类型

首先建设 class AList，成员别离是一个int 数组和长度size，构造函数初始化，先调配一个长度为 100，各项均为 0 的数组item，因为最开始咱们并未增加任何元素，因而size = 0

public class AList {private int[] items;    
    private int size;

public AList() {items = new int[100];
    size = 0;
  }
}

与后面的 Deque 雷同，对于 AList，有如下操作:

• addLast(): 开端增加数据
• removeLast(): 删除并返回开端数据
• get(): 返回第 i 项数据
• getLast(): 获取数组最初一项元素数据
• size(): 返回 List 的长度

通过观察，咱们能够发现数组领有以下不变量:

• 在数组开端增加下一项元素的地位 (下标) 总是size
• size总是数组的长度
• 数组最初一项的下标总是size – 1(因为数组的 index 是从 0 开始的)

因而咱们能够写出上述数据操作了:

 // 数组开端增加元素
  public void addLast(int x) {items[size] = x;
    size += 1;
  }
 
 // 获取数组最初一项元素
  public int getLast() {return items[size - 1];
  }
 
 // 查问第 i 项
  public int get(int i) {return items[i];
  }

 // 查问数组长度
  public int size() {return size;}

 // 删除开端项
 public int removeLast(){int x = items[size-1];
    size = size - 1;
    return x;
  }

2.Resizing Array

最开始的时候咱们定义的 item 数组大小默认是 100，假如当初须要增加第 101 个数据 11，数组以后的容量显然是不够的，此时须要咱们从新调整数组的大小，也就是 resizing Array。咱们先思考最简略的形式，也就是应用 System.arraycopy():

int[] a = new int[size + 1];
System.arraycopy(items, 0, a, 0, size);
a[size] = 11;
items = a;
size = size + 1;

咱们从新申明了一个新数组 a, 比原数组item 长 1 位，并把原数组 item 的值 copy 到 a 中，把 a 最初一位用来寄存新数据，由此解决数组容量不够的问题。之后还能够写成一个专用的函数 resize() 来操作开拓与复制数组:

private void resize(int capacity) {int[] a = new int[capacity];
  System.arraycopy(items, 0, a, 0, size);
  items = a;
}
 
public void addLast(int x) {if (size == items.length) {resize(size + 1);
  }
  items[size] = x;
  size += 1;
}

3. 剖析 Resizing Array 的工夫复杂度

回忆以下咱们之前的 SLList，往队尾增加一个元素的工夫复杂度是 O(1)，那么对于AList 来说，与 SLList 相比工夫复杂度如何呢？
考虑一下，如果此时原数组大小是 100，向其中新增一个数据，那么 addLast() 须要做的是:

1. 新申明一个数组，大小为 101，并拷贝原数组的 100 个元素
2. 增加新增元素至 101

操作总共须要 201 个内存空间
如果新增两个元素呢？依照下面的步骤，总共须要 101+102 = 203 个空间，新增 1000 个，须要101+102+103+……+1000 = 495450 约 50w 个空间，可见内存空间耗费很大

在 Linux 下，能够在运行命令 java filename 前加一个 time，从而取得程序的运行工夫
以下是 SLList 与AList的开端插入新元素对比图：

因为前者每次在开端增加元素的工夫复杂度是 O(1), 常数阶，总的操作工夫的累加即常数的积分: 一次函数，是一条直线
对于后者，每次的拷贝操作是从 0 开始将原数组全副元素拷贝至新数组，拷贝操作工夫复杂度是 O(n)，总的拷贝次数的累加即 n 的积分，也就是抛物线

4. 优化 Resizing Array

工夫复杂度优化

将每次 size+1 改成size•refactor, 也就是每次数组大小的裁减从加一个数变成乘以某个数，从而化为 Geometric Resizing，能够大幅升高工夫复杂度

public void addLast(int x) {if (size == items.length) {resize(size * RFACTOR);
  }
  items[size] = x;
  size += 1;
}

空间内存优化

如果咱们有一个大小为 100000 的数组，当我删除其 99999 项后，原数组只剩下 1 项。事实上，删除操作只是将 size 一直左移，原来数组所占的内存空间依然存在，在这种状况下残余内存大量节约。思考引入usage ratio, 定义为

“usage ratio”R = size / items.length

如果 R <0.25，则将数组长度减半

5. 泛型数组

正如咱们之前对 SLList 所做的，咱们能够批改 AList 以便它能够保留任何数据类型，而不仅仅是整数, 例如，应用 ElemType 作为泛型参数
在此之前须要留神的一点是Java 不容许咱们创立泛型对象数组, 也就是说不能这样写:

Elemtype[] items = new Elemtype[8];

相同，咱们应该这样写:

Elemtype[] items = (Elemtype []) new Object[8];

只管编译器会产生正告，当前解释 …

最初是一点优化，后面咱们写 removeLast() 的时候，只应用了

size = size-1;

开端的元素值在数组中依然存在，只是被咱们漠视了，当数组较大时，这将造成内存节约，因而在执行 size = size-1 之前，将原来的开端元素值赋值为null，让垃圾回收器将其回收，avoid “loitering”

  items[size - 1] = null;
  size -= 1;