List集合

• Collection介绍
• Collection的遍历
• Vector
• ArrayList
  • 概述
  • 继承关系
  • 底层数据结构
  • 增删改查
  • modCount
• Stack
• LinkedList
  • 概述
  • 增删改查
• Queue
  • DeQueue

Collection

java的集合主要按两种接口分类:

• set
• map

Collection是一个接口,主要有两个分支,List和Set.
List和Set都是接口,继承与Collection.List是有序的队列,List中可以有重复的元素,Set是数学概念中的集合,没有重复的元素.

Collection介绍

1. 集合的特点:
   • 集合中存储的元素是对象.
   • 集合的长度是可变的.
   • 集合不可以存储基本数据类型.
2. 集合是用于存储对象的容器,而每种容器内部都有其独特的数据结构,正因为不同的容器内部数据结构不同,使其有自己的使用场景,虽然每个容器都有其独特的结构,但是类似的容器还是存在共性的,所以这些共性方法被不断抽取,最终形成了集合框架体系.
3. 与数组的区别: 元素的类型可以不一致,长度可变.
4. 从继承关系和源码分析: Collection继承了Iterator接口.在java1.8中包含了18个方法.
   • add(E e) 返回值是boolean
   • addAll(Collection<? extends E> c) 返回值是boolean.
   • clear() 返回值是void
   • contains(object o) 如果包含返回为true
   • contains(Collection<? extends E> c) 包含集合c返回true
   • equals(object o)
   • hashCode 返回值是int,返回哈希码
   • isEmpty() 如果为空返回true
   • itreator() 返回迭代器
   • remove(object o)返回类型是boolean
   • removeIf(Predicate<? super E> filter) 删除满足条件的元素
   • removeAll(Colletion<?> c) 删除包含集合c的所有元素
   • size() 返回类型是int
   • toArray().返回值是object[] ,将集合转换为数组
   • stream() 返回类型是stream 返回顺序流
   • spliterator() 分割迭代器,1.8加入的可并行迭代

Collection的遍历

1. for循环遍历
2. 迭代器遍历

Iterator<String> it=Collection.iterator();
while(it.hasNext()){
System.out.println(it.next());
}

Vector

底层数组不被transient修饰,序列化时会全部复制. 继承了AbstractList,实现了List,RandomAccess,Cloneable,Serialiazable

1. 线程安全
2. 可以指定增长因子,如果增长因子制定了,扩容的时候每次新的数组大小会增加,否者就原数组大小*2;

int newCapacity=oldCapacity+((capacityIncrement>0)? capacityIncrement:oldCapacity);

ArrayList

概述

ArrayList是实现List接口的动态数组,所谓动态就是说它的大小是可变的.
每次添加新元素时,ArrayList都会检查是否需要进行扩容操作,扩容操作带来的数据向新数组重新拷贝.如果我们知道业务的数据量,可以在构造ArrayList时给一个初始容量,可以相应的减少扩容时数据拷贝的问题.

继承关系

继承了AbstractList,实现了List,RandomAccess,Cloneable,Serialiazable

底层数据结构

ArrayList底层是一个Object数组,并且由trasient修饰

transient Object[] elementData;

底层数组不会参与序列化,而是使用另外的序列化方式.使用writeObject方法进行序列化.只复制数组中有值得位置,其他未赋值的位置不进行序列化,节省空间.

增删改查

• 添加元素时,首先判断索引是否合法,然后检测是否需要扩容,最后使用system.arraycopy()方法来完成数组的复制.
• 删除元素时,首先判断索引是否合法,删除的方式是把被删除元素右边的元素左移,也是使用system,arraycopy方法拷贝.
• ArrayList提供一个清空数组的方法,方法是将所有元素设置为null,就可以让GC自动回收掉没有被引用的元素.
• 修改元素时,只需要检查下标即可进行修改操作.

modCount

Fail-Fast机制
通过modCount域,modCount代表修改次数,对ArrayList内容的修改都将增加这个值,在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount.
在迭代过程中,判断modCount跟expectedModCount是否相等,如果不相等,就表示已经有其他线程修改了.

1. 线程不安全.
2. 默认初始容量10
3. 本质上是一个可改变大小的数组,元素顺序存储,随机访问快,删除头元素慢,新增元素慢切浪费资源,如果不是需要可变数组,建议使用数组.
4. 扩容为原来的1.5倍

Collections.synchronizedList()方法可以把ArrayList变成线程安全的List

Stack

继承了Vector类. 通过五个操作对Vector进行了扩展

• empty 判断栈是否为空
• peek() 查看栈顶的对象,但不移除
• pop() 查看栈顶的对象并返回,移除对象
• push(E item) 把项压入栈顶部
• search(Object o) 返回对象在栈中的位置,以1为基数

LinkedList

概述

LinkedList与ArrayList一样实现List接口,LinkedList是List接口链表的实现,基于链表实现的方式使得LinkedList在插入和删除时优于ArrayList.而随机访问则比ArrayList逊色.

LinkedList类还为列表的开头结尾get,remove和insert元素提供了统一的命名方法.这些操作允许将链表用作堆栈,队列或双端队列.

增删改查

添加方法

• add(E e) 将指定元素添加到此列表的末尾,调用了addBefore()方法

public boolean add(E e){
	addBefore(e,header);
	return true;
}

addBefore方法构建一个新节点,修改entry.previous和entry.next
还提供了很多方法

• addLast() 添加到末尾
• addFirst() 添加到开头
• add(int index,E e);指定位置添加

移除方法

• remove(Object o) 移除列表中首先出现的指定元素

public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

• remove();获取并移除此列表的头(第一个元素)
• clear();删除所有元素
• removeFirst();删除第一个元素
• removeLast();删除最后一个元素

Queue

Queue定义了队列数据结构,元素时有序的,先进先出.

DeQueue

是接口,继承了Queue接口,创建双向队列,更灵活,可以双向迭代,队头队尾添加数据.LinkedList就实现了DeQueue.