数组
什么是数组?
数组就是把数据码成一排进行寄存
须要留神的是数组的索引是从0开始
应用Java中的数组
public static void main(String[] args) {
//定义数组以及长度为10
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
arr[i] = i;
}
//定义数组以及数据
int[] scores = new int[]{100, 99, 98};
//批改第0个值为10
scores[0] = 10;
for (int score : scores) {
System.out.println(score);
}
}
封装属于咱们的数组
- 数组最大的长处:疾速查问。 scores[2]
- 数组最好利用于”索引有语意”的状况。
- 然而并非所有有语意的索引都实用于数组
- 例如:身份证号,如果想用身份证号来当索引的话,咱们要开拓一个很大的空间。
索引没有语意的状况下,如何示意没有元素?
如何增加元素?如何删除元素?
基于Java的数组,二次封装属于咱们本人的数组类。
public class Array {
private int[] data;
private int size;
//无参数的构造函数,默认的数组容量大小为10
public Array() {
this(10);
}
//构造函数,传入数组的容量capacity结构Array
public Array(int capacity) {
data = new int[capacity];
size = 0;
}
//获取数组中的元素个数
public int getSize() {
return size;
}
//获取数组的容量
public int getCapacity() {
return data.length;
}
public boolean isEmpty() {
return size == 0;
}
}
向数组中增加元素
一开始,数组的size是0,如果咱们想增加值为66,数据将会寄存在索引为0的地位,而后size进行自增。
public void addLast(int e){
if(size >= data.length){
throw new ArrayIndexOutOfBoundsException("AddLast failed. Array is full");
}
data[size] = e;
size ++;
}
然而,如果咱们想在指定地位插入数据呢?
如果咱们要把77插入到如图索引为1的地位,咱们首先须要将100往后挪一位,而后将99、88顺次后挪一位,而后腾出地位给77进行插入。插入之后不要遗记将size自增
public void addLast(int e) {
add(size, e);
}
public void addFirst(int e) {
add(0, e);
}
public void add(int index, int e) {
if (size >= data.length) {
throw new ArrayIndexOutOfBoundsException("add failed. Array is full.");
}
if (index < 0 || index > size) {
throw new IllegalArgumentException("add failed. Require index >= 0 and index <= size.");
}
//将大于index的元素都进行索引加一
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
顺便咱们重写一下toString办法,测试一下咱们的Array类。
@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();
}
public static void main(String[] args) {
Array array = new Array(20);
for (int i = 0; i < 10; i++) {
array.addLast(i);
}
array.addLast(15);
array.addFirst(17);
array.add(5,18);
System.out.println(array);
}
Array: size = 13 , capacity = 20[17, 0, 1, 2, 3, 18, 4, 5, 6, 7, 8, 9, 15]
查问元素和批改元素
//获取index索引地位的元素
public int get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get failed. Require index >= 0 and index < size.");
}
return data[index];
}
//批改index索引地位的元素
public void set(int index, int e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("set failed. Require index >= 0 and index < size.");
}
data[index] = e;
}
蕴含,搜寻和删除
//查找数组中是否有元素e
public boolean contains(int e){
for (int i = 0; i < size; i++) {
if (data[i]== e){
return true;
}
}
return false;
}
//查找数组中元素e所在的索引,如果不存在元素e,则返回-1
public int find(int e){
for (int i = 0; i < size; i++) {
if (data[i]== e){
return i;
}
}
return -1;
}
如果咱们想删除指定地位的元素,咱们须要将大于指定地位的索引全副顺次往前挪一位。
当数据挪完当前呢,咱们不须要删除索引为4的数据,只须要将索引减一指向4即可。
因为用户是永远看不到size的值是多少,只能查问到size – 1的值。
//从数组中删除index地位的元素,并返回删除的元素
public int remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove failed. Require index >= 0 and index < size.");
}
int ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size --;
return ret;
}
//从数组中删除最初一个元素,并返回删除的元素
public int removeLast() {
return remove(size -1);
}
//从数组中删除第一个元素,并返回删除的元素
public int removeFirst() {
return remove(0);
}
//从数组中删除元素e
public void removeElement(int e) {
int index = find(e);
if (index != -1){
remove(index);
}
}
目前为止,咱们这个Array只能承载int类型,咱们不可能为每个类型创立一个数组类,所以咱们要应用泛型来解决此问题。
应用泛型
这里我就间接放出替换好的Array类
public class Array<E> {
private E[] data;
private int size;
//无参数的构造函数,默认的数组容量大小为10
public Array() {
this(10);
}
//构造函数,传入数组的容量capacity结构Array
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
//获取数组中的元素个数
public int getSize() {
return size;
}
//获取数组的容量
public int getCapacity() {
return data.length;
}
public boolean isEmpty() {
return size == 0;
}
public void addLast(E e) {
add(size, e);
}
public void addFirst(E e) {
add(0, e);
}
public void add(int index, E e) {
if (size >= data.length) {
throw new ArrayIndexOutOfBoundsException("add failed. Array is full.");
}
if (index < 0 || index > size) {
throw new IllegalArgumentException("add failed. Require index >= 0 and index <= size.");
}
//将大于index的元素都进行索引加一
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
//获取index索引地位的元素
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get failed. Require index >= 0 and index < size.");
}
return data[index];
}
//批改index索引地位的元素
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("set failed. Require index >= 0 and index < size.");
}
data[index] = e;
}
//查找数组中是否有元素e
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i] == e) {
return true;
}
}
return false;
}
//查找数组中元素e所在的索引,如果不存在元素e,则返回-1
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i] == e) {
return i;
}
}
return -1;
}
//从数组中删除index地位的元素,并返回删除的元素
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove 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;
return ret;
}
//从数组中删除最初一个元素,并返回删除的元素
public E removeLast() {
return remove(size -1);
}
//从数组中删除第一个元素,并返回删除的元素
public E removeFirst() {
return remove(0);
}
//从数组中删除元素e
public void removeElement(E e) {
int index = find(e);
if (index != -1){
remove(index);
}
}
@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();
}
}
而后咱们进行一下测试
public static void main(String[] args) {
Array<String> arr = new Array<>(10);
arr.addLast("张三");
arr.addLast("李四");
arr.addLast("王五");
System.out.println(arr);
}
Array: size = 3 , capacity = 10[张三, 李四, 王五]
这样咱们就能够很轻易的实现了不同对象的数组。
动静数组
当初咱们的数组还是一个无限的固定的容量,如果预估容量过大,会导致节约很多空间,如果预估容量过小,则会呈现不够用,所以咱们须要应用可伸缩的动静数组。
如果以后数组曾经满了,那咱们就开拓一个新的数组,而后将data的数组进行循环拷贝过来,而后将data指向新的数组。
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);
}
//将大于index的元素都进行索引加一
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i]= data[i];
}
data = newData;
}
相应的,如果数组缩减到肯定水平,咱们也要将数组进行缩容。
//从数组中删除index地位的元素,并返回删除的元素
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove 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;
//缩容
if (size == data.length / 2 && data.length / 2 != 0){
resize(data.length / 2);
}
return ret;
}
简略工夫复杂度剖析
-
增加操作
- addLast(e)
O(1)
- addFirst(e)
O(n)
- add(index,e)
O(n/2) = O(n)
- addLast(e)
-
删除操作
- removeLast(e)
O(1)
- removeFirst(e)
O(n)
- remove(index,e)
O(n/2) = O(n)
- removeLast(e)
-
批改操作
- set(index,e)
O(1)
- set(index,e)
-
查找操作
- get(index)
O(1)
- contains(e)
O(n)
- find(e)
O(n)
- get(index)
发表回复