摘要：
总结很重要、他能客观的体现出你对这个体系的理解程度、首先要对整体的结构框架要掌握、再细化到每个分支的特点、再比较不同分支之间的相同点、不同点、再根据他们不同的特性分析他们的应用场景。
一：List的整体框架图
线条简单说明：
1、上图中虚线且无依赖字样、说明是直接实现的接口
2、虚线但是有依赖字样、说明此类依赖与接口、但不是直接实现接口
3、实线是继承关系、类继承类、接口继承接口
类或接口说明：
1、Collection：高度抽象出来的集合、定义某一类集合所具有的基本的方法、标准。
2、Iterable：标识性接口、要求子类提供获取Iterator方法、并且要实现Iterator具有的几个方法。
3、Iterator：迭代器、用于迭代Collection中元素、要求子类必须实现获取Iterator的方法、
4、ListIterator：用于迭代List集合的迭代器、要求List子类必须实现获取ListIterator方法、并且实现其必须方法。
5、List：以队列的形式存储、操作元素、定义了这种形式的集合所具有的基本方法、以及方法的定义。要求List实现类集合中每个元素都有索引、索引值从0开始、
6、Queue：以队列的数据结构存储、操作元素、Queue对于插入、提取和检查操作。每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）。
7、Deque：实现Queue、使子类可以以双向链表的数据结构形式存储、操作数据、从这可以看出其子类的灵活性较大。
8、Enumeration：枚举、用于Vector及其子类迭代元素、他避免了fail-fast机制、使得Vector及其子类在迭代元素的时候可以保证线程安全。
9、AbstractCollection：Collection的实现类、要求需要实现Collection接口的类都必须从它继承、目的是用于简化编程。
10、 AbstractList：继承AbstractCollection、实现List接口中定义方法、目的也是简化编程、并且其内部提供了获取Iterator、ListIterator的方法。
11、 AbstractSequencedList：继承AbstractList、使得List支持有序队列、比如链表形式存储操作元素。
12、 ArrayList：继承AbstractList、以动态数组的形式存储、操作元素、
13、 LinkedList：继承AbstractSequencedList、实现Deque、List接口、以双向链表的形式存储、操作元素。
14、 Vector：继承AbstractList、以动态数组的形式存储、操作元素、线程安全
15、 Stack：继承Vector、在Vector的基础上新增以栈的形式存储、操作元素。
二：LinkedList与ArrayList
1、相同之处
a）都直接或者间接继承了AbstractList、都支持以索引的方式操作元素
b）都不必担心容量问题、ArrayList是通过动态数组来保存数据的、当容量不足时、数组会自动扩容、而LinkedList是以双向链表来保存数据的、不存在容量不足的问题
c） 都是线程不安全的、一般用于单线程的环境下、要想在并发的环境下使用可以使用Collections工具类包装。
2、不同之处
a）ArrayList是通过动态数组来保存数据的、而LinkedList是以双向链表来保存数据的
b）相对与ArrayList而言、LinkedList实现了Deque接口、Deque继承了Queue接口、同时LinkedList继承了AbstractSequencedList类、使得LinkedList在保留使用索引操作元素的功能的同时、也实现了双向链表所具有的功能、这就决定了LinkedList的特定
c）对集合中元素进行不同的操作效率不同、LinkedList善于删除、添加元素、ArrayList善于查找元素。本质就是不同数据结构之间差异。
三：ArrayList与Vector
1、相同之处：
a） 都是继承AbstractList、拥有相同的方法的定义、
b）内部都是以动态数组来存储、操作元素的、并且都可以自动扩容。
2、不同之处：
a） 线程安全：ArrayList是线程不安全的、适用于单线程的环境下、Vector是线程安全的、使用与多线程的环境下。
b）构造方法：Vector有四个构造方法、比ArrayList多一个可以指定每次扩容多少的构造方法
c） 扩容问题：每当动态数组元素达到上线时、ArrayList扩容为：“新的容量”=“(原始容量x3)/2 + 1”、 而Vector的容量增长与“增长系数有关”，若指定了“增长系数”，且“增长系数有效(即，大于0)”；那么，每次容量不足时，“新的容量”=“原始容量+增长系数”。若增长系数无效(即，小于/等于0)，则“新的容量”=“原始容量 x 2”。
d） 效率问题：因为Vector要同步方法、这个是要消耗资源的、所以效率会比较低下
e）Vector为摆脱fail-fast机制、自己内部多提供了一种迭代方法Enumeration、
四：LinkedList、ArrayList、Vector、Stack、Array
1、不同操作的效率对比
关于上面四个集合加一个数组、在这里给出一个表格用于表示他们的不同的操作的效率的排名、这样更直观、
|
|
实现机制 |
随机访问 |
迭代操作 |
插入操作 |
删除操作 |
|
数组 |
连续内存区保护元素 |
1 |
不支持 |
不支持 |
不支持 |
|
ArrayList |
以数组保存元素 |
2 |
2 |
2 |
2 |
|
Vector |
以数组保存元素 |
3 |
3 |
3 |
3 |
|
Stack |
以数组保存元素 |
3 |
3 |
3 |
3 |
|
LinkedList |
以链表保存元素 |
4 |
1 |
1 |
1 |
通过实例来验证上面表格的内容、由于数组比较特殊、他是牺牲的长度的变化直接在内存中开辟空间来存储元素、所以查询效率是毋庸置疑的、同时由于size一旦确定就不能改变、所以插入删除不支持。所以下面验证没有关于Array的的验证
2、示例：
package com.chy.collection.example;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import java.util.Vector;
public class EfficiencyTest {
private static ArrayList<String> arrayList = new ArrayList<String>();
private static Vector<String> vector = new Vector<String>();
private static Stack<String> stack = new Stack<String>();
private static LinkedList<String> linkedList = new LinkedList<String>();
/**
* 测试插入方法（每次都将新增加的元素插入到集合开始处）、注意不要写成 add(Object o)方法、具体原因自己分析
*/
private static void testInsert(){
testInsert(arrayList);
testInsert(vector);
testInsert(stack);
testInsert(linkedList);
}
/**
* 测试随机访问效率
*/
private static void testRandomAccess(){
testRandomAccess(arrayList);
testRandomAccess(vector);
testRandomAccess(stack);
testRandomAccess(linkedList);
}
/**
* 测试Iterator迭代效率
*/
private static void testIterator(){
testIterator(arrayList);
testIterator(vector);
testIterator(stack);
testIterator(linkedList);
}
/**
* 测试删除效率
*/
private static void testDelete(){
testDelete(arrayList);
testDelete(vector);
testDelete(stack);
testDelete(linkedList);
}
private static void testInsert(List<String> list){
long start = currentTime();
for (int i = 0; i < 10000; i++) {
list.add(0,"a");
}
long end = currentTime();
System.out.println("the add method of " + list.getClass().getName() + " use time : " + (end - start) + "ms");
}
private static void testRandomAccess(List<String> list){
long start = currentTime();
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
long end = currentTime();
System.out.println("the random access method of " + list.getClass().getName() + " use time : " + (end - start) + "ms");
}
private static void testIterator(List<String> list){
long start = currentTime();
Iterator<String> it = list.iterator();
while(it.hasNext()){
it.next();
}
long end = currentTime();
System.out.println("the iterator method of " + list.getClass().getName() + " use time : " + (end - start) + "ms");
}
private static void testDelete(List<String> list){
long start = currentTime();
for (int i = 0; i < 10000; i++) {
if(!list.isEmpty()){
list.remove(0);
}
}
long end = currentTime();
System.out.println("the delete method of " + list.getClass().getName() + " use time : " + (end - start) + "ms");
}
private static long currentTime(){
return System.currentTimeMillis();
}
public static void main(String[] args) {
testInsert();
System.out.println("==========================================================");
testRandomAccess();
System.out.println("==========================================================");
testIterator();
System.out.println("==========================================================");
testDelete();
}
}
运行结果：
the add method of java.util.ArrayList use time : 32ms the add method of java.util.Vector use time : 47ms the add method of java.util.Stack use time : 31ms the add method of java.util.LinkedList use time : 15ms ========================================================== the random access method of java.util.ArrayList use time : 15ms the random access method of java.util.Vector use time : 16ms the random access method of java.util.Stack use time : 17ms the random access method of java.util.LinkedList use time : 47ms ========================================================== the iterator method of java.util.ArrayList use time : 16ms the iterator method of java.util.Vector use time : 15ms the iterator method of java.util.Stack use time : 17ms the iterator method of java.util.LinkedList use time : 16ms ========================================================== the delete method of java.util.ArrayList use time : 47ms the delete method of java.util.Vector use time : 31ms the delete method of java.util.Stack use time : 32ms the delete method of java.util.LinkedList use time : 15ms
不同的运行环境、差异可能比较大。
3、差异原因分析：
在这里不会主要讨论所有的差异、而是通过源码的方式分析LinkedList与Arraylist、ArrayList与Vector在随机访问、插入、删除元素方面的差异原因、至于迭代Iterator、他们都是用从AbstractList继承的获取Iterator方法、差异不大、不再比较。
ArrayList与LinkedList
a）ArrayList的随机访问效率高于LinkedList：
随机访问是通过索引去查找元素的、LinkedList关于获取指定索引处值的源码：
/** 获取index处的元素*/
public E get(int index) {
return entry(index).element;
}
/** 获取双向链表LinkedList中指定位置的节点、是LinkedList实现List中通过index操作元素的关键*/
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
Entry<E> e = header;
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
关于获取指定索引处的值的源码：
/** 检测下标是否越界*/
private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
}
/** 获取ArrayList中索引为index位置的元素*/
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
对比两者源码可以看出、LinkedList获取指定索引处的值是通过二分法先确定索引所在范围之后、在逐个查找、直到找到指定索引处、并且对每个索引都是如此、相比于ArrayList直接定位到index处的值来讲、无疑是非常浪费时间、消耗资源的、
b）ArrayList的插入、删除操作效率低于LinkedList的原因：
对于指定index处的插入、删除、ArrayList和LinkedList都是先通过索引查找到指定位置、然后进行下一步的插入删除操作、上面我们知道LinkedList是先通过二分法查找index范围再确定index具体位置、但是ArrayList是直接定位到index处、为什么LinkedList反而快？依然通过源码找原因。
ArrayList关于指定位置的元素的插入：
/**
* 确保此ArrayList的最小容量能容纳下参数minCapacity指定的容量、
* 1、minCapacity大于原来容量、则将原来的容量增加(oldCapacity * 3)/2 + 1;
* 2、若minCapacity仍然大于增加后的容量、则使用minCapacity作为ArrayList容量
* 3、若minCapacity不大于增加后的容量、则使用增加后的容量。
*/
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
/** 将指定元素添加到指定的索引处 、
* 注意：
* 1、如果指定的index大于Object[] 的size或者小于0、则抛IndexOutOfBoundException
* 2、检测Object[]是否需要扩容
* 3、 将从index开始到最后的元素后移一个位置、
* 4、将新添加的元素添加到index去。
*/
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
LinkedList关于指定位置的元素的插入：
/** 在index前添加节点，且节点的值为element*/
public void add(int index, E element) {
addBefore(element, (index==size ? header : entry(index)));
}
/** 获取双向链表LinkedList中指定位置的节点、是LinkedList实现List中通过index操作元素的关键*/
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
Entry<E> e = header;
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
//新建节点、节点值是e、将新建的节点添加到entry之前
private Entry<E> addBefore(E e, Entry<E> entry) {
//觉得难理解的可以先花个几分钟看一下链式结构资料、最好是图片形式的
//新建节点实体
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
//将参照节点原来的上一个节点（即插在谁前面的）的下一个节点设置成newEntry
newEntry.previous.next = newEntry;
//将参照节点（即插在谁前面的）的前一个节点设置成newEntry
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
对比上面代码可以看出来ArrayList每当插入一个元素时、都会调用System.arraycopy()将指定位置后面的所有元素后移一位、重新构造一个数组、这是比较消耗资源的、而LinkedList是直接改变index前后元素的上一个节点和下一个节点的引用、而不需要动其他的东西、所以效率很高。
ArrayList与Vector：
ArrayList、Vector都是继承与AbstractList、并且在类结构上没有多少差异、但是因为Vector要同步方法、所以在性能上不如ArrayList、从源码也可以看出Vector许多方法都是使用关键字synchronized修饰的。不再贴源码
总结：
学以致用、最后总结下上述List集合体系的各个类的使用环境：
1、当需要对集合进行大量的查询时、并且是单线程环境下使用ArrayList
2、当需要对集合进行大量添加、删除时、并且是单线程环境下使用LinkedList、
3、当多线程时、需要对集合进行大量的查询时、可以考虑使用Vector或者Stack、但是不建议、我们可以使用多次提到的Collections类包装。
相关推荐
集合框架是Java标准库中的重要部分，包括List、Set和Map等接口及其实现类。习题可能要求学生熟练运用ArrayList、LinkedList、HashSet、HashMap等，理解它们的区别和适用场景，以及如何高效地操作和遍历集合。 IO流...
"java技术集合体系图"涵盖了Java集合框架的重要概念和组件，对于深入理解Java编程至关重要。下面我们将详细探讨这个话题。 首先，"Collection.jpg"可能是一个展示了Java集合接口层次结构的图表。在Java集合框架中，...
Java集合框架是Java编程语言中的一个核心组成部分，它为存储、管理和操作对象提供了一组统一的接口和类。这个框架使得开发者能够以一种灵活且高效的方式处理数据集合，而无需关心底层实现的复杂性。本课件将深入探讨...
理解并熟练运用Java集合体系中的List、Set、Map接口及其实现类，对于日常开发和面试来说至关重要，因为它们是许多Java框架和库的基础。在实际项目中，根据需求选择合适的集合类型可以提高代码的效率和可维护性。在...
描述中提到“java中集合list的应用非常重要”，这确实不假，因为List在处理有序数据时具有广泛的应用场景。 List接口位于java.util包下，它继承自Collection接口。Java提供了多种List的实现类，如ArrayList、...
在这个“Java List集合的应用.rar”压缩包中，我们可以预见到一系列关于如何在实际场景中使用List集合的实例，例如学生管理系统中的注册、登录和日志管理等常见功能。 首先，让我们深入了解一下Java List集合的基础...
Java集合框架是Java编程语言中不可或缺的一部分，它为开发者提供了数据结构和算法的实现，使得在处理各种数据存储和操作时更加高效。本资源“Java_jihe2.rar”包含了关于Java集合框架第二部分的学习源码，是进一步...
总结来说，List 和 Set 是Java集合框架中的两个主要接口，它们分别提供了有序的和无序的元素存储方式。在选择使用哪种集合时，应考虑数据的特性和操作的需求，比如是否需要保持元素的插入顺序、是否允许重复以及是否...
4. **集合框架**：Java集合框架是用于存储和操作对象的工具，包括List、Set、Map等接口以及ArrayList、LinkedList、HashSet、HashMap等实现类。掌握它们的特性和使用场景，以及迭代器、泛型和并发容器的使用。 5. *...
Java集合框架是Java API的一部分，它提供了多种数据结构，如List、Set和Queue等，以及操作这些数据结构的方法。这些数据结构可以帮助我们有效地存储和管理数据。 2. **ArrayList与HashMap**： - **ArrayList**：...
其中，集合框架是Java编程中不可或缺的一部分，包括接口如 `List`, `Set`, `Map` 以及实现这些接口的具体类如 `ArrayList`, `HashSet`, `HashMap` 等，它们提供了数据存储和操作的强大支持。 `java.net` 包支持网络...
4. **集合框架**: 学习ArrayList、LinkedList、HashSet、HashMap等容器的使用，理解它们的区别和应用场景，以及List、Set、Map接口的概念。 5. **IO流**: 学习如何进行文件的读写操作，包括字节流和字符流，以及...
2. **集合框架**：Java集合框架是处理对象集合的一组接口和类，如List、Set、Map等。在电商项目中，集合常用于存储商品、用户、订单等信息。 3. **多线程**：在高并发场景下，Java的多线程机制显得尤为重要。项目...
`java.util.Collection`接口是Java集合框架的基础，它是所有Set和List集合类型的根接口。该接口定义了一系列基本的操作方法，如添加(add)、删除(remove)、获取元素数量(size)等。这些方法为实现集合框架提供了统一的...
总结来说，Java集合框架提供了丰富的数据结构和操作，适用于各种场景。理解并熟练掌握Collection、List、Map和Set的特性和用法，能显著提高代码的效率和可维护性。在实际开发中，应根据需求选择合适的集合类，并利用...
5. **集合框架**：Java集合框架包括List、Set、Queue和Map等接口，以及ArrayList、LinkedList、HashSet、HashMap等实现类。实例会展示如何存储、操作和遍历这些数据结构。 6. **IO流**：Java的IO流处理涵盖了读写...
在Java编程中，List集合是开发人员经常使用的一种数据结构，用于存储有序的元素列表。本文将详细介绍6种初始化Java List集合的方法，并通过代码示例帮助理解每种方法的使用和特点。 1. 常规方式 这是最常见的初始化...
再者，Java集合框架是处理数据结构的关键，包括List（如ArrayList和LinkedList）、Set（如HashSet和TreeSet）、Map（如HashMap和TreeMap）等接口和实现。它们提供了丰富的操作，使得数据组织和操作更加高效。 然后...
本文将深入探讨Java集合框架的基础知识，包括接口、类、以及它们在实际开发中的应用。 首先，Java集合框架由一系列接口和实现这些接口的类组成。主要的接口有`List`、`Set`和`Queue`，它们各自代表了不同特性的数据...