图片.png
目录
一、什么是数据结构？
二、线性表
2.1 数组（Array）
2.2 动态数组(Dynamic Array)接口设计
2.3 动态数组(Dynamic Array)示例
一、什么是数据结构？
概念:数据结构是计算存储、组织数据的方式
在实际应用中，根据使用场景来选择最合适的数据结构
常见的数据结构
二、线性表线性表
线性表示具有n相同类型元素的有限序列（n>=0）
图片.png
常见的线性表有
- 数组
- 链表
- 栈
- 队列
- 哈希表（散列表）
2.1 数组（Array）：
int[] array = new int[]{11,2,33};
2.2 动态数组(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(); // 清除所有元素
2.3 动态数组(Dynamic Array)示例
动态数组的属性设计
图片.png
数组的常见操作无非就是 增、删、查、改
ArrayList初始化操作
//泛型 可以存放任何数据类型（int/string/double）
//java中在定义类的时候就要 定义泛型
//<E> 表示泛型 E:表示类型名 （名字随便自己取）
//后面用到E都表示是可以变的 E存放元素的类型
//在java中 所有的类都继承Object
public class ArrayList<E> {
//成员变量
private int size; //元素的数量
public E[] elements; //所有的元素
private static final int DEFAULT_CAPACICY = 2;
private static final int ELEMENT_NOT_FOUND = -1;
//初始化
@SuppressWarnings("unchecked")
public ArrayList(int capaticy) {
capaticy = (capaticy < DEFAULT_CAPACICY)?DEFAULT_CAPACICY:capaticy;
//强制转换
elements = (E[]) new Object[capaticy];
}
public ArrayList() {
this(DEFAULT_CAPACICY);
}
增
/**
* 添加元素到尾部
* */
public void add(E element ) {
add(size, element);
}
/**
* 在index位置插入一个元素
* */
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacity(size+1);
for (int i = size ; i > index; i--) {
elements[i] = elements[i-1];
}
elements[index] = element;
size ++;
}
图片.png
删
/**
* 删除index位置的元素
* */
public void remove(int index) {
rangeCheck(index);
for (int i = index + 1; i < size; i++) {
elements[i- 1] = elements[i];
}
elements[--size] = null;
}
/**
* 删除某个元素
* */
public void removeElement(E element) {
remove(indexOf(element));
}
/**
* 清除所有元素
*/
public void clear() {
// elements =null; 与for的区别
// 推荐使用for 能循环利用则循环利用
// elements =null指的是直接将栈空间 向堆空间申请的线断掉 则堆空间所有数组、内存都清除 那意味着下次又要new一个数组
// for则表示的是 让数组里面指向的对象为null
//清空内存
for (int i = 0; i < size; i++) {
elements[i]= null;
}
// elements =null;
size = 0;
}
图片.png
查
/**
* 获取index位置的元素
* */
public E get(int index) {
rangeCheck(index);
return elements[index];
}
/**
* 查看元素的索引
* */
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 ;
}
/**
* 元素的数量
*/
public int size() {
return size;
}
图片.png
改
/**
* 设置index位置的元素
* */
public void set(int index,E element) {
rangeCheck(index);
elements[index] = element;
}
图片.png
其他操作
/**
* 是否为空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某个元素
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
//扩容
//保证容量
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return; //不需要扩容
//扩容 oldCapacity >> 1 等价于 *1.5 但是*1.5比位运算耗时间
//新容量为旧容量的1.5倍 oldCapacity >> 1 意思是 >>(右移) /2 ， 如果是 <<(左移) *2
int newCapacity = oldCapacity + (oldCapacity >> 1);
@SuppressWarnings("unchecked")
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 rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
}
public void rangeCheck(int index) {
if (index<0 || index >= size) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
}
@Override
public String toString() {
//size = 3, [1,2,3]
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]);
//方式二：需要做减法操作
// if (i != size - 1) {
// string.append(",");
// }
}
string.append("]");
return string.toString();
}
