List 集合介绍
List 集合概述
??List 集合是一个元素有序(每个元素都有对应的顺序索引, 第一个元素索引为 0), 且可重复的集合.
List 集合常用方法
??List 是 Collection 接口的子接口, 拥有 Collection 所有方法外, 还有一些对索引操作的方法.
void add(int index, E element);
: 将元素 element 插入到 List 集合的 index 处;
boolean addAll(int index, Collection<? extends E> c);
: 将集合 c 所有的元素都插入到 List 集合的 index 起始处;
E remove(int index);
: 移除并返回 index 处的元素;
int indexOf(Object o);
: 返回对象 o 在 List 集合中第一次出现的位置索引;
int lastIndexOf(Object o);
: 返回对象 o 在 List 集合中最后一次出现的位置索引;
E set(int index, E element);
: 将 index 索引处的元素替换为新的 element 对象, 并
返回被替换的旧元素
;
E get(int index);: 返回集合 index 索引处的对象;
List<E> subList(int fromIndex, int toIndex);
: 返回从索引 fromIndex(包含)到索引 toIndex(不包含)所有元素组成的子集合;
void sort(Comparator<? super E> c)
: 根据 Comparator 参数对 List 集合元素进行排序;
void replaceAll(UnaryOperator<E> operator)
: 根据 operator 指定的计算规则重新设置集合的所有元素.
ListIterator<E> listIterator();
: 返回一个 ListIterator 对象, 该接口继承了 Iterator 接口, 在 Iterator 接口基础上增加了以下方法, 具有向前迭代功能且可以增加元素:
bookean hasPrevious()
: 返回迭代器关联的集合是否还有上一个元素;
E previous();: 返回迭代器上一个元素;
void add(E e);: 在指定位置插入元素;
示例
1)运行主类
- public class DemoApplication {
- public static void main(String[] args) {
- List<String> list = new ArrayList();
- list.add(new String("book001"));
- list.add(new String("book002"));
- list.add(new String("book003"));
- System.out.println("原列表:" + list);
- // 将新字符串插入第二个位置
- list.add(1, new String("newBook002"));
- System.out.println("新增第二个位置元素后列表:" + list);
- // 删除第三个元素
- list.remove(2);
- System.out.println("删除第三个元素后列表:" + list);
- // 判断指定元素在 List 集合的位置
- System.out.println("判断 newBook002 的位置:" + list.indexOf(new String("newBook002")));
- // 将第二元素替换新的字符串
- System.out.println("替换的旧值:" + list.set(1, new String("book002")));
- System.out.println("替换第二个元素后的列表:" + list);
- // 返回第二个元素
- System.out.println("回第二个元素:" + list.get(1));
- List<String> newList = new ArrayList<>();
- newList.add("book001");
- newList.add("book004");
- newList.add("book002");
- // 新增集合
- list.addAll(1, newList);
- System.out.println("新增一个集合后的列表:" + list);
- // 返回元素最后一次出现的位置索引
- System.out.println("返回 \"book001\"最后一次出现的位置:" + list.lastIndexOf("book001"));
- // 截取子集合
- System.out.println("返回一个范围子集合列表:" + list.subList(0, 3));
- list.sort(new Comparator<String>() {
- @Override
- public int compare(String o1, String o2) {
- // 逆序
- return o2.compareTo(o1);
- }
- });
- //lambda 表达式输出
- list.forEach(book -> System.out.println(book));
- list.replaceAll(String::trim);
- System.out.println("replaceAll 去除两端空格" + list);
- list.replaceAll(t -> t.replace("book00", "书籍系列"));
- System.out.println("replaceAll 替换字符串:" + list);
- System.out.println("正向迭代输出:");
- ListIterator listIterator = list.listIterator();
- while (listIterator.hasNext()) {
- System.out.println(listIterator.next());
- // 添加元素, 会影响 list 元素
- listIterator.add("book");
- }
- System.out.println("反向迭代输出:");
- while(listIterator.hasPrevious()) {
- System.out.println(listIterator.previous());
- }
- System.out.println(list);
- }
- }
2)运行结果:
原列表:[book001, book002, book003 ]
新增第二个位置元素后列表:[book001, newBook002, book002, book003 ]
删除第三个元素后列表:[book001, newBook002, book003 ]
判断 newBook002 的位置: 1
替换的旧值: newBook002
替换第二个元素后的列表:[book001, book002, book003 ]
回第二个元素: book002
新增一个集合后的列表:[book001, book001, book004, book002, book002, book003 ]
返回 "book001" 最后一次出现的位置: 1
返回一个范围子集合列表:[book001, book001, book004]
- book004
- book002
- book002
- book001
- book001
- book003
replaceAll 去除两端空格[book004, book002, book002, book001, book001, book003]
replaceAll 替换字符串:[书籍系列 4, 书籍系列 2, 书籍系列 2, 书籍系列 1, 书籍系列 1, 书籍系列 3]
正向迭代输出:
书籍系列 4
书籍系列 2
书籍系列 2
书籍系列 1
书籍系列 1
书籍系列 3
反向迭代输出:
book
书籍系列 3
book
书籍系列 1
book
书籍系列 1
book
书籍系列 2
book
书籍系列 2
book
书籍系列 4
[书籍系列 4, book, 书籍系列 2, book, 书籍系列 2, book, 书籍系列 1, book, 书籍系列 1, book, 书籍系列 3, book]
?? 从上述运行结果看出, System.out.println("判断 newBook002 的位置:" + list.indexOf(new String("newBook002"))); 我们重新 new 一个 "newBook002" 进行判断索引位置时, 还是可以返回索引位置, List 集合判断两个对象相当只通过 equals()方法, 所以如果重写对象的 equals()方法都是 true, 则存入 List 集合中的对象其实都是相等的.
ArrayList
ArrayList 概述
?? ArrayList 是一个数组队列, 相当于动态数组. 与 Java 中的数组相比, 它的容量能动态增长. 它继承于 AbstractList, 实现了 List, RandomAccess(随机访问), Cloneable(克隆), java.io.Serializable(可序列化)这些接口.
??ArrayList 继承了 AbstractList, 实现了 List. 它是一个数组队列, 提供了相关的添加, 删除, 修改, 遍历等功能.
??ArrayList 实现了 RandmoAccess 接口, 即提供了随机访问功能. RandmoAccess 是 java 中用来被 List 实现, 为 List 提供快速访问功能的. 在 ArrayList 中, 我们即可以通过元素的序号快速获取元素对象; 这就是快速随机访问.
??ArrayList 实现了 Cloneable 接口, 即覆盖了函数 clone(), 能被克隆.
??ArrayList 实现 java.io.Serializable 接口, 这意味着 ArrayList 支持序列化, 能通过序列化去传输.
?? 和 Vector 不同, ArrayList 中的操作不是线程安全的! 所以, 建议在单线程中才使用 ArrayList, 而在多线程中可以选择 Vector 或者 CopyOnWriteArrayList.
ArrayList 源码解析
ArrayList 包含了两个重要的对象: elementData 和 size.
elementData 是 "Object[]类型的数组", 它保存了添加到 ArrayList 中的元素. 实际上, elementData 是个动态数组, 我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为 initialCapacity; 如果通过不含参数的构造函数 ArrayList()来创建 ArrayList, 则 elementData 的容量默认是 10.elementData 数组的大小会根据 ArrayList 容量的增长而动态的增长
size 则是动态数组的实际大小.
ArrayList 实际上是通过一个数组去保存数据的. 当我们构造 ArrayList 时; 若使用默认构造函数, 则 ArrayList 的默认容量大小是
10
.
当 ArrayList 容量不足以容纳全部元素时, ArrayList 会重新设置容量:
新的容量 ="(原始容量 x3)/2 + 1".
ArrayList 的克隆函数, 即是将全部元素克隆到一个数组中.
ArrayList 实现
java.io.Serializable
的方式. 当写入到输出流时, 先写入 "容量", 再依次写入 "每一个元素"; 当读出输入流时, 先读取 "容量", 再依次读取 "每一个元素".
ArrayList 的遍历方式
3 种方式
第一种, 通过迭代器遍历. 即通过 Iterator 去遍历.
- Integer value = null;
- Iterator iter = list.iterator();
- while (iter.hasNext()) {
- value = (Integer)iter.next();
- }
第二种, 随机访问 index, 通过索引值去遍历.
由于 ArrayList 实现了 RandomAccess 接口, 它支持通过索引值去随机访问元素.
- Integer value = null;
- int size = list.size();
- for (int i=0; i<size; i++) {
- value = (Integer)list.get(i);
- }
第三种,
增强 for 循环遍历
. 如下:
- Integer value = null;
- for (Integer integ:list) {
- value = integ;
- }
遍历 ArrayList 时, 使用随机访问 (即, 通过索引序号访问) 效率最高, 而使用迭代器的效率最低
LinkedList
LinkedList 概述
??LinkedList 是一个继承于 AbstractSequentialList 的双向链表. 它也可以被当作堆栈, 队列或双端队列进行操作. LinkedList 的本质是双向链表. 1)LinkedList 继承于 AbstractSequentialList, 并且实现了 Dequeue 接口. 2) LinkedList 包含两个重要的成员: header 和 size.
header 是双向链表的表头, 它是双向链表节点所对应的类 Entry 的实例. Entry 中包含成员变量: previous, next, element.(其中, previous 是该节点的上一个节点, next 是该节点的下一个节点, element 是该节点所包含的值.)
size 是双向链表中节点的个数.
??LinkedList 实现 List 接口, 能对它进行队列操作.
??LinkedList 实现 Deque 接口, 即能将 LinkedList 当作双端队列使用.
??LinkedList 实现了 Cloneable 接口, 即覆盖了函数 clone(), 能克隆.
??LinkedList 实现 java.io.Serializable 接口, 这意味着 LinkedList 支持序列化, 能通过序列化去传输.
??LinkedList 是非同步的.(若要实现同步 List list = Collections.synchronizedList(new LinkedList(...));)
LinkedList 源码分析
访问性
LinkedList 实际上是通过双向链表去实现的. 既然是双向链表, 那么它的
顺序访问会非常高效
, 而
随机访问效率比较低
.
根据索引值操作
既然 LinkedList 是通过双向链表的, 但是它也实现了 List 接口, 也就是说, 它实现了 get(int index),remove(int index)等根据索引值来获取, 删除节点的函数.
LinkedList 是如何实现 List 的这些接口的, 如何将双向链表和索引值联系起来的? 其实, 它是通过一个计数索引值来实现的. 例如, 当程序调用 get(int index)方法时, 首先会比较 location 和
双向链表长度的 1/2
; 如果前者大, 则从
链表头开始向后
查找, 直到 location 位置; 否则, 从
链表末尾开始向前
查找, 直到 location 位置.
总结:
LinkedList 实际上是通过双向链表去实现的. 包含一个非常重要的内部类: Entry.Entry 是双向链表节点所对应的数据结构, 它包括的属性有:
当前节点所包含的值
, 上一个节点, 下一个节点.
LinkedList 的克隆函数, 即是将全部元素克隆到一个新的 LinkedList 对象中.
LinkedList 实现
java.io.Serializable
. 当写入到输出流时, 先写入 "容量", 再依次写入 "每一个节点保护的值"; 当读出输入流时, 先读取 "容量", 再依次读取 "每一个元素".
由于 LinkedList 实现了 Deque, 而 Deque 接口定义了在双端队列两端访问元素的方法. 提供插入, 移除和检查元素的方法. 每种方法都存在两种形式: 一种形式在操作失败时抛出异常, 另一种形式返回一个特殊值(null 或 false, 具体取决于操作).
LinkedList 遍历方式
支持多种遍历方式. 建议不要采用随机访问的方式去遍历 LinkedList, 而采用逐个遍历的方式.
第一种, 通过迭代器遍历. 即通过 Iterator 去遍历.
- for(Iterator iter = list.iterator(); iter.hasNext();)
- iter.next();
通过快速随机 index 访问遍历 LinkedList
- int size = list.size();
- for (int i=0; i<size; i++) {
- list.get(i);
- }
通过另外一种增强版 for 循环来遍历 LinkedList
- for (Integer ele: list) {
- }
通过 pollFirst()来遍历 LinkedList,
获取并移除此列表的第一个元素
; 如果此列表为空, 则返回 null
- while(list.pollFirst() != null){
- }
通过 pollLast()来遍历 LinkedList,
获取并移除此列表的最后一个元素
; 如果此列表为空, 则返回 null.
- while(list.pollLast() != null) {
- }
通过 removeFirst()来遍历 LinkedList,
移除并返回此列表的第一个元素
. NoSuchElementException - 如果此列表为空.
- try {
- while(list.removeFirst() != null) {
- }
- } catch (NoSuchElementException e) {
- }
通过 removeLast()来遍历 LinkedList,
移除并返回此列表的最后一个元素
.NoSuchElementException - 如果此列表为空.
- try {
- while(list.removeLast() != null) {
- }
- } catch (NoSuchElementException e) {
- }
- QA
ArrayList 底层动态扩容的原理?
??ArrayList 底层采用数组实现, 当使用不带参数的构造方法生成 ArrayList 对象时, 底层实际会生成一个长度为 10 的 Object 类型数组, 如果增加的元素个数超过 10 个, 则 ArrayList 底层会新生成一个数组, 长度为原数组的 1.5 倍 + 1, 然后将原数组的内容复制到新数组中去, 兵器后续增加的内容都会放入新数组中, 当新数组无法容纳新元素时, 又会重复上述步骤.
ArrayList 和 LinkedList 的区别?
底层实现: ArrayList 实现是基于动态数组的数据结构(新建一个数组进行扩容, 然后 copy 原来数组中内容, 实现数组可增长);LinkedList 是基于双向链表的数据结构, 其每个对象除了数据本身外, 还有两个引用, 分别指向前一个元素和后一个元素.
查询: 对于随机访问 get 和 set,ArrayList 支持; LinkedList 不支持, 因为 LinkedList 要移动指针.
增删: 对于新增和删除操作 add 和 remove, 在 ArrayList 的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动; 而在 LinkedList 的中间插入或删除一个元素的开销是固定的.
应用场景: ArrayList 适合一列数据的后面添加数据而不是在前面或中间, 且需要随机访问元素; LinkedList 适合在一列数据的前面或中间添加或删除数据, 且按照顺序访问其中的元素.
消耗内存: LinkedList 比 ArrayList 消耗更多的内存, 因为 LinkedList 中的每个节点都存储前后节点的引用.(双向链表)
ArrayList 和 Vector 的区别?
线程安全性: ArrayList 是非线程安全的, Vector 是线程安全的, 如果需要再迭代的时候对列表进行改变, 使用 CopyOnWriteArrayList.
效率: ArrayList 是非同步的, 效率高; Vector 是同步的, 效率低;
ArrayList 和 CopyOnWriteArrayList 的区别
和 ArrayList 继承于 AbstractList 不同, CopyOnWriteArrayList 没有继承于 AbstractList, 它仅仅只是实现了 List 接口.
ArrayList 的 iterator()函数返回的 Iterator 是在 AbstractList 中实现的; 而 CopyOnWriteArrayList 是自己实现 Iterator.
ArrayList 的 Iterator 实现类中调用 next()时, 会 "调用 checkForComodification()比较'expectedModCount'和'modCount'的大小"; 但是, CopyOnWriteArrayList 的 Iterator 实现类中, 没有所谓的 checkForComodification(), 更不会抛出 ConcurrentModificationException 异常!
Iterater 和 ListIterator 区别
遍历目标: 可以使用 Iterator 来遍历 Set 和 List 集合; 而 ListIterator 只能遍历 List.
遍历方向: Iterator 只可以后向顺序遍历; 而 ListIterator 可以双向遍历.
功能区别: ListIterator 从 Iterator 接口继承, 然后添加了一些额外的功能, 比如添加一个元素, 替换一个元素, 获取前面或后面元素的索引位置.
来源: http://www.bubuko.com/infodetail-3493543.html