一、线性表
线性表是具有n个相同类型元素的有限序列（n>=0）
索引 0 1 2 ...... n-3 n-2 n-1
A1——A2——A3 ...... An-2 An-1 An
其中 A1是首节点（首元素），An是尾节点（尾元素）
A1是A2的前驱，A2是A1的后继
常见的线性表有：数组、链表、栈、队列、哈希表（散列表）
二、数组
数组是一种顺序存储的线性表，所有元素的内存地址是连续的。
例如：int[] array = new int[]{11,22,33}表示一个数组。
然而这种数组是无法动态修改容量的。因此，在开发中我们更希望数组的容量是可以动态改变的。
三、动态数组
1.动态数组接口设计
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.接口的实现
public class Arraylist {
//前期准备:元素数量定义、所有元素定义、开辟新的空间
private int size;// 定义元素数量
private int[] elements;// 定义所有元素
public static final int DEFAULT_CAPACITY = 2;// 定义静态变量
public static final int ELEMENT_NOT_FOUND = -1;
public Arraylist(int capaticy) {// 定义构造方法来开辟空间
capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
elements = new int[capaticy];// 创造元素空间
}
public Arraylist() {
this(DEFAULT_CAPACITY);
}
//1.清除所有元素
public void clear() {
size = 0;
}
//2. 元素数量
public int size() {
return size;
}
//3.是否为空
public boolean isEmpty() {
return size == 0;// size==0:true/size!=0:false
}
//4.是否包含某个元素
public boolean contains(int element) {
return indexOf(element) != ELEMENT_NOT_FOUND;// 不包含返回-1
}
//5.添加元素到最后面
/*
* 数组扩容问题（add方法）： 1.申请一个更大的空间 2.将数据挪动 3.将数组指向更大空间
*/
public void add(int element) {
ensureCapacity(size + 1);
// size为几就往里面添加
elements[size] = element;
size++;
}
private void ensureCapacity(int capacity) {// 保证有capacity个容量
int oldCapacity = elements.length;
if (oldCapacity >= capacity)
return;
int newCapacity = oldCapacity + (oldCapacity >> 1);// 扩容为原来的1.5倍
int[] newElements = new int[newCapacity];// 1.开辟新空间
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];// 2.将原先数据挪动
}
elements = newElements;// 3.将数组指向更大空间
}
//6.返回index位置对应的元素
public int get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index:" + index + ",Size:" + size);
}
return elements[index];
}
//7.设置index位置的元素
public int set(int index, int element) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index:" + index + ",Size:" + size);
}
int old = elements[index];
elements[index] = index;
return old;
}
// 8.往index位置添加元素
// index及其后面的元素向后挪一个位置（最后面的先向后挪动）从size-1到index的元素挪动，空出来的元素插入新元素
public void add(int index, int element) {
if (index < 0 || index > size) {// 允许index>size：向最后一个位置插入元素
throw new IndexOutOfBoundsException("Index:" + index + ",Size:" + size);
}
ensureCapacity(size + 1);// 保证有多少容量
for (int i = size - 1; i >= index; i--) {
elements[i + 1] = elements[i];// 挪动元素
}
elements[index] = element;// 插入元素
size++;
}
// 9.删除index位置对应的元素
// 将要删除的元素后的元素向前移动 移动范围：index+1到size-1这些个数
public int remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index:" + index + ",Size:" + size);
}
int old = elements[index];
for (int i = index + 1; i <= size - 1; i++) {
elements[i - 1] = elements[i];
}
size--;
return 0;
}
// 10.查看元素的位置
public int indexOf(int element) {
for (int i = 0; i < size; i++) {
if (element == elements[i])
return i;
}
return ELEMENT_NOT_FOUND;
}
// 输出元素信息
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();
}
}
public static void main(String[] args) {
//new:向堆空间申请内存
Arraylist list = new Arraylist();
list.add(33);
list.add(40);
list.add(22);
list.add(34);
list.add(29);
list.add(1,39);
System.out.println(list.toString());
}
image.png
