ArrayList原理
数据结构
ArrayList的底层数据结构就是一个数组,数组元素的类型为Object类型,对ArrayList的所有操作底层都是基于数组的。
自己制作一个ArrayList
package com.lhx.list;
import java.util.ArrayList;
import java.util.Arrays;
/**
* 自己制作一个ArrayList
* */
public class MyArrayList {
private Object[] arr = null;
private int i;
public MyArrayList() {
this(10);
}
public MyArrayList(int capacity) {
this.arr = new Object[capacity];
}
public void add(Object obj){
ensureCapacityInternal();
arr[i++] = obj;
}
private void ensureCapacityInternal() {
if(i == arr.length){
arr = Arrays.copyOf(arr,arr.length * 3 / 2);
}
}
public Object get(int index){
return arr[index];
}
public void remove(int index){
for (int j = index; j < arr.length - 1; j++) {
arr[j] = arr[j + 1];
}
arr[arr.length - 1] = null;
}
public int size(){
int i = 0;
for (Object o : arr) {
if(o != null){
i++;
}
}
return i;
}
@Override
public String toString() {
//[11, 22, 33, 44, 55]
StringBuffer sb = new StringBuffer();
sb.append("[");
for (Object o : arr) {
if(o != null) {
sb.append(o);
sb.append(", ");
}
}
sb.deleteCharAt(sb.length()-1);
sb.deleteCharAt(sb.length()-1);
sb.append("]");
return sb.toString();
}
//==================================Test===================================
public static void main(String[] args) {
list();
MyArrayList ml = new MyArrayList();
ml.add("11");
ml.add("22");
ml.add("33");
ml.add("44");
ml.add("55");
ml.remove(6);
System.out.println(ml.size());
System.out.println(ml.toString());
}
private static void list(){
ArrayList list = new ArrayList();
list.add("11");
list.add("22");
list.add("33");
list.add("44");
list.add("55");
list.remove(4);
System.out.println(list.size());
System.out.println(list.toString());
System.out.println("==========================");
}
}
优缺点
- 优点
- ArrayList底层以数组实现,是一种随机访问模式,再加上它实现了RandomAccess接口,因此查找也就是get的时候非常快。
- ArrayList在顺序添加一个元素的时候非常方便,只是往数组里面添加了一个元素而已。
- 根据下标遍历元素,效率高。
- 根据下标访问元素,效率高。
- 可以自动扩容,默认为每次扩容为原来的1.5倍。
- 缺点
- 插入和删除元素的效率不高。
- 根据元素下标查找元素需要遍历整个元素数组,效率不高。
- 线程不安全。