1.说说ArrayList

1.基本原理

ArrayList,原理就是底层基于数组来实现。

01.基本原理:

这个数组扩容+元素拷贝的过程,相对来说会慢一些

02.缺点:

01:不要频繁的往arralist里面去塞数据,导致他频繁的数组扩容,避免扩容的时候较差的性能影响了系统的运行。

02: 数组来实现,数组你要是往数组的中间加一个元素,是不是要把数组中那个新增元素后面的元素全部往后面挪动一位,所以说,如果你是往ArrayList中间插入一个元素,或者随机删除某个元素,性能比较差,会导致他后面的大量的元素挪动一个位置

03.优点:

基于数组来实现,非常适合随机读,你可以随机的去读数组中的某个元素

04.常用场景:

05.场景示例:

2.源码剖析

01.核心方法的剖析

咱们来启动一个demo工程,在里面写写集合的代码,跟进去看看各种集合的实现原理,直接可以看JDK底层的源码。

(1).示例代码:
public class ArrayListDemo {
    public static void main(String[] args) {
        ArrayList<String> sayLove =new ArrayList<String>();
       sayLove.add("老婆,早上好");
        sayLove.add("老婆,下午好");
        sayLove.add("老婆,下班啦,我去找你");
        sayLove.set(0,"老婆,早上好,我们一起吃早饭吧");
        sayLove.add(2,"老婆,注意坐姿,不要久坐哦");
    }
}
(2).构造函数分析:

默认的构造函数,直接初始化一个ArrayList实例的话,会将内部的数组做成一个默认的空数组,{},Object[],他有一个默认的初始化的数组的大小的数值,是10,也就是我们可以认为他默认的数组初始化的大小就是只有10个元素。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//空数组
​
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
​
 private static final int DEFAULT_CAPACITY = 10;//初始容量 10

注意点:

(3).add(E)方法

分析如下:

 public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

#2 ensureCapacityInternal(size + 1);:判断一下当前的数组容量是不是满了,如果满了会进行扩容;

 if (minCapacity - elementData.length > 0)
            grow(minCapacity);

1).第一次进入这个方法时,minCapacity=10,默认值,而此时底层还是个空数组,自然会进行数组的扩容。扩容代码如下:

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);
    }

通过计算,确认本次数组增加的容量就是默认大小10,然后通过Arrays.copyOf进行数组的数据拷贝和创建新数组。

#3 elementData[size++] = e;,就是将添加数据数据放到index=0的位置上,并且size+1;

2).然后就返回添加成功了。

数组的变化:

size=0,elementData={}变成了size=1,elementData=["老婆,早上好"]

依次执行三次,就完成今天的sayLove日常了。

(4).set(index,E)方法
sayLove.set(0,"老婆,早上好,我们一起吃早饭吧");

分析如下:

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

#2 rangeCheck(index);:还记得我们那些年学Java的青葱岁月吗?都得喊一嗓子:角标越界,错误就在这里了,熟悉的异常,值得的青葱岁月。

if (index >= size)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

#3 E oldValue = elementData(index);:操作很简单,返回原来位置上的值,将新值插入想插入的位置,并返回旧值。

E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
(5).add(index,E)方法
sayLove.add(2,"老婆,注意坐姿,不要久坐哦");

分析如下:

public void add(int index, E element) {
        rangeCheckForAdd(index);
​
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

#2,#4,还是熟悉的检查角标是否越界以及检查容量是否已满。

#5,调用native方法System.arraycopy,进行数组中元素的移位,参数如下所示:

index=2,size=3;

System.arraycopy(elementData, 新增的角标位=2, elementData, 往后移动的起始角标位=3,
                 要往后移动的个数=1);

#5,#6,插入新值到指定位置,size+1。

完成指定位置插入数据的操作。

(6).remove(index)方法
sayLove.remove(2);//加班,所以,不能去找媳妇了。撤回 “老婆,下班啦,我去找你” 这句话。

分析如下:

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;
    }

#7 int numMoved = size - index - 1;:numoved=4-2-1=1,要移动的个数,当前大于0,调用native方法,进行数组元素移动,System.arraycopy(elementData, 3, elementData, 2,1);,从当前数组的index=3位置,共一个元素,从index=2位置开始拷贝。

说到底,就是删除位置后的所有元素都往前移位,然后将最后位置上的元素设置为null。so easy。

2.谈谈LinkedList

1.基本原理

底层是基于链表来实现的。

01.基本原理:

02.优点:

03.缺点:

04.常用场景:

05.场景示例:

2.源码剖析

01.插入元素

在尾部插入元素、在头部插入元素、在中间插入元素

add(),默认就是在队列的尾部插入一个元素,在那个双向链表的尾部插入一个元素

add(index, element),是在队列的中间插入一个元素

addFirst(),在队列的头部插入一个元素

addLast(),跟add()方法是一样的,也是在尾部插入一个元素

(1).示例代码:
public static void main(String[] args) {
    LinkedList<String> housework=new LinkedList<String>();
    housework.add("洗菜");
    housework.add("切肉");
    housework.add("炒菜");
    housework.add(1,"给老婆倒杯水");
    }
(2).add(E)方法

分析如下:

public boolean add(E e) {
        linkLast(e);
        return true;
    }

#2 linkLast(e);:将元素直接插入到队尾代码如下:

void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

1). #2~#4: 第一次last肯定是null,创建了一个Node节点,对象结构Node<preNode,元素,next节点>;并且该节点赋值给了last变量。

2). #5~#8: 第一次last节点是null,所以first节点也被赋值成创建的node节点。而如果是第二次进行add操作的话,就是会将新的Node节点挂在到前一个Node节点的next节点上去。

3).size+1,操作成功。

(3).add(index,E)方法
housework.add(1,"给老婆倒杯水");

分析如下:

public void add(int index, E element) {
        checkPositionIndex(index);
​
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

#2 checkPositionIndex(index);:对于指定位置的插入数据,我们都是需要进行角标是否越界的检查的;

 private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
 }

#4-#7:如果正好是最后一个位置,就直接插入到队尾;

如果不是,就要进行指定位置的插入,这里走的是这个分支。

 void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

1).先根据index获取到之前位置的node;

2).#3~#5: 1. 新创建一个Node,新Node的pre节点设置为原Node节点的pre节点,next节点设置为原node节点。

  1. 将原来的Node节点的pre节点设置为新Node节点。

2).#6~#9:如果原节点的pre节点是null,就把新Node节点设置为first节点;

否则就是将原Node节点的next节点设置为新创建Node节点。

3).size+1,然后就返回添加成功了。

02.获取元素

(1).get(index)方法

示例代码:

public static void main(String[] args) {
        LinkedList<String> loveStory=new LinkedList<String>();
        loveStory.add("看电影");
        loveStory.add("去野餐");
        loveStory.add("摩天轮");
        loveStory.add("去海边");
        loveStory.get(2);
    }

我们来分析这一行代码:

 loveStory.get(2);

分析如下:

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

#2 checkElementIndex;:角标是否越界的检查。

private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

#3 node(index);:这里就极为关键了,LinkedList底层是如何遍历查找指定位置的元素呢?来看如下分析:

 Node<E> node(int index) {
        // assert isElementIndex(index);
​
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

#4~#6

1).size/2,取了中间数,然后判断我们要找的位置是在中间数的前部分还是后部分。

如果是前半部分就从first节点开始往后查找,

如果是后半部分,就从last节点开始往前查找,有点二分法查找的感觉。

2).我们这里index=2, 2>2不成立,走else分支,然后,我们可以看到他通过一个for循环进行遍历,从最后一个节点开始,每次都查找Node节点的prev节点,直到index+1的位置时,就跳出循环了,而index+1节点的prev节点不正是我们要获取的index节点么?完美!

03.删除元素

(1).get(index)方法

示例代码:

public static void main(String[] args) {
        LinkedList<String> loveStory=new LinkedList<String>();
        loveStory.add("看电影");
        loveStory.add("去野餐");
        loveStory.add("摩天轮");
        loveStory.add("惹老婆生气");
        loveStory.add("去海边");
        loveStory.get(2);
    }

我们来分析这一行代码:

loveStory.remove(2);

分析如下:

public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

#2 checkElementIndex;:角标是否越界的检查。

private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

#3 unlink(node(index));:先遍历找到index对应的Node节点,然后进行删除工作。

 E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
​
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
​
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
​
        x.item = null;
        size--;
        modCount++;
        return element;
    }

#3~#5:获取index对应的Node节点的prev节点和next节点;

#7~#12:如果prev节点为null,就把Node节点的next节点设置为first节点;

否则就将prev节点的next节点设置为Node节点的next节点。

#14~#19:如果next节点为null,就把Node节点的prev节点设置为last节点;

否则就将next节点的prev节点设置为Node节点的prev节点。

#21~#24:将node节点的值设置为null,size-1,最终返回原来Node的元素值。

3).对比总结

最后谢谢大家阅读,有不足之处欢迎指出。

03-06 15:16