一。通用数据结构：数组，链表，树，哈希表
通用数据结构通过关键字的值来存储并查找数据，如报表，合同，记录，业绩等数据。通用数据结构可以用速度的快慢来分类，数组和链表是最慢的，树相对较快，哈希表是最快的。请注意，并不是最快的就一定是最好的，因为最快的结构的程序在不同程度上比数组和链表的复杂，而且哈希表要求预先要知道存储多少数据，数据对存储空间的利用率也不是非常高。普通的二叉树对顺序的数据来说，会变成缓慢的O(N)级操作，平衡树虽然避免了这个问题，但程序编写却比较困难。
通过数据结构的关系可以用这个图来表示：
随着计算机硬件性能的不断提升，CPU的计算速度也越来越快，所以首选简单数据结构，除非他们真的表现太慢，否则不要采用复杂的数据结构，只要运行结果在可接受范围内，没人会在乎你用了什么数据结构的。
在操作对象的速度上，java比其他语言有优势，对于大多数数据结构来说，java只存储引用而不是实际的对象。在分析算法时，不是从对象的真实存储空间出发，因而移动对象的速度也不依赖于对象的大小，只是考虑对象引用的移动，而对象本身的大小就不重要了。在编程语言中，类库会封装一些数据结构和算法，所以在选择类库时要确保这个类能真正适应特定的业务场景。
1.数组
存储和操作数据时，大多数情况下，数组是首选的，数组最有用的情况是数据量较小和数据量的大小事先可预测。数组元素的删除总是很慢，因为为了填充空出来的单元，平均半数以上的数组元素要被移动。在有序数组中的遍历是很快的。向量是一种当数据太满时可以自己扩充空间的数组，向量可以应用于数据量不可预知的情况下，但是向量在扩充时，要将旧的数据拷贝到一个新的空间，这个过程会造成程序的周期性暂停。
2，链表
如果需要存储的数据量不能预知或需要频繁的插入删除数据元素，考虑使用链表。当有新的元素加入时，链表就开辟新的空间，它甚至可以占满所有可用空间，在删除过程中不会像数组那样填补空缺。在一个无序链表中，插入很快，查找和删除却很慢，因此，与数组一样，链表最好也应用于数据量较小的场景。相比之下，链表比数组复杂，但比树和哈希表简单。
3.二叉搜索树
当确认数组和链表过慢时，最先考虑的是二叉树，树可以提供快速的O(logN)级的插入，查找，删除，遍历的时间复杂度是O(N)级的，对于遍历一定范围内的数据可以很快得到访问数据的最大值和最小值。对于程序，不平衡的二叉树要比平衡二叉树简单的多，但是有序数据能将它的性能降低到O(N)级，并不比链表好。如果能保证数据是随机的，就不需要用平衡二叉树。
4.平衡树
红黑树和多叉树都是平衡树，无论数据是否有序，都能保证性能是O(logN)。对于编程来说，最难的是红黑树（应用最广泛）。它们也因用了附加存储而产生额外耗费，这对系统多少都有些影响。利用树的类库可以降低编程困难度，某些情况下，选择哈希表比平衡树要好。
5.哈希表
哈希表在数据存储结构中速度最快，哈希表通常用于拼写检查器和作为计算机编程语言中的编译器的符号表。哈希表对数据插入的顺序并不敏感，因此可以取代平衡树，而且哈希表的编程比平衡树简单多了。哈希表需要有额外的存储空间，因为哈希表用数组作为基本结构，所以预先必须精确的知道待存储的数据量。用链地址法处理冲突的哈希表是最好的实现方法。
哈希表并不能提供任何形式的有序遍历，或对最大最小值元素进行存取，实现这些功能使用二叉搜索树更好一些。
二。专用数据结构：栈，队列，优先级队列
这些结构不是为了用户可访问的数据库而建立的，通常用它们在程序中辅助实现一些算法。这些结构都不支持查找或遍历。
栈，队列，优先级队列都是抽象数据类型（ADT），它们由一些更加基础的结构如数组，链表，堆组成。这些ADT只提供给用户简单的接口，一般只允许用户插入和访问或删除一个数据项（栈：最后被插入的数据；队列：最先被插入的数据；优先级队列：具有最高优先级的数据）。
1.栈
是一个后进先出的结构，往往通过数组或链表实现，因为最后被插入的数据总是在数组的最后，这个位置的数据很容易被删除。栈的溢出有可能会出现，通过合理规划数组的大小可以避免，而且栈很少会拥有大量的数据。如果栈拥有大量的数据，并且数量不可精确预测（用栈实现递归时），用链表比数组更好一些，因为从表头的位置删除或插入一个元素很方便，除非整个内存满了。链表比数组稍慢一些，因为对于插入一个新链接必须分配内存，从表中某个链接点上删除元素后回收分配内存也是必需的。
2，队列
是一个先进先出的结构，同样可以通过数组和链表实现，数组需要附加的程序来处理队列在数组尾部回绕的情况。链表必须是双端的，这样才能从一段插入从另一端删除。如果知道数据量的多少就可以用数组，否则用链表。
3.优先级队列
优先级队列用在只对访问最高优先级数据项访问的时候，最高优先级数据项就是含有最大或最小的关键字的项。
可以用有序数组或堆来实现。向有序数组中插入是很慢的，但删除很快。使用堆来实现优先级队列，插入和删除的时间复杂度都是O(logN)级。当插入速度不重要时，可以使用数组或双端链表，数据量可以被预测时，使用数组，数据量未知时使用链表，如果速度很重要的话，选择堆更好。
三。排序：插入排序，希尔排序，快速排序，归并排序，堆排序
随着计算机的处理能力越来越快，在实际中，选择数据结构时，可以先尝试选择一种较慢但简单的排序，如插入排序（这里指数据量小于1000的数据），插入排序如果没有太多的元素处于乱序的位置，操作的时间复杂度约为O(N)级，通常是在往一个已经排好序的文件中插入一些新的数据元素的场景下。如果插入排序显得太慢，可以尝试希尔排序，根据经验，数据量在5000以下时很有用。只有当希尔排序变得很慢时，才应该考虑复杂的算法，如归并排序，堆排序，快速排序。归并排序需要辅助存储空间，堆排序需要有一个堆的数据结构，在某些程度上这两种都比快速排序慢，所以经常会优先选择快速排序。但是快速排序在处理非随机性数据时性能不太好。如果有可能是非随机性数据，堆排序更好。
四。图：邻接矩阵，邻接表
图并不存储通用数据，也不会在其他算法中成为程序员的工具，它们直接模拟现实世界的情况，图的形状直接反映了问题的结构。没有其他数据结构可以取代图的使用。根据图的疏密程度，稠密的图选择邻接矩阵，稀疏的图用邻接表。邻接矩阵表示的图的深度优先搜索和广度优先搜索时间复杂度为O(V*V)级，V是顶点的个数。邻接表表示的图的两种操作时间复杂度是O(V+E)级，E是边的条数。使用前，先估计图中的V和E，然后计算哪种表示方法更合适。
五。外部存储：顺序存储，索引文件，B-树，哈希方法
如果数据量大到内存容不下时，只能被存储到外部存储空间，一般是磁盘文件。存在磁盘文件中具有固定大小单元的数据称为块，每个块都存储一定数量的记录（磁盘文件中的记录拥有与主存中对象相同的数据类型）。与对象一样，每条记录都有一个关键字值，通过它可以访问到这条记录。假设读写操作总是在一个单一的块中进行，这些读写操作比对主存中的数据进行任何操作都要耗时的多，为了提高操作速度必须将磁盘的存取次数减到最小。
1.顺序存储
通过特定的关键字进行搜索的最简单的方法是随机存储记录然后顺序读取，新的记录可以被简单的插入到文件的最后，已删除的记录可以标记为已删除或将记录移动，同数组中一样来填补空缺。
平均来看，查找和删除会涉及到读取半数的块，所以顺序存储并不快，时间复杂度为O(N)级，但是对于小量数据它仍然是可以选择的。
2.索引文件
使用索引文件时，速度会明显的提高。在这种方法中，关键字的索引和相应块的号数被存放在内存中，通过一个特殊的关键字访问一条记录时，程序会先向索引询问，索引提供这个关键字的块号数，然后只需要读取这一个块，仅耗费了O(1)级的时间。可以使用不同种类的关键字来做多种索引，只要索引数量能在内存的存储范围之内。通常，索引文件存储在磁盘上，只有在需要时才复制进内存中。
索引文件的缺点是必需先创建索引，这有可能会对磁盘上的文件进行顺序读取，所以创建索引是很慢的。当记录被加入到文件中时，索引还需要更新。
3.B-树
B-树是多叉树，通常用于外部存储，树中的节点对应于磁盘中的块。跟其他树一样，根据算法来遍历树，在每一层上读取一个块。B-树可以在O(logN)级的时间内进行查找，插入和删除，这样很快，并且对大文件也很有效。但是编程很麻烦。
4.哈希方法
外部哈希同索引文件有相同的存取时间O(1)，但它可以对更大的文件进行操作，如图选择外部存储结构：
5.虚拟内存
有时可以不需要编程，通过操作系统的虚拟内存来解决磁盘存取问题，如果读取一个大小超过主存的文件，虚拟内存系统会读取合适主存大小的部分并将其存储在磁盘上。当访问文件的不同部分时，它们会自动从磁盘读入并放置在内存中。可以对整个文件使用内部存储的算法，使它们好像同时都在内存中一样，如果文件的哪个部分不在内存中，也让操作系统去读取它们。当然，这个操作比整个文件在内存中的操作要慢的多，但是通过外部存储算法一块一块的处理文件的话，速度也是一样的慢。不要在乎文件的大小适合放在内存中，在虚拟内存的帮助下验证算法的好坏尤其是对那些比可用内存大不了多少的文件来说，这个解决方案更简单。
Java集合总结
Java集合是每个Java程序员在日常开发中都会使用到，而且有时候使用得好的话，能事半功倍。细数Java集合，其实比较常见的就是List、Set、Map和Queue，在这四者之中，除了Map之外，其他三个接口都继承于Collection。
在这里，首先我们要明确的是，List、Set、Map和Queue其实只是以接口的形式存在着的，所以在日常的程序开发中，请不要出现说想要直接初始化它们的想法和做法，虽然笔者也曾经犯过这样子的错误。
继承与Collection接口的–List接口
List接口本身的特点
List接口在Java的集合类中充当的是一个元素有序、元素可重复的集合角色。List继承于Collection集合，故其拥有了Collection集合的全部方法，同时，List集合也拥有属于自己的方法：用来实现根据元素索引来操作集合元素的作用。通过List集合的源码(JDK1.7)我们简单地看看List集合包含的方法:
package java.util;
public interface List extends Collection {
int size(); //集合元素的数量
boolean contains(Object o); //是否包含某变量，包含返回ture
Iterator<E> iterator();
Object[] toArray(); //将集合转化为一个数组，所有的集合元素变成相应的数组元素
<T> T[] toArray(T[] a); //将集合转化为一个类型T数组
boolean add(E e); //增加元素，成功返回true
boolean remove(Object o); //移除元素，成功返回true
boolean containsAll(Collection<?> c); //是否包含集合c中的全部元素，若是返回true
boolean addAll(Collection<extends E> c); //添加整个集合c中全部元素，
boolean addAll(int index, Collection<extends E> c);
boolean removeAll(Collection<?> c); //移除该List集合中包含的c中的全部元素
boolean retainAll(Collection<?> c); //是否包含c集合中的元素，包含返回ture
void clear(); //清空集合
boolean equals(Object o);
int hashCode();
E get(int index); //根据index取元素值
E set(int index, E element); //根据index把List该元素重新复制element
void add(int index, E element); //根据index添加新元素element
E remove(int index);
int indexOf(Object o); //返回对象o在List集合中第一次出现的位置索引
int lastIndexOf(Object o); //返回对象o在List集合中最后一次出现的位置索引
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex); //截断集合
}
常见的继承List接口的实用类
ArrayList
ArrayList是基于数组实现的List类，故其封装了一个动态的、允许再分配的Object[]数组，ArrayList用initialCapacity参数来设置该数组的长度，当长度超过预设值后，ArrayList会动态增加。
ArrayList类是线程不安全的，如果要保证该集合的同步性，必须在程序中手动保证。
值得注意的是：虽说与以链表形式建立的LinkedList相比，ArrayList()的插入和修改速度较慢，但那个也是建立在数据量较大的情况下的，在数据量较小的情况下，ArrayList()不一定比LinkedList()方法要慢。另外，ArrayList在末尾插入和删除数据的话，速度反而比LinkedList要快
LinkedList
LinkedList(): 在实现中采用链表数据结构。插入和删除速度快，访问速度慢。
因为除了继承List接口外，LinkedList接口也继承了Deque接口，故也可以当作“栈”和队列（双向队列）来使用。因此LinkList接口也会多出一些Deque接口方面的方法，如offer()（将元素接到队列的尾部）、push()或offerFirst()（将元素加入栈的顶部）、peek()或peekFirst()（访问但是不删除栈顶元素）、pop()或者pollLast()（将栈顶元素弹出栈）等方法。
Vector
Vector与ArrayList十分地相像，都是基于数组实现的List类，其也是封装了一个动态分配的Object[]数组，也可以使用initialCapacity参数来设置该数组的长度。
Vector是线程安全的，但是也因此Vector的性能很差。
Stack
Stack是继承与Vector的子类，它主要用来模拟”栈“，因此也具备了peek()、pop()、push()等主要用于栈操作的方法。
由于Stack是一个比较古老的Java集合类，它同样是线程安全的，但也因此暴露出了性能较差的缺点，如果程序中要使用栈这样的数据结构的话，可以试一试ArrayDeque，该类也是List的实现类，但和LinkedList一样也继承了Deque接口。
实用类对比
使用List集合有以下建议：
1、遍历集合元素。ArrayList和Vector使用get()方法来获取遍历元素，LinkedList应该采用迭代器来遍历集合元素。
2、插入和删除。当这类操作较多的时候，优先考虑使用LinkedList。
3、多线程。当需要使用到多线程的ArrayList时，可以使用Collections将该集合类包装成线程安全的集合。
继承与Collection接口的–Set接口
Set接口本身的特点
Set代表的是无序的、不可重复的集合。因此在Set集合中加入数据元素时，Set集合通常不用记住元素的添加顺序。不可重复则是说当将两个相同的元素加入到一个Set集合中，则添加操作失败，add()方法返回false，且新元素不会被添加。
public interface Set extends Collection {
int size(); //集合元素的数量
boolean isEmpty(); //判断集合是否为空
boolean contains(Object o); //是否包含某变量，包含返回ture
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c); //是否包含c集合中的元素，包含返回ture
boolean addAll(Collection<extends E> c); //添加包含c集合中所有的元素，包含返回ture
boolean retainAll(Collection<?> c);
boolean removeAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
}
常见的继承Set接口的实用类
HashSet
HashSet按照Hash算法来存储集合中的元素，因此具有良好的存取和查找功能。
HashSet有三个特点：与TreeSet不同，HashSet是无序的；不是线程同步；集合元素可以是null值。
HashSet集合的存储过程：当向HashSet集合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据该值决定该对象在HashSet中的存储位置。如果有两个元素通过equals()方法返回true，但他们的hashCode()方法返回值不相等，HashSet也会将其存储在不同的位置。也就是说:HashSet的添加元素判断标准是：两个对象通过equals()方法比较相等，并且两个对象的hashCode()方法返回值也相等。
LinkedHashSet
LinkedHashSet是继承于HashSet的子类。
但是与父类不同的是，LinkedHashSet用以链表的形式来维护元素的次序，也就是说：LinkedHashSet是有序的。遍历该集合时输出顺序为添加顺序。
TreeSet
TreeSet是SortedSet接口的实现类，所以TreeSet可以确保集合元素处于排序状态。TreeSet使用红黑树来维护集合元素的次序。如果实现comparator()方法，可以实现定制排序。如果采用自然排序，则返回null。
TreeSet集合的特有方法:first()、last()、lower(Object e)（返回指定元素之前的元素）、higher(Object e)（返回指定元素之后的元素）等等。
下面我们说一说TreeSet的定制排序和自然排序：
1、 定制排序
通过Comparator接口的帮助，实现降序排序。
2、 自然排序
TreeSet通过CompareTo（Object obj）比较元素之间的大小关系，将集合元素按升序排列。实现元素必须实现Comparable元素，而且在比较的时候如果出现不同类型时要转换类型后比较。
EnumSet
EnumSet是专门为枚举类设计的集合类，EnumSet中的所有元素都必须是指定枚举类型的枚举值，该枚举类型在创建EnumSet时显式或隐式地指定。
EnumSet在内部以位向量的形式存储，十分紧凑、高效，因此EnumSet对象占用内存很小，且运行效率很高。但是该集合元素中不允许加入null元素。
实用类对比
继承与Collection接口的–Queue接口
Queue接口本身的特点
Queue用来模拟队列这种数据结构，故其拥有add()、element()、offer()、peek()、poll()、remove()等方法。
package java.util;
public interface Queue extends Collection {
boolean add(E e); //在队尾增加元素e
boolean offer(E e); //在队尾增加元素e
E remove(); //获取队列头部的元素，并移除该元素
E poll(); //获取队列头部的元素，并移除该元素
E element(); //获取队列头部的元素，但不移除该元素
E peek(); //获取队列头部的元素，但不移除该元素
}
常见的继承Queue接口的实用类
PriorityQueue
PriorityQueue是Queue的标准队列实现类。PriorityQueue不是按照加入队列的顺序进行排列的，而是根据队列大小进行重新排序的（升序），这一点要特别注意的。
PriorityQueue中不允许插入null元素，它也有两种排序方式：自然排序（实现Comparable接口，且为同一个类比较）和定制排序（建立对象时传入一个Comparator对象）。这个部分和TreeSet的要求基本一致。
Deque–ArrayDeque
首先要说明的是:Deque是Queue的子接口，代表的是双向链表，故该接口中也定义了一些方法来从两端来操作队列的数据。
ArrayDeque：是一个基于数组实现的双端队列，它与ArratList的实现体制很相像，都会采用了动态可再分配的数组来存储集合元素。但是其在用途上主要是被当作”栈“来使用。
Deque–LinkedList
LinkedList在上述已表述过。与ArrayDeque不同的是，LinkedList是使用链表实现的。
特例独立的–Map接口
Map接口本身的特点
Map与上述三个接口不同的是，该接口无法继承于Collection接口，主要原因还是因为Map是用来存储具有映射关系的数据，所以Map中保存着两组值。一组值用来保存Map中的Key，另外一组用来保存Map里的value。值得注意的是：Map中的key不能重复。判断标准是同一个Map对象的任何两个key通过equals方法比较总是返回false。
package java.util;
public interface Map {
int size();
boolean isEmpty();
boolean containsKey(Object key); //是否包含key值，如果是返回true
boolean containsValue(Object value); //是否包含value值，如果是返回true
V get(Object key); //根据key值获取相应的value值
V remove(Object key); //根据key值从集合中移除相应的value值
void putAll(Map<extends K, extends V> m); //将指定的m中的key-value复制到该集合中
void clear();
Set<K> keySet(); //返回该Map中所有key组成Set集合
Collection<V> values(); //返回该Map中所有的value组成的Collection
//返回Map中包含的key-value对所组成的Set组合，每个集合元素都是Map.Entry对象。
Set<Map.Entry<K, V>> entrySet();
interface Entry<K,V> {
K getKey(); //返回该Entry里面包含的key值
V getValue(); //返回该Entry里面包含的value值
V setValue(V value); //设置原本的value值并返回该值
boolean equals(Object o);
int hashCode();
}
boolean equals(Object o);
int hashCode();
}
Map与Set相似度极高，将Map中的key和value分离开来看。key组是使用set集合方法来存储的。不仅如此，在子类的实现方面，两者也有很多的相似，所以你也会发现两者子类的命名很相像。
常见的继承Map接口的实用类
HashMap
HashMap是线程不安全的实现，且HashMap中可以使用null作为key或者value。
LinkedHashMap
LinkedHashMap使用一个双向链表来维护key-value对的次序，其也是一个有序的Map集合，顺序与key-value对的插入顺序保持一致。
TreeMap
TreeMap是一个红黑树的结构，每个key-value作为红黑树的一个节点。TreeMap也会对key进行排序，也分为自然排序和定制排序两种。
EnumMap
EnumMap是一个与枚举类一起使用的Map实现。
HashTable
HashTable是一个比较古老的Map实现类，它是一个线程安全的Map实现，且不允许使用null作为key和value。由于该类是比较久远的类，其性能较低，所以现在用的也比较少。
HashTable判断value相等的标准是：value与另外一个对象通过equals()方法返回true即可。
实用类对比
一般的应用场景，使用HashMap已经够用了。它非常适合于快速查询。但是如果程序需要一个排序的Map集合，可以考虑使用TreeMap。
操作集合的工具类：Collections
Java提供了一个操作Set、List和Map等集合的工具类：Collections，该类提供了大量的方法对集合元素进行排序、查询和修改等操作，还提供了将集合对象设置为不可变、对集合对象实现同步控制。
排序：reverse()(反转集合元素顺序)、shuffle()(随机排列)、sort()、swap()等方法。
查找和替换：binarySearch(list,obj)(二分查找指定List集合元素obj的索引)、max()、min()、fill()、frequency()(返回指定集合元素的出现次数)、replaceAll()等方法。
同步控制：Collections提供了多个synchronizedXxx()方法，该方法可以将指定的集合包装成线程同步的集合，进而解决了多线程并发访问集合时的线程安全问题。
设置不可变集合：Collections提供三个方法来返回一个不可变的集合：emptyXxx()(返回一个空的、不可变的集合对象)、singletonXxx()、unmodifiableXxx()方法。
1. Java 容器都有哪些？
Java 容器分为 Collection 和 Map 两大类，其下又有很多子类，如下所示：
Collection：
List
ArrayList
LinkedList
Vector
Stack
Set
HashSet
LinkedHashSet
TreeSet
Map：
HashMap
LinkedHashMap
TreeMap
ConcurrentHashMap
Hashtable
2. Collection 和 Collections 有什么区别？
- Collection 是一个集合接口，它提供了对集合对象进行基本操作的通用接口方法，所有集合都是它的子类，比如 List、Set 等。
- Collections 是一个包装类，包含了很多静态方法，不能被实例化，就像一个工具类，比如提供的排序方法： Collections. sort(list)。
3. List、Set、Map 之间的区别是什么？
List、Set、Map 的区别主要体现在两个方面：元素是否有序、是否允许元素重复。
三者之间的区别，如下表：
4. HashMap 和 Hashtable 有什么区别？
HashMap是非线程安全的，HashTable是线程安全的。
HashMap的键和值都允许有null值存在，而HashTable则不行。
因为线程安全的问题，HashMap效率比HashTable的要高。
Hashtable是同步的，而HashMap不是。因此，HashMap更适合于单线程环境，而Hashtable适合于多线程环境。
一般现在不建议用HashTable,
①是HashTable是遗留类，内部实现很多没优化和冗余。
②即使在多线程环境下，现在也有同步的ConcurrentHashMap替代，没有必要因为是多线程而用HashTable。
5. 如何决定使用 HashMap 还是 TreeMap？
对于在 Map 中插入、删除、定位一个元素这类操作，HashMap 是最好的选择，因为相对而言 HashMap 的插入会更快，但如果你要对一个 key 集合进行有序的遍历，那 TreeMap 是更好的选择。
6. 说一下 HashMap 的实现原理？
HashMap 基于 Hash 算法实现的，我们通过 put(key,value)存储，get(key)来获取。当传入 key 时，HashMap 会根据 key. hashCode() 计算出 hash 值，根据 hash 值将 value 保存在 bucket 里。当计算出的 hash 值相同时，我们称之为 hash 冲突，HashMap 的做法是用链表和红黑树存储相同 hash 值的 value。当 hash 冲突的个数比较少时，使用链表否则使用红黑树。
7. 说一下 HashSet 的实现原理？
HashSet 是基于 HashMap 实现的，HashSet 底层使用 HashMap 来保存所有元素，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成，HashSet 不允许重复的值。
8. ArrayList 和 LinkedList 的区别是什么？
- 数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。
- 随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。
- 增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标。
综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。
9. 如何实现数组和 List 之间的转换？
- 数组转 List：使用 Arrays. asList(array) 进行转换。
- List 转数组：使用 List 自带的 toArray() 方法。
代码示例：
// list to array
List<String> list = new ArrayList<String>();
list. add("叶痕秋");
list. add("的诗情画意");
list. toArray();
// array to list
String[] array = new String[]{"王磊","的诗情画意"};
Arrays. asList(array);
10. ArrayList 和 Vector 的区别是什么？
- 线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而 ArrayList 是非线程安全的。
- 性能：ArrayList 在性能方面要优于 Vector。
- 扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，只不过在 Vector 扩容每次会增加 1 倍，而 ArrayList 只会增加 50%。
11. Array 和 ArrayList 有何区别？
- Array 可以存储基本数据类型和对象，ArrayList 只能存储对象。
- Array 是指定固定大小的，而 ArrayList 大小是自动扩展的。
- Array 内置方法没有 ArrayList 多，比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。
12. 在 Queue 中 poll()和 remove()有什么区别？
- 相同点：都是返回第一个元素，并在队列中删除返回的对象。
- 不同点：如果没有元素 poll()会返回 null，而 remove()会直接抛出 NoSuchElementException 异常。
代码示例：
Queue<String> queue = new LinkedList<String>();
queue. offer("string"); // add
System. out. println(queue. poll());
System. out. println(queue. remove());
System. out. println(queue. size());
13. 哪些集合类是线程安全的？
Vector、Hashtable、Stack 都是线程安全的，而像 HashMap 则是非线程安全的，不过在 JDK 1.5 之后随着 Java. util. concurrent 并发包的出现，它们也有了自己对应的线程安全类，比如 HashMap 对应的线程安全类就是 ConcurrentHashMap。
14. 迭代器 Iterator 是什么？
Iterator 接口提供遍历任何 Collection 的接口。我们可以从一个 Collection 中使用迭代器方法来获取迭代器实例。迭代器取代了 Java 集合框架中的 Enumeration，迭代器允许调用者在迭代过程中移除元素。
15. Iterator 怎么使用？有什么特点？
Iterator 使用代码如下：
List<String> list = new ArrayList<>();
Iterator<String> it = list. iterator();
while(it. hasNext()){
String obj = it. next();
System. out. println(obj);
}
Iterator 的特点是更加安全，因为它可以确保，在当前遍历的集合元素被更改的时候，就会抛出 ConcurrentModificationException 异常。
16. Iterator 和 ListIterator 有什么区别？
- Iterator 可以遍历 Set 和 List 集合，而 ListIterator 只能遍历 List。
- Iterator 只能单向遍历，而 ListIterator 可以双向遍历（向前/后遍历）。
- ListIterator 从 Iterator 接口继承，然后添加了一些额外的功能，比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置。
17. 怎么确保一个集合不能被修改？
可以使用 Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合，这样改变集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。
示例代码如下：
List<String> list = new ArrayList<>();
list. add("x");
Collection<String> clist = Collections. unmodifiableCollection(list);
clist. add("y"); // 运行时此行报错
System. out. println(list. size());