01_动态数组
1、什么是数据结构？
-
数据结构是计算机存储、组织数据的方式
线性结构：线性表（数组、链表、栈、队列、哈希表）
树形结构：二叉树、AVL树、红黑树、B树、堆、Trie哈夫曼树、并查集
图形结构：邻接矩阵、邻接表
-
在实际应用中，根据使用场景来选择最合适的数据结构
2、线性表
-
线性表是具有n个相同类型元素的有限序列（n>=0）
- a1是首节点（首元素），an是尾结点（尾元素）
- a1是a2的前驱，a2是a1的后继
-
常见的线性表有
- 数组
- 链表
- 栈
- 队列
- 哈希表（散列表）
3、数组
- 数组是一种顺序存储的线性表，所有元素的内存地址是连续的
int[] array = new int[]{11,22,33};
- 在很多编程语言中，数组都有个致命的缺点（无法动态修改容量）
- 实际开发中，我们更希望数组的容量是可以动态改变的
3.1、动态数组（Dynamic Array）接口设计
◼ int size(); // 元素的数量
◼ boolean isEmpty(); // 是否为空
◼ boolean contains(E element); // 是否包含某个元素
◼ void add(E element); // 添加元素到最后面
◼ E get(int index); // 返回index位置对应的元素
◼ E set(int index, E element); // 设置index位置的元素
◼ void add(int index, E element); // 往index位置添加元素
◼ E remove(int index); // 删除index位置对应的元素
◼ int indexOf(E element); // 查看元素的位置
◼ void clear(); // 清除所有元素
3.2、动态数组的设计
- 在Java中，成员变量会自动初始化，比如
- int类型自动初始化为0
- 对象类型自动初始化为null
3.2.1、添加元素——add(E element)
当size等于0时
当size等于5时
elements[size] = elementl
size++;
3.2.2、打印数组
- 重写toString方法
- 在toString方法中将元素拼接成字符串
- 字符串拼接建议使用StringBuilder
3.2.3、删除元素——remove(int index)
size等于7
index等于3
我们要删除的元素是数组下标为3的元素，即删除44
我们要做的事情就是将后边的数挨个向前移，从index+1处开始
①我们要将55向前移，覆盖44
得到的样式如下：
然后我们要将后一位向前移：
得到如下：
然后将最后一位向前移：
最后得到如下：
最后我们需要做的就是维护size大小，进行size--操作
3.2.4、添加元素——add(int index,E element)
size等于5
index等于2
需要注意的是，我们进行添加元素时，顺序应该是从数组最后面的元素开始，一位一位向后挪动，因为如果我们是从index+1的位置开始挪动的话，前一位元素会将后面位置的值进行覆盖，就会出现线面错误覆盖顺序的图示：
下面是错误的覆盖顺序
3.2.5、如何扩容
3.2.6、泛型
- 使用泛型技术可以让动态数组更加通用，可以存放任何数据类型
public class ArrayList<E>{
private int size;
private E elements;
}
elements = (E[]) Object[capacity];
ArrayList<Integer> list = new ArrayList<>();
3.2.7、对象数组
Object[] objects = new Object[7];
3.2.8、内存管理细节
public void clear(){
for(int i = 0; i < size; i++){
elements[i] = null;
}
size = 0;
}
public E remove(int index){
rangeCheck(index);
E old = elements[index];
for(int i = index + 1; i <= size - 1; i++){
elements[i-1] = elements[i];
}
elements[--size] = null;
return old;
}
3.2.9、null的处理
- 一个内部设计方面的问题
- 是否可以存储null数据？
public int indexOf(E element){
if(element == null){
for (int i = 0; i < size; i++) {
if(elements[i] == null) {
return i;
}
}
}else {
for (int i = 0; i < size; i++) {
if(element.equals(elements[i])) {
return i;
}
}
}
return ELEMENT_NOT_FOUND;
}
最后是代码：
package nuc.edu;
import java.util.Arrays;
/**
* @author 薛东
* @date 2021/3/5 16:43
*/
public class ArrayList<E> {
/**
* 数组的大小
*/
private int size;
/**
* 所有元素
*/
private E[] elements;
public static final int DEFAULT_CAPACITY = 10;
public static final int ELEMENT_NOT_FOUND = -1;
public ArrayList(int capacity){
capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
elements = (E[])new Object[capacity];
}
public ArrayList(){
this(DEFAULT_CAPACITY);
}
/**
* 清除所有元素
*/
public void clear(){
for (int i = 0; i < size; i++) {
elements[i] = null;
}
}
/**
* 元素的数量
* @return
*/
public int size(){
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element){
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 添加元素到尾部
* @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
* @return 原来的元素
*/
public E set(int index, E element){
rangeCheck(index);
E old = elements[index];
elements[index] = element;
return old;
}
/**
* 在index的位置插入一个元素
* @param index
* @param element
*/
public void add(int index, E element){
rangeCheckForAdd(index);
ensureCapacity(size + 1);
for(int i = size - 1; i >= index; i--){
elements[i + 1] = elements[i];
}
elements[index] = element;
size++;
}
/**
* 删除index位置的元素
* @param index
* @return
*/
public E remove(int index){
rangeCheck(index);
E old = elements[index];
for(int i = index + 1; i <= size - 1; i++){
elements[i-1] = elements[i];
}
size--;
elements[size] = null;
return old;
}
/**
* 查看元素的索引
* @param element
* @return
*/
public int indexOf(E element){
if(element == null){
for (int i = 0; i < size; i++) {
if(elements[i] == null) {
return i;
}
}
}else {
for (int i = 0; i < size; i++) {
if(element.equals(elements[i])) {
return i;
}
}
}
return ELEMENT_NOT_FOUND;
}
private void ensureCapacity(int capacity){
int oldCapacity = elements.length;
if(oldCapacity >= capacity){
return;
}
// 扩容为原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
System.out.println(oldCapacity + "扩容为：" + newCapacity);
}
private void outOfBounds(int index){
throw new IndexOutOfBoundsException("index:" + index + ",size:" + size);
}
private void rangeCheck(int index){
if(index < 0 || index >= size){
outOfBounds(index);
}
}
private void rangeCheckForAdd(int index){
if(index < 0 || index > size){
outOfBounds(index);
}
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
for (int i = 0; i < size; i++) {
if(i != 0){
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
}