线性表的定义

线性表: 具有n个相同类型元素的有限序列 n>=0
线性表的元素特点是有索引, 可以通过索引快速查找到元素.

a1是a2的前驱, a2是a1的后继
常见的线性表

1. 数组
2. 链表
3. 栈
4. 队列
5. 哈希表 (散列表)

数组

数组是一种顺序存储的线性表, 所有的元素的内存地址是连续的.
int array[] = new int[] {11, 22, 33}
array: 放栈空间
new int 放堆空间
数组在jvm中存放的形式如下图

数组的缺点: 无法动态的修改容量.
解决办法: 自己写一个动态数组.

简易接口设计

自己创建一个ArrayList, 先简易将此数组用于存放int类型的数据

接口设计如下:

public class ArrayList {/*** 清除所有元素*/public void clear() {}/*** 元素的数量* @return*/public int size() {return 0;}/*** 是否为空* @return*/public boolean isEmpty() {return false;}/*** 是否包含某个元素* @param element* @return*/public boolean contains(int element) {return false;}/*** 添加元素到尾部* @param element*/public void add(int element) {}/*** 获取index位置的元素* @param index* @return*/public int get(int index) {return 0;}/*** 设置index位置的元素* @param index* @param element* @return 原来的元素ֵ*/public int set(int index, int element) {return 0;}/*** 在index位置插入一个元素* @param index* @param element*/public void add(int index, int element) {}/*** 删除index位置的元素* @param index* @return*/public int remove(int index) {return 0;}/*** 查看元素的索引* @param element* @return*/public int indexOf(Object element) {return 0;}/*** 保证要有capacity的容量* @param capacity*/private void ensureCapacity(int capacity) {}private void outOfBounds(int index) {}private void rangeCheck(int index) {}private void rangeCheckForAdd(int index) {}@Overridepublic String toString() {return null;}
}