|
如有错误之处，请指出，谢谢！
ArrayList
通过一个集合变量，来存储数据
可以屏蔽掉底层存储的复杂度
实际存储选择使用数组进行
可以存储任意类型
Java中使用泛型<E>来解决这个问题
也可以采用只存储int
需求分析
需要的数据量级不同
实际存储的容量交由用户决定，或者自己固定分配某个合理的值
ArrayList编写
package list;
//存储任意类型 通过泛型解决
//存储数据大小交由用户指定，或者自己指定一个合适的大小
public class ArrayList <E>{
private E[] elementsData;//实际存储元素的容器
private static final int INIT_CAPACITY=10;//指定默认情况下数组的初始长度为10
private int size;//维护当前数组中的待添加的索引位置，维护当前数组的元素个数
/*
* 空构造器 创建一个指定长度的数组对象
* */
public ArrayList() {
this(INIT_CAPACITY);
}
/*
* 带参构造器 创建用户指定长度的数组对象
* @param capacity 用户指定数组长度
* */
public ArrayList(int capacity) {
this.elementsData = (E[]) new Object[capacity];
}
/*
* 添加元素E到当前的集合中指定位置
* @param
* */
public void add(E e,int index) {//时间复杂度O（n）
//判定元素的合法性
checkIndex(index);
//循环挪动元素
for(int i=size;i>index;i--) {
elementsData[i]=elementsData[i-1];
//添加元素到index
}
elementsData[index]=e;
//维护size
size++;
}
/*
* 判定index的合法性
* @param Index
* */
private void checkIndex(int index) {
if(index<0||index>size) {
throw new IllegalArgumentException("index out of bounds index:"+index);
}
}
/*
* 添加首元素
* @param e
* */
public void addFirst(E e) {//时间复杂度O（n）
add(e,0);
}
/*
* 添加元素E到当前的集合中的末尾
* @param
* */
public void add(E e) {//时间复杂度O（1）
elementsData[size] =e;//将元素e添加到size指向的索引位置
size++;//维护size
}
/*
* 添加元素E到当前的集合中的末尾
* @param
* */
public void addLast(E e) {//时间复杂度O（1）
elementsData[size] =e;//将元素e添加到size指向的索引位置
size++;//维护size
}
/*
* 查看当前集合是否为空
* @return
* */
public boolean isEmpty() {//时间复杂度O（1)
return size ==0;
}
/*
* 查看当前集合中的元素个数
* @return
* */
public int getSize() {//时间复杂度O（1)
return this.size;
}
public String toString() {//时间复杂度O（n)
StringBuilder retStr = new StringBuilder();
retStr.append("size:"+size+"[");
for(int i=0;i<size;++i) {
retStr.append(elementsData[i]);
if(i!=size-1)
retStr.append(",");
}
retStr.append("]");
return retStr.toString();
}
}
?? ?public void add(E e) {//时间复杂度O（1）
?? ?public void addLast(E e) {//时间复杂度O（1）
? ???public boolean isEmpty() {//时间复杂度O（1)
?? ?public int getSize() {//时间复杂度O（1)
?? ?public String toString() {//时间复杂度O（n)
测试用例
package list;
public class ArrayListTest {
public static void main(String[] args) {
ArrayList<Integer> lists =new ArrayList<>();
System.out.println(lists.isEmpty());
System.out.println(lists.getSize());
for(int i=1;i<11;i++) {
lists.add(i);
System.out.println(lists);
}
/*
* true
0
size:1[1]
size:2[1,2]
size:3[1,2,3]
size:4[1,2,3,4]
size:5[1,2,3,4,5]
size:6[1,2,3,4,5,6]
size:7[1,2,3,4,5,6,7]
size:8[1,2,3,4,5,6,7,8]
size:9[1,2,3,4,5,6,7,8,9]
size:10[1,2,3,4,5,6,7,8,9,10]/
*/
}
}
指定位置上添加元素
判定元素的合法性：
不能添加超过size元素，防止数组中出现内部碎片
/*
* 添加元素E到当前的集合中指定位置
* @param
* */
public void add(E e,int index) {//时间复杂度O（n）
//判定元素的合法性
checkIndex(index);
//循环挪动元素
for(int i=size;i>index;i--) {
elementsData[i]=elementsData[i-1];
//添加元素到index
}
elementsData[index]=e;
//维护size
size++;
}
/*
* 判定index的合法性
* @param Index
* */
private void checkIndex(int index) {
if(index<0||index>size) {
throw new IllegalArgumentException("index out of bounds index:"+index);
}
}
/*
* 添加首元素
* @param e
* */
public void addFirst(E e) {//时间复杂度O（n）
add(e,0);
}
?? ?public void add(E e,int index) {//时间复杂度O（n）
?? ?public void addFirst(E e) {//时间复杂度O（n）
测试用例
for(int i=1;i<7;i++) {
lists.add(i);
}
lists.addFirst(11);
lists.add(13, 1);
System.out.println(lists);
//size:8[11,13,1,2,3,4,5,6]
|