概念：略
数据结构的存储方式: 线性结构，树型结构，图形结构
image.png
线性结构 :
树型结构：
二叉树，AVL树，红黑树，B树，堆，Tire,哈夫曼树，并查集
图形结构
在实际的应用中，根据使用场景来选择最合适的数据结构
线性表
线性表示具有N个相同元素的有限序列(n>=0)
image.png
线性表元素的特点
-
通过索引查找
image.png - a1是首节点，a...n 是尾结点
-
a1是a2的前驱，a2是a1的后驱
image.png
image.png
image.png
可以通过自定义动态数据来实现
下面介绍自定义动态数据接口
image.png
动态数据的实现源码
package com.example.demo;
import java.util.Arrays;
public class DynaicArray<E> {
// 初始化元素的个数
private static final int DEFAULT_CAPACITY = 10;
private Object elementData[] = {};
// 元素数量
private int size;
public DynaicArray() {
this(DEFAULT_CAPACITY);
}
public DynaicArray(int initialCapacity) {
initialCapacity = initialCapacity < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : initialCapacity;
this.elementData = new Object[initialCapacity];
}
public int size() {
return size;
}
public void clear() {
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
public void add(E element) {
ensureCapacityInternal(size + 1);
elementData[size++] = element;
}
/**
* 指定数组下标添加
* 元素移动规则，先移动最后面的元素
* @param index
* @param element
*/
public void add(int index, E element) {
ensureCapacityInternal(size + 1);
// index > this.size 不能出现中间断连接的情况
if (index < 0 || index > this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// 元素移动
for (int i = size; i > index; i++)
// 向后移动一位
elementData[i + 1] = elementData[i];
// 添加指定元素
elementData[index] = element;
size++;
}
private void ensureCapacityInternal(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow();
}
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
Object newElement[] = new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElement[i] = elementData[i];
}
elementData = newElement;
}
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
/**
* 获取元素
* @param index
* @return
*/
public E get(int index) {
rangeCheck(index);
return (E) elementData[index];
}
E elementData(int index) {
return get(index);
}
/**
*检查给定索引是否在范围内。如果没有，抛出一个合适的
* 运行时异常。此方法不检查索引是否
* 否定：它总是在数组访问之前使用，
* 如果索引为负，则抛出ArrayIndexOutOfBoundsException。
* @param index
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 构造IndexOutboundsException详细消息。
* 在许多可能的错误处理代码重构中，
* 这种“大纲”在服务器和客户机vm中表现最好。
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
/**
* 查找元素的位置
* @param element
* @return
*/
public int indexOf(E element) {
if (element == null) {
for (int i = 0; i < size; i++) {
if (elementData[i] == null)
return i;
}
}else {
for (int i = 0; i < size; i++) {
if (elementData[i].equals(element))
return i;
}
}
return -1;
}
/**
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
public boolean contains(E element) {
return indexOf(element) >= 0;
}
/**
* 删除元素
* @param element
*/
public void remove(E element) {
remove(indexOf(element));
}
public E remove(int index) {
rangeCheck(index);
for (int i = index + 1; i <= size -1; i++)
elementData[i - 1] = elementData[i];
elementData[--size] = null;
return (E) elementData[index];
}
@Override
public String toString() {
return "DynaicArray{" +
"elementData=" + Arrays.toString(elementData) +
", size=" + size +
'}';
}
}
动态数组的缺点
有可能造成内存空间的大量浪费
能否使用多少申请多少？
链表可以办到这一点
