02_动态数组
2020-09-14 本文已影响0人
伶俐ll
什么是数据结构？
数据结构是计算机存储、组织数据的方式
Snip20200914_5.png
数组
数组是一种顺序存储的线性表，所有元素的内存地址是连续的
数组的接口设计
int size(){} // 元素的数量boolean isEmpty(){} // 是否为空void add(E element){} // 添加元素到最后面void set(int index,E element){} // 设置index位置的元素void add(int index,E element){} // 在index位置插入一个元素void remove(int index){} // 删除index位置的元素boolean contains(E element){} // 是否包含某个元素E get(int index){} // 获取index位置的元素int indexOf(E element){} // 查看元素的索引void clear(){} // 清除所有元素
动态数组的缩容
- 如果内存使用比较紧张，动态数组有比较多的剩余空间，可以考虑进行缩容操作
- 比如剩余空间占总容量一半时，就进行缩容
- 如果扩容倍数、缩容时机设计不得当，有可能会导致复杂度震荡
比如，扩容倍数设置为原来容量的2倍，而缩容时机设置为当元素个数小于等于原容量1/2时 - 注意点：扩容倍数 和 缩容时机 不要相乘等于1
代码实现
- 普通的动态数组
package ListArray;
public class LZArrayList <E>{
/**
* 元素的数量
*/
private int size;
/**
* 所有的元素
*/
private E[] elements;
/**
* 数组的初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 元素找不到
*/
private static final int ELEMENT_NOT_FOUND = -1;
/**
* 构造函数
*/
public LZArrayList(int capaticy){
capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY:capaticy;
elements = (E[]) new Object[capaticy];
}
/**
* 构造函数
*/
public LZArrayList(){
this(DEFAULT_CAPACITY);
}
/**
* 清除所有元素
*/
public void clear(){
for (int i = 0;i<size;i++){
elements[i] = null;
}
size = 0;
}
/**
* 元素的数量
* @return
*/
public int size(){
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 添加元素到尾部
* @param element
*/
public void add(E element){
add(size,element);
}
/**
* 获取index位置的元素
* @param index
* @return
*/
public E get(int index){
rangeCheck(index);
return elements[index];
}
/**
* 设置index位置的元素
* @param index
* @param element
*/
public void set(int index,E element){
rangeCheck(index);
elements[index] = element;
}
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index,E element){
if (index<0 || index>size) {
outOfBounds(index);
}
//扩容
ensureCapacity();
//插入数据
for (int i = size;i>index;i--){
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
/**
* 删除index位置的元素
* @param index
*/
public void remove(int index){
rangeCheck(index);
for (int i = index+1;i<size;i++){
elements[i-1] = elements[i];
}
elements[--size] = null;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element){
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 查看元素的索引
* @param element
* @return
*/
public int indexOf(E element){
if (element == null){
for (int i = 0;i<size;i++){
if (elements[i] == null) return i;
}
}
for (int i = 0;i<size;i++){
if (element.equals(elements[i])) return i;
}
return ELEMENT_NOT_FOUND;
}
/**
* 动态扩容
* 当数组的容量小于size + 1 时，扩容到原来容量的 1.5 倍
*/
private void ensureCapacity(){
int oldCapacity = elements.length;
if (elements.length >= size + 1) return;
int newCapacity = oldCapacity + (oldCapacity>>1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0;i<size;i++){
newElements[i] = elements[i];
}
elements = newElements;
}
/**
* 检查下标越界
* @param index
* @return
*/
private void rangeCheck(int index){
if (index<0 || index >= size){
outOfBounds(index);
}
}
/**
* 检查到下标越界，抛出异常
* @param index
* @return
*/
private void outOfBounds(int index){
throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
}
@Override
public String toString(){
StringBuffer string = new StringBuffer();
string.append("size = ").append(size).append("\n[");
for (int i = 0;i<size;i++){
if (i != 0){
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
}
- 环形动态数组 - 自动缩容
package ListArray;
public class LZCircleArrayList <E>{
/**
* 元素的数量
*/
private int size;
/**
* 所有的元素
*/
private E[] elements;
/**
* 第一个元素的下标
*/
private int front;
private static final int DEFAULT_CAPACITY = 10;
private static final int ELEMENT_NOT_FOUND = -1;
/**
* 构造函数
*/
public LZCircleArrayList(int capaticy){
capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY:capaticy;
elements = (E[]) new Object[capaticy];
}
/**
* 构造函数
*/
public LZCircleArrayList(){
this(DEFAULT_CAPACITY);
}
/**
* 清除所有元素
*/
public void clear(){
for (int i = 0;i<size;i++){
elements[realIndex(i)] = null;
}
front = 0;
size = 0;
shrinkageCapacity();
}
/**
* 元素的数量
* @return
*/
public int size(){
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 添加元素到尾部
* @param element
*/
public void add(E element){
add(size,element);
}
/**
* 获取index位置的元素
* @param index
* @return
*/
public E get(int index){
rangeCheck(index);
return elements[realIndex(index)];
}
/**
* 设置index位置的元素
* @param index
* @param element
*/
public void set(int index,E element){
rangeCheck(index);
elements[realIndex(index)] = element;
}
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index,E element){
if (index<0 || index>size) {
outOfBounds(index);
}
//扩容
ensureCapacity();
//插入数据
if (index>=(size>>1)){ //插入位置更接近数组尾部
for (int i = size;i>index;i--){
elements[realIndex(i)] = elements[realIndex(i - 1)];
}
elements[realIndex(index)] = element;
}else { //插入位置更接近数组头部
for (int i = -1;i<index;i++){
elements[realIndex(i)] = elements[realIndex(i + 1)];
}
elements[realIndex(index)] = element;
front = realIndex(-1);
}
size++;
}
/**
* 删除index位置的元素
* @param index
*/
public void remove(int index){
rangeCheck(index);
//删除数据
if (index>=(size>>1)){ //删除位置更接近数组尾部
for (int i = index+1;i<size;i++){
elements[realIndex(i-1)] = elements[realIndex(i)];
}
elements[realIndex(size-1)] = null;
}else { //删除位置更接近数组头部
for (int i = index;i>0;i--){
elements[realIndex(i)] = elements[realIndex(i - 1)];
}
elements[realIndex(0)] = null;
front = realIndex(1);
}
size--;
//缩容
shrinkageCapacity();
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element){
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 查看元素的索引
* @param element
* @return
*/
public int indexOf(E element){
if (element == null){
for (int i = 0;i<size;i++){
if (elements[realIndex(i)] == null) return i;
}
}
for (int i = 0;i<size;i++){
if (element.equals(elements[realIndex(i)])) return i;
}
return ELEMENT_NOT_FOUND;
}
/**
* 根据index求出真实索引
* @param index
* @return
*/
private int realIndex(int index){
index += front;
if (index<0){
return index + elements.length;
}
return index - (index>= elements.length?elements.length:0);
// return (front + index) % elements.length;
}
/**
* 动态扩容
*/
private void ensureCapacity(){
int oldCapacity = elements.length;
//不需要扩容
if (elements.length >= size + 1) return;
int newCapacity = oldCapacity + (oldCapacity>>1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0;i<size;i++){
newElements[i] = elements[realIndex(i)];
}
elements = newElements;
front = 0;
}
/**
* 动态缩容
* 当元素个数小于数组容量的一半，并且大于默认初始容量时，进行缩容
* 如果数组中没有元素或者数组容量小于初始容量的2倍，缩容为初始容量，否则缩容为容量的1/2
*/
private void shrinkageCapacity(){
int oldCapacity = elements.length;
//不需要缩容
if (size>=(oldCapacity>>1) || oldCapacity<=DEFAULT_CAPACITY) return;
int newCapacity = (oldCapacity < DEFAULT_CAPACITY + DEFAULT_CAPACITY || size == 0)?DEFAULT_CAPACITY:(oldCapacity>>1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0;i<size;i++){
newElements[i] = elements[realIndex(i)];
}
elements = newElements;
front = 0;
}
/**
* 检查下标越界
* @param index
* @return
*/
private void rangeCheck(int index){
if (index<0 || index >= size){
outOfBounds(index);
}
}
/**
* 检查到下标越界，抛出异常
* @param index
* @return
*/
private void outOfBounds(int index){
throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
}
@Override
public String toString(){
StringBuffer string = new StringBuffer();
string.append("front = ").append(front).append("\n");
string.append("size = ").append(size).append("\n[");
for (int i = 0;i<elements.length;i++){
if (i != 0){
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
}
时间复杂度分析
- 添加
最好：O(1) 最坏：O(n) 平均：O(n) - 添加元素到结尾
最好：O(1) 最坏：O(1) 平均：O(1) 均摊：O(1) - 删除
最好：O(1) 最坏：O(n) 平均：O(n) - 设置index位置的值
最好：O(1) 最坏：O(1) 平均：O(1) - 获取inde位置的值
最好：O(1) 最坏：O(1) 平均：O(1)
