什么是数据结构?
数据结构：是相互之间存在一种或多种关系的数据元素的集合。
逻辑结构和物理结构
关于数据结构，我们可以从逻辑结构和物理结构这两个维度去描述
逻辑结构是数据对象中数据元素之间的关系，是从逻辑意义上去描述的数据之间的组织形式。
逻辑结构有4种：
-
集合结构（数据元素之间仅以集合的方式体现，元素之间没有别的关系）
-
线性结构（数据元素之间存在一对一的关系）
线性表（数组、链表、栈、队列、哈希表）
-
树（数据元素之间为一对多或多对一的关系）
二叉树、AVL树、红黑树、B树、堆、Trie、哈夫曼树、并查集
-
图（数据元素之间为多对多的关系）
邻接矩阵、邻接表
物理结构则是逻辑结构在计算机中内存中的存储形式，分为两种：
-
顺序存储结构
-
链式存储结构
线性表
◼ 线性表是具有 n 个相同类型元素的有限序列（ n ≥ 0 ）
a1是首节点（首元素）， an是尾结点（尾元素）
a1是 a2 的前驱， a2是 a1的后继
数组（Array）
◼ 数组是一种顺序存储的线性表，所有元素的内存地址是连续的
int[] array = new int[]{11,22,33};
◼ 在很多编程语言中，数组都有个致命的缺点
无法动态修改容量
◼ 实际开发中，我们更希望数组的容量是可以
动态改变的
动态数组的设计
package com.njf;
@SuppressWarnings("unchecked")
public class ArrayList<E> {//E为泛型（elements取E开头）
/**
* 元素的数量
*/
private int size;
/**
* 所有的元素
*/
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;//初始数组容量
private static final int ELEMENT_NOT_FOUND = -1;
public ArrayList(int capaticy) {
capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
elements = (E[]) new Object[capaticy];
}
public ArrayList() {
this(DEFAULT_CAPACITY);
}
/**
* 清除所有元素
*/
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null; //对象类型的数组，数组中保存的是元素的内存地址，内存地址置null，这个数组中的元素就不存在了，基本数据类型的数组保存的是元素的值。
}
size = 0;
//缩容操作
if (elements != null && elements.length > DEFAULT_CAPACITY) {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
}
/**
* 元素的数量
* @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; i > index; i--) {
elements[i] = elements[i - 1];
}
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; i++) {
elements[i - 1] = elements[i];
}
elements[--size] = null; //数组最后一位元素的置null（内存地址）
trim();
return old;
}
/**
* 查看元素的索引
* @param element
* @return
*/
public int indexOf(E element) {
if (element == null) { // 1
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; // n
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 保证要有capacity的容量
* @param capacity
*/
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);
}
/**
* 缩容
* @param capacity
*/
private void trim() {
int oldCapacity = elements.length;
int newCapacity = oldCapacity >> 1;
if (size >= newCapacity || oldCapacity <= DEFAULT_CAPACITY) return;
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() {
// size=3, [99, 88, 77]
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();
}
}
下面是调用关系
package com.njf;
public class Main {
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<>();
list.add(new Person("lilei", 15));
list.add(10);
list.add(new Person("lilei", 10));
list.add(null);
Asserts.test(list.size() == 4);
System.out.println(list);
}
}
打印结果
size=4, [Person [name=lilei, age=15], 10, Person [name=lilei, age=10], null]
调用中涉及的验证类别
package com.njf;
public class Person {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Person [name=" + name + ", age=" + age + "]";
}
}
package com.njf;
public class Asserts {
public static void test(boolean value) {
try {
if (!value) throw new Exception("测试未通过");
} catch (Exception e) {
e.printStackTrace();
}
}
}
均摊时间复杂度
在上面的代码中可以看到，在未超出动态数组容量之前，往动态数组中每添加一个元素，时间复杂度为O(1),添加n次，时间复杂度就是O(n),当超出动态数组容量之后，往动态数组中添加元素就会扩容，时间复杂度就变成O(n)。
这种经过连续的多次复杂度比较低，个别复杂度比较高的情况我们用均摊时间复杂度去分析，把每次扩容的时间复杂度O(n)均摊到前面n次未扩容的O(1)上面，这样每次往动态数组中添加元素的平均时间复杂度就是O(2)，根据复杂度的换算规则，其实就是O(1)。
复杂度震荡
在往动态数组中添加元素的时候会出现扩容，有时候为了避免动态数组造成的内存空间的浪费，在删除动态数组元素的时候会进行缩容。假设动态数组容量为n，扩容是2n，缩容的判断条件是0.5n，每次扩容后就删除元素，这样每次时间复杂度就是O(n),出现复杂度震荡
满足复杂度震荡的条件是 扩容*缩容的判断条件 = 1
解决复杂度震荡可以把 缩容的判断条件 = 0.25n，缩容为0.5n
