一、定义
线性表是一种线性结构，它是具有相同类型的n(n≥0)个数据元素组成的有限序列。
二、存储分类
1.顺序存储：
①简述：是指将线性表中的各个元素依次存放在一组地址连续的存储单元中，通常将这种方法存储的线性表称为顺序表；数组中稍微复杂一点的是多维数组和动态数组。对于Java而言，Collection集合中提供了ArrayList和Vector。
②特点：数据是连续的；随机访问速度快；
③实现方式：一维数组
④顺序表相关操作：
A.顺序表的插入
B.顺序表的删除
⑤代码实现(动态数组案例):
@SuppressWarnings("unchecked")
public class ArrayList<E> { //数组中存在的元素数量（与容器大小不同，size<=DEFAULT_CAPACITY）
private int size; //所有元素
private E[] elements; //默认的容器大小
private static final int DEFAULT_CAPACITY = 10;
//不存在默认返回的值
private static final int ELEMENT_NOT_FOUND = -1; /**
* 创建一个自定义容量大小的动态数组，自定义大小不能小于DEFAULT_CAPACITY
*
* @param capaticy 容量大小
*/
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;
}
size = 0;
} /**
* @return 元素的数量
*/
public int size() {
return size;
} /**
* @return 是否为空（true空 false不为空）
*/
public boolean isEmpty() {
return size == 0;
} /**
* @param element 所判断的元素
* @return 是否包含某个元素（true包含 false不包含 ）
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
} /**
* 添加元素到尾部
*
* @param element 添加的元素
*/
public void add(E element) {
add(size, element);
} /**
* 在index位置插入一个元素
*
* @param index
* @param element
*/
public void add(int index, E element) {
//检查添加的位置对不对
rangeCheckForAdd(index);
//检测 size+1<=容器容量 (true不扩容 false扩容)
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 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
* @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;
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) {
//数组的容量，用length是为了获取自定义的容量
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 index
*/
private void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
} /**
* 检查index是不是在[0,size]的范围
* @param index
*/
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
} /**
* 添加元素在index上时，判断index是否在[0,size)的范围
* @param 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();
}
}
