Java容器ArrayList知识点总结
程序员文章站
2023-12-19 14:22:52
arraylist
底层实现是数组,访问元素效率高 (查询快,插入、修改、删除元素慢)
与linkedlist相比,它效率高,但线程不安全。
arraylist数...
arraylist
底层实现是数组,访问元素效率高 (查询快,插入、修改、删除元素慢)
与linkedlist相比,它效率高,但线程不安全。
arraylist数组是一个可变数组,可以存取包括null在内的所有元素
- 每个arraylist实例都有一个容量,该容量是指用来存储列表元素的数组的大小
- 随着向arraylist中不断增加元素,其容量自动增长
- 在添加大量元素前,应用程序也可以使用ensurecapacity操作来增加arraylist实例的容量,这样可以减少递增式再分配的数量。
- 所以如果我们明确所插入元素的多少,最好指定一个初始容量值,避免过多进行扩容操作而浪费时间、效率
- 源码分析
底层使用数组实现
transient object[] elementdata;
构造方法
private static final int default_capacity = 10; private static final object[] empty_elementdata = {}; private static final object[] defaultcapacity_empty_elementdata = {}; transient object[] elementdata; private int size; // 构造一个空列表 public arraylist() { this.elementdata = defaultcapacity_empty_elementdata ; } // 构造一个指定初始容量的空列表 public arraylist(int initialcapacity) { if (initialcapacity > 0) { this.elementdata = new object[initialcapacity]; } else if (initialcapacity == 0) { this.elementdata = empty_elementdata; } else { throw new illegalargumentexception("illegal capacity: "+ initialcapacity); } } // 构造一个指定collection元素的列表,这些元素按照connection元素的迭代返回顺序进行排列 public arraylist(collection<? extends e> c) { elementdata = c.toarray(); if ((size = elementdata.length) != 0) { // c.toarray might (incorrectly) not return object[] (see 6260652) if (elementdata.getclass() != object[].class) elementdata = arrays.copyof(elementdata, size, object[].class); } else { // replace with empty array. this.elementdata = empty_elementdata; } }
存储
// 在列表的指定位置的元素用element替代,并且返回该位置原来的元素 public e set(int index, e element) { rangecheck(index); // 检查数组容量,抛出:indexoutofboundsexception e oldvalue = elementdata(index); elementdata[index] = element; return oldvalue; } // 在列表的尾部添加指定元素 public boolean add(e e) { ensurecapacityinternal(size + 1); // 数组扩容 elementdata[size++] = e; return true; } // 在列表的指定位置添加元素 public void add(int index, e element) { rangecheckforadd(index); ensurecapacityinternal(size + 1); // increments modcount!! // src:源数组,srcpro:源数组中的起始位置 // dest:目标数组,destpost:目标数组的起始位置,length:要复制的数组元素数量 // 将当前位于该位置的元素以及所有后续元素后移一个位置 system.arraycopy(elementdata, index, elementdata, index + 1, size - index); // 用element替换index位置的元素 elementdata[index] = element; size++; } // 在列表的尾部添加connection中的元素,元素顺序按照connection迭代器返回的顺序 public boolean addall(collection<? extends e> c) { object[] a = c.toarray(); // 转化为一个数组 int numnew = a.length; ensurecapacityinternal(size + numnew); // increments modcount // increments modcount!! system.arraycopy(a, 0, elementdata, size, numnew); size += numnew; return numnew != 0; } // 在列表的指定位置添加connection中的元素,元素顺序按照connection迭代器返回的顺序 public boolean addall(int index, collection<? extends e> c) { rangecheckforadd(index); object[] a = c.toarray(); int numnew = a.length; ensurecapacityinternal(size + numnew); // increments modcount int nummoved = size - index; if (nummoved > 0) system.arraycopy(elementdata, index, elementdata, index + numnew, nummoved); system.arraycopy(a, 0, elementdata, index, numnew); size += numnew; return numnew != 0; }
读取
// 移除此列表指定位置上的元素 public e remove(int index) { rangecheck(index); modcount++; e oldvalue = elementdata(index); int nummoved = size - index - 1; if (nummoved > 0) system.arraycopy(elementdata, index+1, elementdata, index, nummoved); elementdata[--size] = null; // clear to let gc do its work return oldvalue; } // 移除此列表中的某个元素 public boolean remove(object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementdata[index] == null) { fastremove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementdata[index])) { fastremove(index); return true; } } return false; } private void fastremove(int index) { modcount++; int nummoved = size - index - 1; if (nummoved > 0) system.arraycopy(elementdata, index+1, elementdata, index, nummoved); elementdata[--size] = null; // clear to let gc do its work }
数组扩容
每当向数组中添加元素时,都需要去检查添加元素后元素的个数是否超出当前数组的长度,如果超出,数组将会进行扩容,以满足添加数据的需求。
public void ensurecapacity(int mincapacity) { int minexpand = (elementdata != defaultcapacity_empty_elementdata ) ? 0 : default_capacity; if (mincapacity > minexpand) { ensureexplicitcapacity(mincapacity); } } private void ensurecapacityinternal(int mincapacity) { if (elementdata == defaultcapacity_empty_elementdata ) { mincapacity = math.max(default_capacity, mincapacity); } ensureexplicitcapacity(mincapacity); } private void ensureexplicitcapacity(int mincapacity) { modcount++; // overflow-conscious code if (mincapacity - elementdata.length > 0) grow(mincapacity); } private void grow(int mincapacity) { // overflow-conscious code int oldcapacity = elementdata.length; int newcapacity = oldcapacity + (oldcapacity >> 1); if (newcapacity - mincapacity < 0) newcapacity = mincapacity; if (newcapacity - max_array_size > 0) newcapacity = hugecapacity(mincapacity); // mincapacity is usually close to size, so this is a win: elementdata = arrays.copyof(elementdata, newcapacity); } private static int hugecapacity(int mincapacity) { if (mincapacity < 0) // overflow throw new outofmemoryerror(); return (mincapacity > max_array_size) ? integer.max_value : max_array_size; }
手写arraylist
public class myarraylist /*implements list<e>*/{ private transient object[] elementdata; private int size; //元素个数 public myarraylist(){ this(10); } public myarraylist(int initialcapacity) { if (initialcapacity<0) { try { throw new exception(); } catch (exception e) { e.printstacktrace(); } } elementdata = new object[initialcapacity]; } public int size() { return size; } public boolean isempty(){ return size == 0; } //根据index删掉对象 public void remove(int index) throws exception { rangecheck(index); int nummoved = size-index-1; if (nummoved > 0) { system.arraycopy(elementdata, index+1, elementdata, index, nummoved); } elementdata[--size] = null; } //删掉对象 public boolean remove(object obj) throws exception { for (int i = 0; i < size; i++) { if (get(i).equals(obj)) { remove(i); } return true; } return true; } //修改元素 public object set(int index , object obj ) throws exception{ rangecheck(index); object oldvalue = elementdata[index]; elementdata[index] = obj; return oldvalue; } //在指定位置插入元素 public void add(int index,object obj) throws exception { rangecheck(index); ensurecapacity(); system.arraycopy(elementdata, index, elementdata, index+1, size-index); elementdata[index] = obj; size ++; } public void add(object object) { ensurecapacity(); /*elementdata[size] = object; size ++;*/ elementdata[size++] = object; //先赋值,后自增 } public object get(int index) throws exception { rangecheck(index); return elementdata[index]; } public void rangecheck(int index) throws exception { if (index<0 || index >=size) { throw new exception(); } } //扩容 public void ensurecapacity() { //数组扩容和内容拷贝 if (size==elementdata.length) { //elementdata = new object[size*2+1]; 这么写原来数组里的内容丢失 object[] newarray = new object[size*2+1]; //拷贝数组里的内容 /*for (int i = 0; i < newarray.length; i++) { newarray[i] = elementdata[i]; }*/ system.arraycopy(elementdata, 0, newarray, 0, elementdata.length); elementdata = newarray; } } // 测试 public static void main(string[] args) { myarraylist myarraylist = new myarraylist(3); myarraylist.add("111"); myarraylist.add("222"); myarraylist.add("333"); myarraylist.add("444"); myarraylist.add("555"); try { myarraylist.remove(2); myarraylist.add(3, "新值"); myarraylist.set(1, "修改"); } catch (exception e1) { // todo auto-generated catch block e1.printstacktrace(); } system.out.println(myarraylist.size()); for (int i = 0; i < myarraylist.size(); i++) { try { system.out.println(myarraylist.get(i)); } catch (exception e) { e.printstacktrace(); } } } }