java源码学习

Java源码学习--ArrayList、LinkedList、V

2019-06-02  本文已影响0人  慕北人

Java源码学习--ArrayList、LinkedList、Vector比较

在进行三个的总结之前，还有一个需要了解一下的就是Stack这个类。

一、Stack

这个类继承了Vector，而且该类只是提供了栈操作的方法，没有其他任何的东西：

public class Stack<E> extends Vector<E> {

public Stack() {
}

public E push(E item) {
    addElement(item);

    return item;
}

public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

public synchronized E peek() {
    int     len = size();

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

public boolean empty() {
    return size() == 0;
}

public synchronized int search(Object o) {
    int i = lastIndexOf(o);

    if (i >= 0) {
        return size() - i;
    }
    return -1;
}

private static final long serialVersionUID = 1224463164541339165L;

}

二、ArrayList、LinkedList、Vector比较

1. ArrayList

1.1 add方法

ArrayList的add系列的方法的实现逻辑为：

由于ArrayList中维护的是一个数组，而数组根据下标的操作的时间复杂度都是O(1)所以ArrayList的add方法几乎是没有耗时的，当调用在指定位置添加的方法时由于需要把index后面的元素向后移动一格而调用了System.arraycopy方法，会产生一些耗时,当遇到需要扩容时由于执行了Arrays.copyof方法，此时需要一些耗时

1.2 addAll方法

ArrayList的addAll系列方法的实现逻辑为：

在ArrayList的addAll方法中，和add相比，多执行了一次System.arraycopy方法，多出的耗时就是在这里。

1.3 remove方法

ArrayList的remove(int index)方法实现逻辑为：

可见ArrayList的删除执行位置的方法，唯一耗时的就是向前移动元素。

ArrayList的remove(Object o)方法的实现逻辑为：

直接删除对象的方法更加耗时，原因就在于多了一个for来寻找被删除对象的位置。

ArrayList中还有一个removeAll的方法，其作用是将参数集合中所有的元素都从ArrayList中删除；该方法效率很低下，就是对于参数中的每一个元素ArrayList都要调用contains方法来判断是否含有该元素，关键是contains方法的实现就是一个for循环遍历ArrayList中是所有元素，所以removeAll的复杂度为O(n^2)

1.4 get和set方法

ArrayList的get和set就是一个数组根据下标来查找元素的方法，所以没任何毛病；不过发扬传统，在执行数组的写和读的操作之前还是要检查一下index的合法性问题。

2. LinkedList

2.1 add方法

LinkedList的add方法就是一个双向链表的插入方法，其逻辑为：

LinkedList方法的插入和ArrayList相比会慢一些，首先是节点的插入肯定比不上数组根据下标进行读写，其次是虽然指定添加位置时ArrayList需要将index后面的元素拷贝一下，但是LinkedList中却需要找到index位置的节点，所以前者耗时在后续数据的移动，而后者耗时在index位置节点的获取，这么一比还是ArrayList占据了上风；但是LinkedList有一个优点就是没有需要扩容的情况。

2.2 addAll方法

LinkedList的addAll方法的逻辑为：

额，这个方法好像没啥好说的。

2.3 remove方法

LinkedList的remove(Object o)方法的实现逻辑是：

可见该方法和ArrayList相比在找该对象时使用的都是for循环，在这一步上是势均力敌的(ArrayList稍微领先)，包括数据的删除都是ArrayList要由于LinkedList；但是ArrayList在删除数据之后还要把后面的数据整体向前移动一个位置，而LinkedList则没有这一步。

LinkedList的remove(int index)方法的实现逻辑是：

LinkedList的该方法和ArrayList相比就没有多大的优势了，因为ArrayList通过index删除时根本不需要通过for循环，直接一个数组的根据下标操作数据秒杀LinkedList，但是ArrayList还是有一个后续数据的前移的工作要做，因此这个方法ArrayList以微弱优势取胜。

2.4 get和set方法

LinkedList的get和set方法就都很惨了，因为只要涉及到指定了位置index，那LinkedList就只能通过for遍历来找到，所以这里相较于ArrayList直接通过数组的下标操作数据，LinkedList通过for循环找到数据变完全被秒杀了。

3. Vector

由于Vector和ArrayList几乎是一样的实现，这里就不在进行对比了。

三、总结

看完了List系列的源代码，虽然这些源代码确实很简单易懂，但是还是有很多能够学习的：

上一篇下一篇

猜你喜欢

热点阅读