03

guduadmin211月前

文章目录

list接口
- list的API
- listIterator方法
- subList方法
- ArrayList
- - ArrayList的源码阅读
  - LinkedList
  - Vector
  - Stack
    
    list接口
    
    特点：
    - List是Collection的子接口，是描述数据存储的接口
    - 数据结构表现为线性表，可以通过下标来操作
    - 存储数据有序
    - 可以存储重复元素
    - 可以存储null
      list的API
      - List是Collection的子接口。所有肯定有Collection的所有方法。
      - 相对于Collection，list多了一种遍历的方法fori。（因为有了get(index)这种方法）
        void add(int index, E element)：// 在指定位置添加元素。list添加的位置，只能在[0,length]之间 boolean addAll(int index, Collection c)：// 在指定位置添加一个Collection的所有元素 E remove(int index)：// 删除指定下标的元素，只能删除下标的位置[0, length-1]。返回的是删除的元素 E set(int index, E element)：// 设置指定下标的元素为element E get(int index)：// 获取指定下标元素 int indexOf(Object o)：// 获取元素的首个index // 如果这个元素不存在，就会返回-1 int lastIndexOf(Object o)：// 获取元素的最后一个index ListIterator listIterator()： ListIterator listIterator(int index) List subList(int fromIndex, int toIndex)
        
        面向接口编程：
        一般都是拿接口去接取对象，而不是拿实现类去接取对象，因为可以方便之后的替换。
        
        listIterator方法
        
        返回一个ListIterator的对象。这个与迭代器（只能向后移动）类似，只是可以前后移动，可以返回index。
        
        有参构造，返回的迭代器对象，调用next返回的是指定下标的元素。
        传入的index的范围是：[0,length]
        public interface ListIterator extends Iterator ------------------------------------------------------------- 继承迭代器的方法： boolean hasNext() : // 判断后面是否还有元素可以遍历 E next() : // 向后遍历 void remove() : // 删除刚刚遍历的数据 ------------------------------------------------------------- ListIterator的方法： boolean hasPrevious(): // 向前是否可以遍历 E previous(): // 向前遍历 int nextIndex() : // 向后遍历的数据的下标 int previousIndex() : // 向前遍历的下标 void add(E e) : // 添加一个数据到当前遍历位置 // 1. zs ls ww // | // 2. listIterator.add("zl"); // zs zl ls ww // | void set(E e) : // 修改刚刚遍历过的元素位置 // 可以连续set // 1. zs ls ww // | // 2. listIterator.set("zl"); // zl ls ww // |
        
        注：如果我们想逆序遍历，可以list.listIterator(list.size());
        
        subList方法
        
        从原有的集合中截取一部分。
        返回值为[fromIndex , toIndex)
        subList是生成的一个映射。这个生成的subList操作就是对原有集合的操作
        会出现并发修改异常的问题。
        当生成了subList之后，如果再修改原集合。再访问subList的对象，会报错。
        Q：subList是不是把原有的集合截取了一个，产生一个新的数组呢？
        A：subList只是一个引用，只是一个地址。
        
        ArrayList
        
        特点：
        
        ArrayList是List的子实现
        ArrayList数据结构表现为线性表
        底层结构是数组
        存储元素，有序
        可以存储重复元素
        可以存储null
        构造方法：
        
        注：size()其实不是数组的大小，是存储元素的个数
        
        ArrayList的API：
        
        Object clone() // 返回此 ArrayList 实例的浅表副本。 void ensureCapacity(int minCapacity) // 如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数。 void trimToSize() // 将此 ArrayList 实例的容量调整为列表的当前大小。
        
        注意事项：
        
        浅表副本
        String类型不能修改
        arrayList.ensureCapacity(10);
        其实就是比较传过来的数字和当前elementData的大小
        如果传过来的数字小，则不会做任何事情
        如果传过来的数字大，会把数组长度变大
        ArrayList的源码阅读
        
        初始的容量：10
        扩容：按照原来容量的1.5倍进行扩容
        
        (流程图)
        
        class ArrayList { // 最终存放数据的地方 Object[] elementData; // 存放数据的地方 private int size; private static final int DEFAULT_CAPACITY = 10; // 默认是空的，起到占位的作用 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; } public boolean add(E e) { // 1 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; if (minCapacity - elementData.length > 0) // grow是用来扩容的 grow(minCapacity); } private void grow(int minCapacity) { // oldCapacity = 0 int oldCapacity = elementData.length; // newCapacity = oldCapacity * 1.5 int newCapacity = oldCapacity + (oldCapacity >> 1); // 0 - 10 < 0 if (newCapacity - minCapacity < 0) // newCapacity = 10 newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 相当于给elementData赋值了一个长度为10的数组 elementData = Arrays.copyOf(elementData, newCapacity); } }
        
        注意事项：
        
        构造方法里面没有初始化 —> 添加的时候必须进行初始化（add）
        什么时候会扩容 —> 不断调用add方法的时候，会装不下的时候
        
        LinkedList
        
        特点：
        
        LinkedList是List的子实现
        LinkedList数据结构表现为线性表
        LinkedList底层双向链表。
        存储元素有序
        可以存储重复
        可以存储null
        Q：链表的特点是插入和删除快，是真的吗？
        A：查找也需要时间（max(O(n)), O(1))），所以算起来和ArrayList类似。不建议大家把它当List使用，当成Deque接口来用。
        
        构造方法：
        
        Vector
        
        特点：
        
        Vector是List的子实现
        Vector的数据结构表现是线性表
        底层结构是数组
        存储的数据有序，可重复，可存储null
        线程安全
        注意事项：
        
        线程安全：
        
        当多个线程同时对一个变量进行操作时，结果的预期与单线程下是一致的。这就是线程安全的。
        比如多个线程对i进行操作，i初始值是0，有5个线程，每个线程累加10000次。最终结果应该是50000。但真实情况不是这样的，这就是线程安全问题。
        为什么vector会被弃用？
        
        效率低。
        在所有的接口上都加了synchronized关键字。线程安全是没问题了，但是效率却有问题。因为绝大部分都不涉及到多线程情况，所以jdk1.2采用了ArrayList来替代Vector
        Q：ArrayList和Vector的区别？
        A：
        1.两个都是线性表，都是List的子实现，底层都是数组。
        2.存储数据都是有序，允许重复，允许存储null
        3.ArrayList是线程不安全的，Vector是线程安全的
        4.扩容机制不同。ArrayList初始容量10,扩容1.5倍。Vector初始容量10，扩容2倍。
        
        Stack
        
        特点：
        
        Stack是Vector的子实现
        栈，是先进后出的数据容器。但是不建议使用这个来完成，效率是大问题。使用Deque来替代Stack
        Deque接口及其实现提供了一组更完整的和一致的LIFO堆栈操作，应当优先使用此类