【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; } */