0%

Android中的List简要

发表于 更新于 分类于

ArrayList简要

ArrayList 是实现了List、RandomAccess的顺序表，当容量不足时会自动扩容

特点：访问元素效率较高，操作元素效率低（每次add remove都会对整个表进行操作）

初始化

1
2
3
4
// 可自定义初始化储存数据的数组长度
ArrayList(initialCapacity)
// 使用默认数组长度，默认长度为0
ArrayList()

扩容机制

  1. 首次未设置数组长度时: 当执行add*添加数据会创建一个10个长度的数组
  2. 再次扩容：当执行add*时会检查是否有足够空间，没有的话则增加当前长度的一半n/2
  3. 减容：当执行remove*时，先获取数组当前位置的数据，整个数组从当前位置向前移动补位，
    置空数组后面的数据。（这里有个问题：减少容量时ArrayList里的数组长度没有减少，意味着数据长度只增不减）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // 每次执行  add*  时会进行数组长度校验，如果数组长度不够则会添加原长度的 n/2
    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);
    }

线程安全问题

  1. 使用CopyOnWriteArrayList加锁的顺序列表
  2. 使用Collections#synchronizedList

LinkedList简要

LinkedList是实现了List``Deque的队列双向链表，每个节点包含了数据，上一节点和下一节点的信息，容量是动态非连续的

特点：插入、删除较快，不需要移动数据，只移动节点信息就可以了

初始化 LinkedList()

扩容机制 动态随数据长度

Vector简要

与ArrayList相似，区别：线程安全，可自定义每次扩容大小

Stack简要

继承Vector，线程安全，实现栈的功能

常用线程安全的 List,Set

  1. CopyOnWriteArraySet 获取的iterator()不支持remove set add操作
  2. CopyOnWriteArrayList 获取的iterator()不支持remove set add操作
  3. SynchronizedRandomAccessList 通过Collections#synchronizedList获取
  4. SynchronizedList 通过Collections#synchronizedList获取

综合对比

  • ArrayList的操作数据都是通过普通的数组实现，随机访问和修改元素比较快，但插入/删除等操作需要移动较多数据，比较适合在访问数据比较频繁的场景使用
  • LinkedList是双向链表，在随机访问和修改都需要先去查找节点，但是在插入/删除数据时不需要移动数据，比较适合用在插入/删除频繁的场景中。
  • LinkedList还实现了队列接口，通过头或尾进行顺序访问的同时可以删除节点，充分发挥了链表的优势。
  • Vector与Stack实现的线程安全，但也降低的效率