ArrayList、Vector、LinkedList解析

01Vector前言

Vector的底层也是由Object类型的数组，其类图参考ArrayList源码解析,Vector这样的同步容器的所有公有方法全都是synchronized的。

Vector主要属性：

elementData：ArrayList内部结构，是一个Object[]类型的数组
elementCount元素个数
capacityIncrement自动扩容时增加的容量

protected Object[] elementData;
protected int elementCount;
protected int capacityIncrement;

Vector构造方法：

// 默认容量为10,自增容量为0的空vector
public Vector() {
        this(10);
    }

// 指定容量和自增容量的空vector
public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

//指定容量且自增容量为0的空vector
public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }

//使用指定的Collection构造vector
public Vector(Collection<? extends E> c) {
        elementData = c.toArray();
        elementCount = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
    }

02Vector正文

Vector是线程安全版本的ArrayList，基本上增删改查都是用关键synchronized进行修饰，可用于多线程。

Vector查找同样用synchronized变量修饰按照下标去查找元素

Vector新增add操作跟ArrayList一个重要的不同就是通过synchronized进行了修饰保证线程安全，其他跟ArrayList保持一致

Vector移除remove操作也通过synchronized进行修饰，其他的remove动作和ArrayList是一致的

Vector扩容默认size的初始大小为10，加载因子为1(当元素个数超过总量时就进行扩容)，扩充为原来大小的2倍

性能上的差别，由于vector的方法都有同步锁，在方法执行时需要加锁、解锁，所以在执行过程中效率会低于ArrayList，而ArrayList线程不安全但查询速度快。

CopyOnWriteArrayList作为代替Vector生成线程安全的ArrayList。

03LinkedList前言

LinkedList主要属性：

链表的节点个数
指向头节点的指针
指向节点的指针

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

它允许插入所有元素，包括 null。

Node 是在 LinkedList 里定义的一个静态内部类，它表示链表每个节点的结构，包括一个数据域 item，一个后置指针 next，一个前置指针 prev。

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

04LinkedList正文

LinkedList新增：

在表头添加元素的过程如下

当向表头插入一个节点时，很显然当前节点的前驱一定为 null，而后继结点是 first 指针指向的节点，当然还要修改 first 指针指向新的头节点。除此之外，原来的头节点变成了第二个节点，所以还要修改原来头节点的前驱指针，使它指向表头节点。

在表头添加元素的过程如下

当向表尾插入一个节点时，很显然当前节点的后继一定为 null，而前驱结点是 last指针指向的节点，然后还要修改 last 指针指向新的尾节点。此外，还要修改原来尾节点的后继指针，使它指向新的尾节点

在指定节点之前插入，如图所示

当向指定节点之前插入一个节点时，当前节点的后继为指定节点，而前驱结点为指定节点的前驱节点。此外，还要修改前驱节点的后继为当前节点，以及后继节点的前驱为当前节点。

05ArrayList与LinkedList对比

ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
对于随机访问get和set，ArrayList优于LinkedList，因为ArrayList可以随机定位，而LinkedList要移动指针一步一步的移动到节点处。
对于新增和删除操作add和remove，LinedList比较占优势，只需要对指针进行修改即可，而ArrayList要移动数据来填补被删除的对象的空间。

应用场景：

ArrayList 使用查询比较多的时候，但是插入和删除比较少的情况下，而LinkList 使用查询比较少而插入和删除比较多。

网站首页 > 技术文章正文

猜你喜欢

网站首页 > 技术文章 正文

ArrayList、Vector、LinkedList解析

猜你喜欢

网站首页 > 技术文章正文