【Java】集合（一）单列集合List

1.集合

可以动态保存任意多个对象，并提供了一系列的操作对象的方法：add、remove、set、get等。

2.集合框架体系

分为两大类：

单列集合和双列集合

3.List接口基本介绍

List接口是Collection接口的子接口

List集合类中元素有序，可重复，支持索引，List容器中的元素都对应一个整数型的序号，可以根据序号存取容器中的元素。

List 集合里添加了一些根据索引来操作集合元素的方法

1) void add(int index,Obiect ele):在index位置插入ele元素

2）boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来

3）Object get(int index):获取指定index位置的元素

4）int indexof(Obiect obi):返回obi在集合中首次出现的位置

5）int lastlndexof(Obiect obi):返回obi在当前集合中未次出现的位置

6）Object remove(int index):移除指定index位置的元素，并返回此元素

7）Object set(int index, Object ele):设置指定index位置的元素为ele相当于是替换

8）List subList(int fromIndex, int tolndex):返回从fromIndex到tolndex位置的子集合

例子

	    List list=new ArrayList();
        //插入
        list.add(100);
        list.add(3);
        list.add("a");
         System.out.println(list);
        //删除
         list.remove(1);//默认按索引删除,索引从0开始
        list.remove(new Integer(100));//按指定元素删除，需要传入对象才行
        System.out.println(list);
        //修改
        list.set(0,"aaa");
        System.out.println(list);

List的三种遍历方式

方式一：使用iterator

        Iterator iter=list.iterator();
        while(iter.hasNext()) {
        	Object o=iter.next();
        	System.out.println(o);
        }

方式二：使用增强for

         for(Object o:list) {
        	 System.out.println(o);
         }

方式三：使用普通for

         for(int i=0;i<list.size();i++) {
        	 Object o=list.get(i);
        	 System.out.println(o);
         }

4.ArrayList底层结构和源码分析

基本介绍：

1）ArrayList可以加入多个null

2）ArrayList是由数组实现数据存储的

3）ArrayList是线程不安全的，原因看源码没有synchronized

ArrayList底层操作机制源码分析

1)ArrayList中维护了一个Object类型的数组elementData。

transient Object[] elementData; //transient 表示瞬间,短暂的,表示该属性不会被序列号

2）当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第1次添加，则扩容elementData为10，如需要再次扩容，则扩容elementData为1.5倍。
3)如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容则直接扩容elementData为1.5倍。

5.Vector底层结构和源码解剖

基本介绍：

1) Vector底层也是一个对象数组，protected Objectl] elementData;

2） Vector 是线程同步的，即线程安全,Vector类的操作方法带有synchronized

//1. new Vector() 底层
/*
public Vector() {
this(10);
}
补充：如果是 Vector vector = new Vector(8);
走的方法:
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
2. vector.add(i)
2.1 //下面这个方法就添加数据到 vector 集合
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
2.2 //确定是否需要扩容 条件 ： minCapacity - elementData.length>0
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
2.3 //如果 需要的数组大小 不够用，就扩容 , 扩容的算法
//newCapacity = oldCapacity + ((capacityIncrement > 0) ?
//
capacityIncrement : oldCapacity);
//就是扩容两倍.
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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);
}

6.LinkedList底层结构

LinkedList的全面说明
1)LinkedList底层实现了双向链表和双端队列特点

2)可以添加任意元素(元素可以重复)，包括null

3)线程不安全，没有实现同步

 LinkedList的底层操作机制
1)LinkedList底层维护了一个双向链表

2) LinkedList中维护了两个属性first和last分别指向 首节点和尾节点

3)每个节点 (Node对象) ，里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表

4)所以LinkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高

5)模拟一个简单的双向链表

/* 1. LinkedList linkedList = new LinkedList();
public LinkedList() {}
2. 这时 linkeList 的属性 first = null last = null
3. 执行 添加
public boolean add(E e) {
linkLast(e);
return true;
}
4.将新的结点，加入到双向链表的最后
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
*/
/* linkedList.remove(); // 这里默认删除的是第一个结点
1. 执行 removeFirst
public E remove() {
return removeFirst();
}
2. 执行
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
3. 执行 unlinkFirst, 将 f 指向的双向链表的第一个结点拿掉
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
*/