90做网站,装修公司网站多少钱,怎么查公司地址,做系统前的浏览网站能找回吗目录 7.2.4 Vector部分源码分析
7.3 链表LinkedList
7.3.1 链表与动态数组的区别
7.3.2 LinkedList源码分析
启示与开发建议 7.2.4 Vector部分源码分析
jdk1.8.0_271中#xff1a;
//属性
protected Object[] elementData;
protected int elementCount;//构造器
public …目录 7.2.4 Vector部分源码分析
7.3 链表LinkedList
7.3.1 链表与动态数组的区别
7.3.2 LinkedList源码分析
启示与开发建议 7.2.4 Vector部分源码分析
jdk1.8.0_271中
//属性
protected Object[] elementData;
protected int elementCount;//构造器
public Vector() {this(10); //指定初始容量initialCapacity为10
}public Vector(int initialCapacity) {this(initialCapacity, 0); //指定capacityIncrement增量为0
}public Vector(int initialCapacity, int capacityIncrement) {super();//判断了形参初始容量initialCapacity的合法性if (initialCapacity 0)throw new IllegalArgumentException(Illegal Capacity: initialCapacity);//创建了一个Object[]类型的数组this.elementData new Object[initialCapacity];//增量默认是0如果是0后面就按照2倍增加如果不是0后面就按照你指定的增量进行增量this.capacityIncrement capacityIncrement;
}//方法add()相关方法
//synchronized意味着线程安全的
public synchronized boolean add(E e) {modCount;//看是否需要扩容ensureCapacityHelper(elementCount 1);//把新的元素存入[elementCount]存入后elementCount元素的个数增1elementData[elementCount] e;return true;
}private void ensureCapacityHelper(int minCapacity) {//看是否超过了当前数组的容量if (minCapacity - elementData.length 0)grow(minCapacity); //扩容
}private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity elementData.length; //获取目前数组的长度//如果capacityIncrement增量是0新容量 oldCapacity的2倍//如果capacityIncrement增量是不是0新容量 oldCapacity capacityIncrement增量;int newCapacity oldCapacity ((capacityIncrement 0) ?capacityIncrement : oldCapacity);//如果按照上面计算的新容量还不够就按照你指定的需要的最小容量来扩容minCapacityif (newCapacity - minCapacity 0)newCapacity minCapacity;//如果新容量超过了最大数组限制那么单独处理if (newCapacity - MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);//把旧数组中的数据复制到新数组中新数组的长度为newCapacityelementData Arrays.copyOf(elementData, newCapacity);
}//方法remove()相关方法
public boolean remove(Object o) {return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {modCount;//查找obj在当前Vector中的下标int i indexOf(obj);//如果i0说明存在删除[i]位置的元素if (i 0) {removeElementAt(i);return true;}return false;
}//方法indexOf()
public int indexOf(Object o) {return indexOf(o, 0);
}
public synchronized int indexOf(Object o, int index) {if (o null) {//要查找的元素是null值for (int i index ; i elementCount ; i)if (elementData[i]null)//如果是null值用null判断return i;} else {//要查找的元素是非null值for (int i index ; i elementCount ; i)if (o.equals(elementData[i]))//如果是非null值用equals判断return i;}return -1;
}//方法removeElementAt()
public synchronized void removeElementAt(int index) {modCount;//判断下标的合法性if (index elementCount) {throw new ArrayIndexOutOfBoundsException(index elementCount);}else if (index 0) {throw new ArrayIndexOutOfBoundsException(index);}//j是要移动的元素的个数int j elementCount - index - 1;//如果需要移动元素就调用System.arraycopy进行移动if (j 0) {//把index1位置以及后面的元素往前移动//index1的位置的元素移动到index位置依次类推//一共移动j个System.arraycopy(elementData, index 1, elementData, index, j);}//元素的总个数减少elementCount--;//将elementData[elementCount]这个位置置空用来添加新元素位置的元素等着被GC回收elementData[elementCount] null; /* to let gc do its work */
}
7.3 链表LinkedList
Java中有双链表的实现LinkedList它是List接口的实现类。
LinkedList是一个双向链表如图所示 7.3.1 链表与动态数组的区别 动态数组底层的物理结构是数组因此根据索引访问的效率非常高。但是非末尾位置的插入和删除效率不高因为涉及到移动元素。另外添加操作时涉及到扩容问题就会增加时空消耗。 链表底层的物理结构是链表因此根据索引访问的效率不高即查找元素慢。但是插入和删除不需要移动元素只需要修改前后元素的指向关系即可所以插入、删除元素快。而且链表的添加不会涉及到扩容问题。
7.3.2 LinkedList源码分析
jdk1.8.0_271中
//属性
transient NodeE first; //记录第一个结点的位置
transient NodeE last; //记录当前链表的尾元素
transient int size 0; //记录最后一个结点的位置//构造器
public LinkedList() {
}//方法add()相关方法
public boolean add(E e) {linkLast(e); //默认把新元素链接到链表尾部return true;
}void linkLast(E e) {final NodeE l last; //用 l 记录原来的最后一个结点//创建新结点final NodeE newNode new Node(l, e, null);//现在的新结点是最后一个结点了last newNode;//如果lnull说明原来的链表是空的if (l null)//那么新结点同时也是第一个结点first newNode;else//否则把新结点链接到原来的最后一个结点的next中l.next newNode;//元素个数增加size;//修改次数增加modCount;
}//其中Node类定义如下
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;}
}
//方法获取get()相关方法
public E get(int index) {checkElementIndex(index);return node(index).item;
} //方法插入add()相关方法
public void add(int index, E element) {checkPositionIndex(index);//检查index范围if (index size)//如果indexsize连接到当前链表的尾部linkLast(element);elselinkBefore(element, node(index));
}NodeE node(int index) {// assert isElementIndex(index);/*index (size 1)采用二分思想先将index与长度size的一半比较如果indexsize/2就只从位置0往后遍历到位置index处而如果indexsize/2就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历。*///如果indexsize/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;}
}//把新结点插入到[index]位置的结点succ前面
void linkBefore(E e, NodeE succ) {//succ是[index]位置对应的结点// assert succ ! null;final NodeE pred succ.prev; //[index]位置的前一个结点//新结点的prev是原来[index]位置的前一个结点//新结点的next是原来[index]位置的结点final NodeE newNode new Node(pred, e, succ);//[index]位置对应的结点的prev指向新结点succ.prev newNode;//如果原来[index]位置对应的结点是第一个结点那么现在新结点是第一个结点if (pred null)first newNode;elsepred.next newNode;//原来[index]位置的前一个结点的next指向新结点size;modCount;
}//方法remove()相关方法
public boolean remove(Object o) {//分o是否为空两种情况if (o null) {//找到o对应的结点xfor (NodeE x first; x ! null; x x.next) {if (x.item null) {unlink(x);//删除x结点return true;}}} else {//找到o对应的结点xfor (NodeE x first; x ! null; x x.next) {if (o.equals(x.item)) {unlink(x);//删除x结点return true;}}}return false;
}
E unlink(NodeE x) {//x是要被删除的结点// assert x ! null;final E element x.item;//被删除结点的数据final NodeE next x.next;//被删除结点的下一个结点final NodeE prev x.prev;//被删除结点的上一个结点//如果被删除结点的前面没有结点说明被删除结点是第一个结点if (prev null) {//那么被删除结点的下一个结点变为第一个结点first next;} else {//被删除结点不是第一个结点//被删除结点的上一个结点的next指向被删除结点的下一个结点prev.next next;//断开被删除结点与上一个结点的链接x.prev null;//使得GC回收}//如果被删除结点的后面没有结点说明被删除结点是最后一个结点if (next null) {//那么被删除结点的上一个结点变为最后一个结点last prev;} else {//被删除结点不是最后一个结点//被删除结点的下一个结点的prev执行被删除结点的上一个结点next.prev prev;//断开被删除结点与下一个结点的连接x.next null;//使得GC回收}//把被删除结点的数据也置空使得GC回收x.item null;//元素个数减少size--;//修改次数增加modCount;//返回被删除结点的数据return element;
}public E remove(int index) { //index是要删除元素的索引位置checkElementIndex(index);return unlink(node(index));
}
启示与开发建议
1、Vector基本不使用了
2、ArrayList底层使用数组结构查找和添加尾部添加操作效率高时间复杂度为O(1)。 删除和插入操作效率低时间复杂度 为O(n)。 LinkedList底层使用双向链表结构删除和插入操作效率高时间复杂度为O(1)。 查找和添加尾部添加操作效率高时间复杂度为O(n有可能添加操作是O(1)
3、在选择了ArrayList的前提下new ArrayList()底层创建长度为10的数组。
如果开发中大体确认数组的长度则推荐使用ArrayList(int capacity)这个构造器避免底层的扩容、复制数组的操作。
