List集合及其实现类

List集合及其实现类

• java集合
• Cllection接口
• • List列表
  • • 相应实现类源码分析
    • • ArrayList
      • LinkedList
      • ArrayList和LinkedList优缺点
      • Vector
    • List常用方法

java集合

java容器

即集合、数组都是对多个数据进行存储操作的结构

数组的缺点

1. 一旦初始化，其长度不可更改
2. 对于增删等操作不方便
3. 数组一旦定义，其元素类型就确定了，不可更改

集合

集合是存放数据对象引用的容器，集合可以避免数组的以上缺点

常见的集合

List列表，Set集合，Map映射

Cllection接口

Collection接口是集合类的根接口，Java中没有提供这个接口的直接的实现类。却让其被继承，所以产生了两个接口，就是Set和List

List列表

鉴于java用数组存储数据的局限性，通常用List替代数组

List集合类中元素有序、且可重复，集合中每个元素都有对应的顺序索引，List集合允许加入重复元素，因为它可以通过索引来访问指定位置的集合元素。List集合默认按元素的添加顺序设置元素的索引
List常用实现类：
        |--ArrayList：作为List接口的主要实现类;线程不安全，效率高; 底层使用Object[] elementDate存储
        |--LinkedList：对于频繁的插入、删除操作使用效率比ArrayList高;底层使用双向链表存储
        |--Vector：作为List接口的古老实现类;线程安全的，效率低;底层使用Object[] elementDate存储

相应实现类源码分析

ArrayList

//默认初始的容量
private static final int DEFAULT_CAPACITY = 10;
//存储元素的数组，实际上是一个动态数组，如果有参构造(new ArrayList(int initialCapacity))则其初始容量为initialCapacity,如果无参构造(new ArrayList())则其初始容量为10
transient Object[] elementData; 
//数组元素的个数
private int size;

扩容

//插入元素的函数
public boolean add(E e) {
		//增加长度
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //添加元素到数组
        elementData[size++] = e;
        return true;
    }
private void ensureCapacityInternal(int minCapacity) {
		//如果是空参构造，则最小扩容量是10和size+1的最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
		//判断是否需要扩容
        ensureExplicitCapacity(minCapacity);
    }
 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //最小扩容量大于数组的长度则进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
 private void grow(int minCapacity) {
        // 旧容量：数组的长度
        int oldCapacity = elementData.length;
        //新容量：旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //若新容量小于最小扩容量
        if (newCapacity - minCapacity < 0)
        	//新容量等于最小扩容量
            newCapacity = minCapacity;
        //新容量大于最大值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
        	//调用hugeCapacity(minCapacity)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //原数组的元素复制到新数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

add()线程不安全情况

	//多个线程进入ensureCapacityInternal()并执行完毕,此时都不需要扩容,依次赋值时会size+1,所以从第二个开始的线程赋值时其下标很可能超过了容量值,赋值时就报错了
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 是否需要扩容
        elementData[size++] = e;//赋值
        return true;
    }

LinkedList

transient int size = 0;   //LinkedList中存放的元素个数
 
    transient Node<E> first;  //头节点
    
    transient Node<E> last;   //尾节点

//Node体现了底层是双向链表
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;
        }
    }
//add()
public boolean add(E e) {
     linkLast(e);
     return true;
}
//默认添加元素到链表的尾部
void linkLast(E e) {
	 //last尾结点指定的节点赋值给l节点
     final Node<E> l = last;
     //创建新节点，此节点的前驱指向l节点，data = e , next = null 
     final Node<E> newNode = new Node<>(l, e, null);
     last = newNode;
     //若List是否为空
     if (l == null)
         first = newNode;
     //不为空
     else
          l.next = newNode;
     size++;
     modCount++;
}

ArrayList和LinkedList优缺点

ArrayList

• 优点在于可以顺序存储，随机存取,数据元素与位置相关联，因此查找效率高，索引遍历快，尾部插入与删除的速度与LinkedList的效率相差无几。
• 线程不安全，插入与删除慢，需要通过移动元素来实现，因此效率低。

LinkedList

• 优点在于删除和添加数据所消耗的资源较少，且比ArrayList效率高
• 线程不安全，查找消耗的资源大，效率低，不能随机访问。

Vector

• Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写Vector
• 如果集合中的元素的数目大于目前集合数组的长度时，vector增长率为目前数组长度的100%,而arraylist增长率为目前数组长度
  的50%

private void grow(int minCapacity) {
    // 获取当前数组的容量
    int oldCapacity = elementData.length;
    // 扩容。新的容量=当前容量+当前容量/2.即将当前容量增加一倍(capacityIncrement:标准容量增量一般为0)
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    //如果扩容后的容量还是小于想要的最小容量
    if (newCapacity - minCapacity < 0)
        ///将扩容后的容量再次扩容为想要的最小容量
        newCapacity = minCapacity;
    ///如果扩容后的容量大于临界值，则进行大容量分配
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

List常用方法

• void add(int index,Object ele):在index位置插入ele元素
• boolean addAll(int index,Collection eles):从index位置开始将eles中所有的元素添加进来
• Object get(int index):获取指定index位置的元素
• int indexOf(Object obj):返回obj在当前集合中首次出现的位置,如果不存在则返回-1
• int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置,如果不存在则返回-1
• Object remove(int index):移除指定index位置的元素，并返回此元素
• Object set(int index,Object ele):设置指定index位置的元素为ele
• List subList(int fromInedx,int toInedx):返回从fromIndex到toIndex位置的左闭右开子集合

总结

        增:add(Object obj)
        删:remove(Object ele) , remove(int index) (要严格区分)
        改:set(int index,Object ele)
        查:get(int index)
        插:add(int inedx,Object ele)
        长度:size()
        遍历:1.Iterator迭代器
                2.增强for循环：foreach()
                3.普通循环

补充

Iterator迭代器
	Iterator对象称为迭代器(设计模式一种)，主要用于遍历Collection集合中的元素
内部方法：hashNext()和next()
1.hashNext():判断是否还有下一个元素
2.next():1.指针下移2.将下移以后集合位置上的元素返回

示例：

import java.util.ArrayList;
import java.util.Iterator;

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> integers = new ArrayList<>();
        integers.add(2);
        integers.add(3);
        integers.add(19);
        Iterator<Integer> iterator = integers.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }
}

 使用foreach循环遍历集合元素
 遍历操作不需获取Collection或数组的长度，无需使用索引访问元素
 foreach还可以用来遍历数组
 使用格式：
 for(集合元素的类型 局部变量 ：集合对象){
     System.out.println(局部变量)
  }

示例：

import java.util.ArrayList;

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> integers = new ArrayList<>();
        integers.add(2);
        integers.add(3);
        integers.add(19);
        for(Integer num : integers){
            System.out.println(num);
        }
    }
}