List 集合(实现类有ArrayList和LinkedList)
它是单身住宿的，一次存储一个对象。它拥有 Collection 规定的所有方法的实现；同时它可以拥有自身独特的规定的方法。
List集合的特点：
1.有索引：List 集合是有索引的
2.有序性：List 集合是有序的保证了装入集合时的顺序
3.重复性：List 集合允许存储重复的元素
List 集合的三个典型实现：
1、List list1 = new ArrayList();
底层数据结构是数组，查询快，增删慢；线程不安全，效率高。
2、List list3 = new LinkedList();
底层数据结构是链表，查询慢，增删快；线程不安全，效率高。
3、List list2 = new Vector();
底层数据结构是数组，查询快，增删慢；线程安全，效率低，这个集合几乎被淘汰。
List 常用方法学习
public class TestList {
public static void main(String[] args) {
List list = new ArrayList();
Collection list2 = new ArrayList();
//增加元素
list.add("1");
list.add("2");
list.add("3");
list.add("5");
list.add("4");
list.add("5");
//增加元素
list.remove("1");
//改变元素
list.set(4,"被修改了");
System.out.println(list);
//构造 List 的迭代器
Iterator it = list.iterator();
//通过迭代器遍历元素
while(it.hasNext()){
Object obj = it.next();
System.out.println(obj);
}
// List 独有的 遍历方式
for(int i = 0 ; i < list.size() ; i++){
System.out.println(list.get(i));
}
/**
List<E> subList(int fromIndex, int toIndex)
获取一个子集合
参数1 是开始截取的索引
参数2 是结束截取的索引
包含参数1 不包含参数2*/
List li = list.subList(2, list.size());
System.out.println(li);
}
}
int indexOf(Object o) 查看 o 第一次出现的索引位置
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
int lastIndexOf(Object o ) 查看o 最后一次出现的索引位置
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
ArrayList--底层是数组
底层学习
观察所有的构造器 发现都是在为 ElementData 赋值 由此得出 ElementData 就是底层实现，ElementData 本身是 Object[] ElementData;
增加元素
每增加一个元素，就会判断数组是否需要扩容，拿现在size + 1 去判断，如果需要扩容，那就扩容1.5倍。
int newCapacity = oldCapacity + (oldCapacity >> 1);然后
elementData[size++] = 要添加的元素
public boolean add(Object obj){
ensureCapacityInternal(size+1)//扩容
elementData[size++] = obj;
return ture;
}
删减元素
每移除一个元素，会先确定元素的位置，确定元素的值，然后把 要删除的位置之前的，之后的copy到新数组，新数组替换 elementData ，然后把最后一位size赋值为null size也要 --
public E remove(int index){
rangeCheck(index);
modcount++;
E oldValue = elementData(index)
int numMoved = size - index -1;
if(numMoved>0)
System.arraycopy(elementData,index+1,elementData,index,numMoved);
elementData[--size]=null;
return oldValue;
}
LinkedList--底层是链表
什么是链表
链式存储的线性表
LinkedList 存储的是什么
Node 对象：Node对象有 三个属性
item :要存储的对象
next : 下一个元素对象 (last 的next 一般为 null)
prev :上一个元素对象 (first 的prev 一般为 null)
LinkedList 的 add 原理
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++;
}
首先增加到 last，先记录住当前 last 的对象，然后根据当前的 last(prev) 对象和要添加的元素(item) 和 null(next) 创建一个 newNode ，last 重新赋值 赋值为 newNode，添加元素之前的 last , 已经被记录了 ,并且参与了构建新对象 然后再把它的 next 指向新对象，然后 size++。
LinkedList 的 remove 原理
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
1. 根据索引找出要移除的对象
2. 记录 要移除的对象的 上一个指向(prev) 存储的值(value) 下一个指向(next)
3. prev 代表的对象 next 属性不再指向被移除的对象 改为指向 next代表的对象
4. next 代表的对象 它的 prev 属性不要指向被移除的对象 改为指向 prve代表的对象
同时要考虑 被移除对象可能是 first 或 last , 处理方式会有所不同
LinkedList 的 遍历
要得到第一个 Node对象，然后不停的寻找下一个对象即 next 属性，然后一直寻找到最后的，中间地址跳转频繁 ：
