数组
什么是数组？
数组就是把数据码成一排进行寄存
须要留神的是数组的索引是从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)