一：ArrayList实现类：ArrayList是List接口的实现类
基本特点：
数据插入有序
可以存储null值
数据可以重复
底层的数据结构是数组
数据插入有序
可以存储null值
数据可以重复
底层的数据结构是数组
ArrayList的继承关系：
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
继承AbstractList类，实现List接口；
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>
AbstractLiST继承AbstractCollection类，实现List接口；
public abstract class AbstractCollection<E> implements Collection<E>
AbstractCollection实现Collection接口；
public interface Collection<E> extends Iterable<E>
Collection继承Iterable类；
public interface Iterable<T> { /** * Returns an iterator over elements of type {@code T}. * * @return an Iterator. */ Iterator<T> iterator(); }
Iterable是一个接口；
相关属性：
底层：
ArrayList中维护了一个Object类型的数组elementData,创建对象时初始容量设置为0，当第一次添加时，将elementData容量设置为10，该容量代表了数组的大小。随着容器中的元素不断增加，当容器中的元素个数达到10个时，容器已满，此时容器就会进行扩容，扩容后的大小为扩容前大小的1.5倍，在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。
private static final int DEFAULT_CAPACITY = 10;//默认容量是10 private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */ transient Object[] elementData; // non-private to simplify nested class access /** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size;
注：transient关键字：Java语言的关键字，变量修饰符，如果用transient声明一个实例变量，当对象存储时，它的值不需要维持。换句话来说就是，用transient关键字标记的成员变量不参与序列化过程。
作用：
Java的serialization提供了一种持久化对象实例的机制。当持久化对象时，可能有一个特殊的对象数据成员，我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization，可以在这个域前加上关键字transient。当一个对象被序列化的时候，transient型变量的值不包括在序列化的表示中，然而非transient型的变量是被包括进去的。
Java的serialization提供了一种持久化对象实例的机制。当持久化对象时，可能有一个特殊的对象数据成员，我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization，可以在这个域前加上关键字transient。当一个对象被序列化的时候，transient型变量的值不包括在序列化的表示中，然而非transient型的变量是被包括进去的。
1. 扩容机制： 数组的扩容是按照原数组长度的1.5倍扩容
/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); //>>1 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }
2.得到该元素：
/** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { rangeCheck(index); return elementData(index); }
3.清空数组：clear
public void clear() { modCount++; // clear to let GC do its work垃圾回收器 for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }
4.删除：因为ArrayList中可以存储值为null的元素，所以需要对null进行特殊判断
public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; }
fastRemove的实现：主要将index+1号以后的元素移动到index号元素
private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work }
arraycopy源码：
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
5.indexOf( )和lastIndexOf( )
假如一个数组中没有相同的两个数或者不存在该数，它的lastIndexOf()=indexOf();
所以，用此方法可以判断一个数组中是否有两个相同的元素。
lastIndexOf源码：
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; }
6.toArray()方法：将集合转化为数组类型
Collection<String> col=new ArrayList<>(); col.add("zhang"); col.add("zhao"); col.add("wang"); col.add("li"); col.add("hui"); Object[] c=col.toArray(); String[] s=(String[]) col.toArray();//强制转型 System.out.println(Arrays.toString(c)); System.out.println(Arrays.toString(s));
会报类型转换的异常：Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.String;
原因：toArray是一个Object类型的数组，不能将Object[ ] 转化为String[ ]，转化的话只能是取出每一个元素再转化。
java中的强制类型转换只是针对单个对象的，想要偷懒将整个数组转换成另外一种类型的数组是不行的，这和数组初始化时需要一个个来也是类似的。
一：自定义实现ArrayList
package Lesson1; import java.util.Arrays; /** * 问题：my.size()方法不等于elementData-1 elementData.length等于构造函数初始化时，传入的capacity， * 所以mysize()方法与elementData.length无关。所以getSize()方法的返回值可以直接为size * 自定义实现ArrayList * @param <T> */ public class ArrayListMyself <T>{ private Object[] elementData;//定义了一个数组 private int size; public ArrayListMyself(int capacity){ elementData=(T[])new Object[capacity]; } public ArrayListMyself(){ this(2); } /** * 添加值为value的元素 */ public boolean add(T value) { if(full()){ Arrays.copyOf(elementData,elementData.length*2); } this.elementData[this.size++]=value; return true; } public boolean full() { return this.elementData.length==this.getSize(); } /** * * @return直接返回长度size */ public int getSize(){ return size; } /** * 获取index号元素 ，返回元素的值 */ public T get(int index) { if(index<0 || index>size){ throw new IndexOutOfBoundsException("参数异常"); } for (int i=0;i<elementData.length;i++){ if(i==index){ return (T)elementData[i]; } } return null; } /** * 删除index号元素 */ public boolean remove(int index) { if(index<0 ||index>size){ return false; }else { for (int i=index;i<size-1;i++){ elementData[i]=elementData[i+1]; } size--; } return true; } public static void main(String[] args) { ArrayListMyself my=new ArrayListMyself(); my.add(4); my.add(5); System.out.println(my.size);//2 System.out.println(my.elementData.length);//2 System.out.println(my.remove(1));//true System.out.println(my.getSize());//1 System.out.println(my.remove(0));//true System.out.println(my.size);//0 if (my.size!=0){ for (int i = 0; i <my.size; i++) { System.out.print(my.get(i)+" "); } }else { System.out.println("当前数组为空!"); } } }
或者可以自己写一个tooString方法，实现数组的打印：
public String tooString(){ StringBuilder s=new StringBuilder(); if(this.size==0){ return null; } else { for (int i = 0; i < this.size; i++) { s = s.append(get(i) + " "); } return s.toString(); } }
可以封装一个方法进行参数的检查,在添加或者删除的时候直接调用该方法：
（源码中给出了专门添加元素的方法rangeCheckForAdd）
private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
♥ subList方法：推荐文章：为什么呢阿里巴巴要求谨慎使用ArrayList中的subList方法
测试代码：
package Lesson2;
import java.util.ArrayList;
import java.util.List;
class A{
public static void main(String[] args) {
ArrayList a=new ArrayList();
a.add(1);
a.add(2);
a.add(3);
//List类型的subList public List<E> subList(int fromIndex, int toIndex)
List b=a.subList(0,2);//返回子串0-1号
System.out.println(a);// 1 2 3
System.out.println(b);//1 2
/**
* 非结构性地对子串进行改变，原串与子串都会被改变
*/
b.set(1,6);//将1号位置的元素设置为6
System.out.println(b);//1 6
System.out.println(a);//1 6 3
/**
* 结构性的改变字串：增加元素，原串也会相应增加
*/
b.add(10);
System.out.println(b);//1 6 10
System.out.println(a);//1 6 10 3
/**
* 结构性地改变原串，会报错：Exception in thread "main" java.util.ConcurrentModificationException
*/
// a.add(4);
// System.out.println(b);
// System.out.println(a);
}
}
[1, 2, 3] [1, 2] [1, 6] [1, 6, 3] [1, 6, 10] [1, 6, 10, 3]
所以，对子串和原List的修改还需要注意几点，尤其是他们之间的相互影响：
1、对父(sourceList)子(subList)List做的非结构性修改（non-structural changes），都会影响到彼此。
2、对子List做结构性修改，操作同样会反映到父List上。
3、对父List做结构性修改，会抛出异常ConcurrentModificationException。
二：LinkedList实现类：
继承关系：
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
默认属性：
transient int size = 0; transient Node<E> first; transient Node<E> last;
数据结构：
LinkedList的本质是双向链表。
(01) LinkedList继承于AbstractSequentialList，并且实现了Dequeue接口。
(02) LinkedList包含两个重要的成员：header 和 size。
header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。
size是双向链表中节点的个数。
LinkedList的扩容机制：
由于它的底层是用双向链表实现的，没有初始化大小，也没有扩容的机制。
package List; import java.util.Iterator; import java.util.LinkedList; /** * 大量操作首尾元素的方法： * void addFirst(E e) void addLast(E e) * E getFirst() E getLast() * E removeFist() E removeLast() * E pop() void push(E e) boolean isEmpty() * */ public class LinkedListDemo { public static void main(String[] args) { show1(); } private static void show1() { LinkedList<String> linkedList=new LinkedList(); linkedList.add("a"); linkedList.add("b"); linkedList.add("c"); System.out.println(linkedList); //addFirst等效于push linkedList.addFirst("begin"); System.out.println(linkedList); linkedList.push("start"); System.out.println(linkedList); //add类似于addLast linkedList.addLast("last"); System.out.println(linkedList.getFirst());//得到第一个元素 System.out.println(linkedList.getLast());//得到最后一个元素 //removeFirst( )相当于pop( ) System.out.println("第一个元素："+linkedList.removeFirst());//删除第一个元素 System.out.println("最后一个元素："+linkedList.removeLast());//删除最后一个元素 //迭代器遍历集合 Iterator<String> i=linkedList.iterator(); while (i.hasNext()){ System.out.print(i.next()+" "); } System.out.println(); System.out.println(linkedList.isEmpty()); linkedList.clear();//清空链表 System.out.println(linkedList.isEmpty()); }
public static void show2(){
LinkedList<String> linkedList=new LinkedList();
linkedList.add("a");
linkedList.add("b");
linkedList.add("c");
System.out.println(linkedList);
System.out.println(linkedList.get(1));
System.out.println(linkedList.size());
System.out.println(linkedList.remove(1));
Iterator<String> i=linkedList.iterator();
while (i.hasNext()){
System.out.print(i.next()+" ");
}
}
}
