- 什么是 List
- 什么是集合
- 什么是 List
- List的继承、实现关系
- List类的位置
- List的种类
- ArrayList
- 使用
- 实现方式
- 如何扩容
- LinkedList
- 使用
- 实现方式
- 如何扩容
- Vector
- 使用
- 实现方式
- 如何扩容
- 常用方法
- 共有
- LinkedList
- 结尾
集合就是把具有相同属性的东西放在一起，也可以是容器，把有关的东西都放进去
什么是 ListList是位于java.util下的一个接口，有序集合（也称为序列）。此界面的用户可以精确控制每个元素在列表中的插入位置。用户可以通过整数索引（列表中的位置）访问元素，并在列表中搜索元素
List的继承、实现关系其继承了Collection接口并由AbstractList来实现，Collection又继承了Iterable接口
- Collection：集合层次结构中的根接口。一个集合表示一组对象，称为它的元素。一些集合允许重复元素，而另一些则不允许。有些是有序的，有些是无序的。
- Iterable：实现此接口允许对象成为“for-each 循环”语句的目标。
jrelibrt.jarjavautil 下
也就是java本身自带的，不需要额外引用jar来实现
- ArrayList：底层由数组结构实现Object[]，可以存储任何Object类型的对象，是非线程安全的
- LinkedList：List和Deque接口的双向链表实现。实现所有可选列表操作，并允许所有元素（包括null ）。所有操作都按照双向链表的预期执行。索引到列表中的操作将从开头或结尾遍历列表，以更接近指定索引的为准。
- Vector：底层实现是动态数组的方式存放数据，是线程安全的，Vector源码当中每个方法都被synchronized关键字进行修饰，保证了Vector的线程安全，所以效率很低，尽量少使用
List list = new ArrayList<>();
List
实现方式
创建对象的时候会调用其无参构造方法
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList(Collection c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
可见，当创建ArrayList对象的时候就会创建好一个初始容量为 10 的空列表等待着被使用。
如何扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 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);
}
LinkedList 使用int newCapacity = oldCapacity + (oldCapacity >> 1);
每次自增一半，即原来的1.5倍
List list = new LinkedList<>();
List
实现方式
创建对象的时候会调用其无参构造方法
public LinkedList() {
}
public LinkedList(Collection c) {
this();
addAll(c);
}
public boolean addAll(Collection c) {
return addAll(size, c);
}
LinkedList初始化为空
如何扩容由于LinkedList使用双向列表实现的其结构为
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
因此也没有扩容的机制，如有需求一直在其前面或者后面新增下去
Vector 使用 Vector vector = new Vector<>();
Vector
实现方式
protected Object[] elementData;
protected int capacityIncrement;
public Vector() {
this(10);
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
可以看出Vector和ArrayList是非常相似的
- 都是一个Object[]类型存储数据
- 无参数构造默认数组容量是10
- 使用有参数的构造方法可以指定容量的大小
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);
}
常用方法 共有int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
每次自增一倍，即原来的2倍
- int size();
返回此列表中的元素数 - boolean isEmpty();
如果此列表不包含任何元素，则返回true - boolean contains(Object o);
如果此列表包含指定元素，则返回true - Iterator iterator();
以正确的顺序返回此列表中元素的迭代器 - Object[] toArray();
返回此列表中从第一个元素到最后一个元素的数组 - boolean add(E e);
将指定元素附加到此列表的末尾 - boolean remove(Object o);
如果指定元素存在，则从该列表中删除第一次出现的指定元素。如果此列表不包含该元素，则它不变 - boolean addAll(Collection c);
将指定集合中的所有元素附加到此列表的末尾，按照指定集合的迭代器返回的顺序 - boolean removeAll(Collection c);
从此列表中删除包含在指定集合中的所有元素 - void clear();
从此列表中删除所有元素。此调用返回后，列表将为空 - boolean equals(Object o);
比较指定对象与此列表是否相等。当且仅当指定对象也是一个列表时返回true ，两个列表具有相同的大小，并且两个列表中所有对应的元素对都相等 - E get(int index);
返回此列表中指定位置的元素 - E set(int index, E element);
将此列表中指定位置的元素替换为指定元素 - void add(int index, E element);
在此列表中的指定位置插入指定元素。将当前位于该位置的元素和任何后续元素向右移动 - E remove(int index);
移除此列表中指定位置的元素 - int indexOf(Object o);
返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回 -1 - int lastIndexOf(Object o);
返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回 -1
- E getFirst()；
返回此列表中的第一个元素 - E getLast()；
返回此列表中的最后一个元素 - E removeFirst()；
从此列表中删除并返回第一个元素 - E removeLast()；
移除并返回此列表中的最后一个元素 - void addFirst(E e)；
在此列表的开头插入指定元素 - void addLast(E e)；
将指定元素附加到此列表的末尾 - boolean hasNext();
如果此列表迭代器在向前遍历列表时具有更多元素，则返回true - E next();
返回列表中的下一个元素并前进光标位置
- 上述内容绝大多数来自源码
- 部分为自己总结
记：反复使用后的小总结
