更新时间:2020-07-08 来源:黑马程序员 浏览量:
ArrayList底层数据结构是一个数组,查询元素速度快,增删速度稍慢
3.空参构造方法初始化
public ArrayList() { //实际大小为{},长度为0的数组 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }说明: ArrayList无参构造方法初始化时,默认大小是空数组,并不是大家常说的10,
4、第一次添加元素扩容原理
public boolean add(E e) { //确保数组大小是否足够,不够执行扩容,size为当前数组的大小 ensureCapacityInternal(size + 1); // Increments modCount!! //直接把元素e保存到数组中 elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { //如果是空数组{} if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //在最小容量minCapacity和DEFAULT_CAPACITY(10)选择一个较大的值 return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { //记录修改次数 modCount++; //如果我们期望的最小容量>数组目前的长度就扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //oldCapacity >> 1: 是把oldCapacity/2的意思 int newCapacity = oldCapacity + (oldCapacity >> 1); //如果扩容后的值<我们期望的值,扩容后的值等于我们期望的值 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //如果扩容后的值>jvm所能分配的数组的最大值,那么就用Integer的最大值 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); //通过复制数组扩容 elementData = Arrays.copyOf(elementData, newCapacity); }
LinkeList集合
1.数据结构特点:
LinkedList底层数据结构是一个双向链表,链表中的每个节点都可以查找前一个节点或者向后查找后一个节点
2.几个概念:
(1)链表每个节点叫做Node,Node有prev属性,代表前一个节点的地址,next属性代表后一个节点的地址3.链表中的元素(节点)叫做Node,是LinkedList集合的私有静态内部类,代码如下:
private static class Node<E> { E item;//节点数据 Node<E> next;//下一个节点的地址 Node<E> prev;//前一个节点的地址 //初始化参数顺序是: 前一个节点地址,节点本身的数据,后一个节点地址 Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
4.add添加节点(从链表尾部添加)
public boolean add(E e) { linkLast(e); return true;//链表节点数据可以重复,所以add方法始终返回true } //从尾部添加节点 void linkLast(E e) { //把尾节点地址存储在l中 final Node<E> l = last; //创建新的节点,参数含义如下 //l是新节点的前一个节点的地址,当前值是尾节点地址值 //e是当前新增节点中保存的数据,当前新增节点的下一个节点是null,因为是在末尾添加 final Node<E> newNode = new Node<>(l, e, null); //last指向新增节点(新增节点作为尾节点) last = newNode; //如果链表为空(第一次添加节点)(l是尾节点,尾节点为空,链表即空),头部和尾部都是指向同一个节点,都是新建的节点 if (l == null) first = newNode; else //链表不是空(非第一次添加节点),把添加新节点之前的尾节点的下一个节点指向新添加的节点 l.next = newNode; //节点数+1 size++; //链表的实际修改次数+1 modCount++; }
5.get(int index)查询节点
public E get(int index) { checkElementIndex(index);//检查索引值是否越界 return node(index).item; } private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isElementIndex(int index) { return index >= 0 && index < size; }
Node<E> node(int index) { //如果index处于链表的前半部分,从头开始查,size>>1 是 size/2的意思 if (index < (size >> 1)) { Node<E> x = first; //知道for循环到index的前一个node停止 for (int i = 0; i < index; i++) x = x.next; return x; } else { //如果index处于链表的后半部分,从尾开始查 Node<E> x = last; //知道for循环到index的后一个node停止 for (int i = size - 1; i > index; i--) x = x.prev; return x; } }