网站开发培训多少钱,自己弄个网站要多少钱,营销互联网推广,网站备案登陆目录
ArrayList实现类
数据存储
构造器
成员方法#xff1a;CRUD
Vector实现类
数据存储
构造器方法
成员方法
LinkedList实现类
数据存储
构造器方法
成员方法CRUD
List总结 ArrayList#xff1a;数组实现#xff0c;随机访问速度快#xff0c;增删慢#x…目录
ArrayList实现类
数据存储
构造器
成员方法CRUD
Vector实现类
数据存储
构造器方法
成员方法
LinkedList实现类
数据存储
构造器方法
成员方法CRUD
List总结 ArrayList数组实现随机访问速度快增删慢轻量级(线程不安全)
LinkedList双向链表实现增删快随机访问慢 (线程不安全)
Vector数组实现重量级 (线程安全、使用少) ArrayList实现类 List listnew ArrayList();
类定义
public class ArrayListE extends AbstractListE implements ListE, RandomAccess,
Cloneable, java.io.Serializable
数据存储
transient Object[] elementData; //底层存储实现采用的是数组当存储数据元素超过数组长度时会进行扩容处理。
构造器
1、public ArrayList() { //ArrayList默认实现中,针对元素存储的数组赋值为空数组实际上这是一种优化策略避免饿汉模式的缺陷避免额外的空间浪费。 this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
其中常量定义为
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; //空数组 2、public ArrayList(int initialCapacity) { //参数为初始化容积不是元素个数size。 if (initialCapacity 0) { this.elementData new Object[initialCapacity]; //构建指定长度的数组 } else if (initialCapacity 0) { //如果初始化容积为0则为空数组 this.elementData EMPTY_ELEMENTDATA; } else { //否则抛出异常 throw new IllegalArgumentException(Illegal Capacity: initialCapacity); }}
成员方法CRUD
1、public boolean add(E e)
public boolean add(E e) {modCount;
//一个用于实现fail-fast异常的参数记录的是修改次数在迭代器中需要使用这个值只要修改了结构则1add(e, elementData, size);
//参数1为需要插入的数据参数2为正在使用的数组参数3为当前元素个数return true;
//除非上一步出现异常否则返回true表示插入成功
}
private void add(E e, Object[] elementData, int s) {if (s elementData.length) //如果当前数组长度等于元素个数则扩容处理elementData grow();elementData[s] e; //在指定位置存储元素size s 1; //元素个数1
}
private Object[] grow() {return grow(size 1); //新容器为元素个数1
}
private Object[] grow(int minCapacity) {
//参数size1实际上是所需要的最小容积不是扩容的目标大小int oldCapacity elementData.length;
//获取当前数组的长度if (oldCapacity 0 || elementData ! DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, oldCapacity 1 );
//获取最新容积大小值参数1为当前容积值参数2为最小扩容值【size1-数组长度】参数3为老容积值的1/2整除return elementData Arrays.copyOf(elementData, newCapacity);
//执行老数组的元素数据拷贝并将扩容后的新数组赋值给属性以替换老数组} else { //如果容积值0则创建10个长的数组用于存储元素return elementData new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}
}
ArraySupport工具类
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {int prefLength oldLength Math.max(minGrowth, prefGrowth); // might overflow
//新容器老容积max(最小扩容值1老容积的1/2),扩容为50%*原始容积if (0 prefLength prefLength SOFT_MAX_ARRAY_LENGTH) {return prefLength;
//扩容值在0到Integer.MAX_VALUE - 8则正常使用该扩容值} else {
//如果扩容目标长度值大于Integer.MAX_VALUE - 8如果原始长度1小于0 越int界则异常中断如果原始长度1在Integer.MAX_VALUE - 8范围内则每次扩容到Integer.MAX_VALUE - 8;如果原始长度1大于Integer.MAX_VALUE - 8时则每次扩容目标值为原始长度1return hugeLength(oldLength, minGrowth); //原始容积 最小增长值1}
}
private static int hugeLength(int oldLength, int minGrowth) {int minLength oldLength minGrowth; //原始长度1if (minLength 0) { //最小长度值0 则数据溢出抛出异常Error中断运行throw new OutOfMemoryError(Required array length oldLength minGrowth is too large);} else if (minLength SOFT_MAX_ARRAY_LENGTH) {return SOFT_MAX_ARRAY_LENGTH;} else {return minLength;}
}
结论添加数据时当存储数据的数组长度不足时数组会自动变长变长的比例为50% 2、remove方法定义
2.1 public boolean remove(Object o) //按照元素进行删除
2.2 public E remove(int index) //按照指定下表进行删除并返回被删除的元素
public E remove(int index) {Objects.checkIndex(index, size);
//调用工具类Objects中的方法进行索引需要的合法性检查如果不合法[0,size)之间否则IndexOutOfBoundsExceptionfinal Object[] es elementData;
//缓存数组变量,如果需要2个不同对象但是内容相同的数组则需要clone处理只是将存放数据的数组地址赋值给新变量不管使用elementData变量还是使用es变量都是在操作同一个数组E oldValue (E) es[index];
//从数组中获取指定index位置上的数据fastRemove(es, index);
//采用System.arraycopy将指定位置上的数据进行覆盖return oldValue;
}
private void fastRemove(Object[] es, int i) {modCount; //修改次数1final int newSize;if ((newSize size - 1) i) System.arraycopy(es, i 1, es, i, newSize - i);es[size newSize] null;
}
结论使用数组元素移动的方式实现元素的删除 System.arraycopy(es, i 1, es, i, newSize - i);
注意这里没有变小容积
修改元素个数时会有modCount的修改--快速失败
修改次数定义在AbstractList抽象类中
protected transient int modCount 0;
public IteratorE iterator() {return listIterator(); // ---new 迭代器
}
//在抽象类中采用内部类的方式提供了迭代器的实现类
private class Itr implements IteratorE
属性int expectedModCount modCount; //当创建迭代器对象时会记录当前的修改次数
public E next() {
//调用迭代的next方法获取下一个元素时会针对当前集合的修改次数和缓存的修改次数进行比较如果不相等则抛出ConcurrentModificationException异常checkForComodification();// ... ...}
final void checkForComodification() {if (modCount ! expectedModCount)throw new ConcurrentModificationException();
} 3、get方法的实现
结论首先要求index应该在[0,size-1]的范围内否则异常
如果index正确则按照下标从数组中获取元素
public E get(int index) {Objects.checkIndex(index, size);return elementData(index);
}
E elementData(int index) {return (E) elementData[index];
} Vector实现类
public class VectorE extends AbstractListE implements ListE, RandomAccess,Cloneable, java.io.Serializable
从JDK1.0开始就提供的一个List的实现类属于较老的不推荐使用的实现类建议优先考虑ArrayList因为两者的实现方式基本一致而且ArrayList性能优于Vector.
数据存储
protected Object[] elementData; //底层实现仍旧采用的是数组
构造器方法
1、public Vector()
public Vector() {this(10); //无参构建Vector对象时默认初始化容积为10默认容积增长的步长值为0
}
2、public Vector(int initialCapacity)
public Vector(int initialCapacity) {this(initialCapacity, 0);
}
3、public Vector(int initialCapacity, int capacityIncrement)
public Vector(int initialCapacity, int capacityIncrement) {super();if (initialCapacity 0)throw new IllegalArgumentException(Illegal Capacity: initialCapacity);this.elementData new Object[initialCapacity];
//直接创建的就是指定长度的数组并没有支持延迟创建数组的操作this.capacityIncrement capacityIncrement;
}
成员方法
绝大部分的成员方法前有synchronized关键字线程安全属于重量级
1、public synchronized boolean add(E e)
public synchronized boolean add(E e) {modCount; //修改次数1快死异常add(e, elementData, elementCount);
//参数1为需要添加的数据参数2为原始数组参数3为当前元素个数sizereturn true;
}
private void add(E e, Object[] elementData, int s) {if (s elementData.length) //当元素个数和数组长度一致时进行扩容处理growelementData grow();elementData[s] e; //扩容后的数组存储元素elementCount s 1; //元素个数1
}
private Object[] grow() {return grow(elementCount 1); //参数为当前元素个数1作为所需要的最小容积值
}
private Object[] grow(int minCapacity) {int oldCapacity elementData.length; //获取当前数组长度int newCapacity ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, capacityIncrement 0 ? capacityIncrement : oldCapacity);
//获取扩容后的新数组最佳长度值。如果设定了扩容步长值则使用构建Vector对象时所设置的扩容步长值进行长度的递增【定值】如果没有设置则扩容步长值默认为0则新长度为原始长度的2倍扩容100%原始长度return elementData Arrays.copyOf(elementData, newCapacity);
} LinkedList实现类
public class LinkedListE extends AbstialLtractSequenistE implements ListE,
DequeE, Cloneable, java.io.Serializable
实现了Deque双向队列接口
数据存储
transient NodeE first; //头指针
transient NodeE last; //尾指针
private static class NodeE { //静态的内部类定义了列表中每个节点的数据类型。双向链表结构E item; //具体存储的数据NodeE next; //指向下一个元素的后续指针NodeE prev; //指向上一个元素的前驱指针Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;}
}
构造器方法
public LinkedList() {}public LinkedList(Collection? extends E c) {this();addAll(c);}
成员方法CRUD
1、public boolean add(E e)
public boolean add(E e) {linkLast(e); //在链表的默认添加新元素Node类型其中包含存储的数据ereturn true;
}
void linkLast(E e) {final NodeE l last; //获取尾指针final NodeE newNode new Node(l, e, null); //构建链表中的元素对象Node其中包含数据elast newNode; //原始尾指针指向新元素if (l null) //如果尾指针为null则表示链表中没有数据则将头和尾指向同一个元素first newNode;else //如果尾指针不为null则将新元素添加到尾指针(Node元素的后续指针)之后l.next newNode;size; //元素个数1modCount; //修改次数1
} 2、指定位置index序号添加元素
public void add(int index, E element) {checkPositionIndex(index); index 0 index sizeif (index size) //如果插入元素的位置等于元素个数则插入到末尾linkLast(element);else //否则在指定位置之前插入元素linkBefore(element, node(index)); //node()用于获取指定位置的节点元素
}
NodeE node(int index) {
//按照索引序号查找指定位置上的元素时首先判断序号距离头部近还是尾部近如果距离头部近则从头指针指向的元素开始查找如果距离尾部较劲则从后向前查找元素。可以减少1/2个数的元素查找if (index (size 1)) {NodeE x first;for (int i 0; i index; i)x x.next;return x;} else {NodeE x last;for (int i size - 1; i index; i--)x x.prev;return x;}
}
3、public boolean remove(Object o)
public boolean remove(Object o) {
//删除定义元素。如果需要删除的元素o则从头指针开始遍历整个链表如果Node节点对象中的数据为o【equals】则执行删除操作。删除第一个值为o的元素节点if (o null) { for (NodeE x first; x ! null; x x.next) {if (x.item null) { unlink(x); //删除指定的节点return true;}}} else {for (NodeE x first; x ! null; x x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;
} 4、public E remove(int index)
public E remove(int index) {
//按照序号删除指定位置上的节点checkElementIndex(index);
// index 0 index sizereturn unlink(node(index));
//首先调用node()方法获取指定位置上的Node对象然后删除指定的节点
}
总结双向链表实现由于没有数据移动的问题所以号称增删快【增删时还需要查找元素所以实际上差不多O(n)】随机访问慢 (线程不安全)。没有扩容问题按需开辟空间没有空间浪费。
List总结 ArrayList LinkedList Vector 实现方式 数组按照索引下标访问速度快O(1),但是当删除添加元素时会导致元素的移动速度慢O(n) 双向链表按照索引下标访问速度慢O(n)但是删除添加元素速度快O(1) 数组按照索引下标访问速度快O(1),但是当删除添加元素时会导致元素的移动速度慢O(n) 是否同步 不同步,线程不安全但是并发高,访问效率高 不同步,线程不安全但是并发高,访问效率高 同步,所以线程安全但是并发低,访问效率低 如何选择 经常需要快速访问较少在中间增加删除元素时使用;如果多线程访问则需要自行编程解决线程安全问题 经常需要在内部增删元素但是很少需要通过索引快速访问时使用;如果多线程访问则需要自行编程解决线程安全问题 一般不使用如果在多线程访问时可以考虑使用
