javaSE（List集合ArrayList实现类与LinkedList实现类）day15

目录

List集合：

1、ArrayList类：

（1）数据结构：

（2）扩容机制

（3）ArrayList的初始化：

（4）ArrayList的添加元素方法

（5）快速生成集合列表

（6）集合的查看操作：

（7）集合的遍历：

（8）删除集合元素：

（9）修改元素：

 （10）其他方法：

（11）ArrayList的优缺点：

2、LinkedList类：

（1）数据结构：

（2）初始化：

(3)LinledList的常用方法：

（4）LinkedList的遍历：

（5）LinkList的优缺点：

二、ArrayList与LinkList的异同：

1、存储方式：

2、索引/指针：

3、增删元素本质：

4、随机访问性能：

5、适用场景：

总结：若需频繁通过索引访问元素（如查询操作多），优先选择 ArrayList。若需频繁在列表中间进行插入 / 删除操作，优先选择 LinkedList。

List集合：

        集合就是“由若干个确定的元素所构成的整体”，在程序中，一般代表保存若干个元素（数据）的某种容器类。在Java中，如果一个Java对象可以在内部持有（保存）若干其他Java对象，并对外提供访问接口，我们把这种Java对象的容器称为集合。很显然，Java的数组也可以看作是一种集合。

         List集合：在集合类中，List是最基础的一种集合：它是一种有序列表。List的行为和数组几乎完全相同：List内部按照放入元素的先后顺序存放，每个元素都可以通过索引确定自己的位置，List的索引和数组一样，从0开始。

1、ArrayList类：Arraylist 是List接口的实现类，实现了List等一系列的方法，可以创建单列集合对象，并且ArrayList在内存中分配连续的空间，实现了长度可变的动态数组，有序集合（插入的顺序==输出的顺序），在进行插入删除时，休要对后面的每一个元素进行操作（前移或者后移）。

（1）数据结构：ArrayList的底层是基于数组实现的，随着元素的增加而动态扩容，每次扩容为原来的~1.5倍,存在在一定的空间浪费，推荐使用有参初始化，避免空间的浪费，适用于连续性遍历读多写少的场景。

（2）扩容机制：ArrayList的底层以数组存储，无参构造创建对象时默认初始容量为10，当调用add()方法添加元素时，首先会检查容量是否充足，充足，直接添加元素，如果当arraylist对象的size == elementData.length时，则除法扩容。遵循 新容量=旧容量+旧容量/2（扩容为元的1.5倍），若新容量仍小于所需最小容量，则直接使用所需最小容量作为新容量。再通过Arrays。copyOf()方法创建一个新的更大的数组，将原来的数组元素复制到新数组中，原数组elementData指向新数组，完成扩容。 

private void grow(int minCapacity) { int oldCapacity = elementData.length; // 扩容 1.5 倍 int newCapacity = oldCapacity + (oldCapacity >> 1); // 若新容量仍不足，直接使用所需最小容量 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 复制到新数组 elementData = Arrays.copyOf(elementData, newCapacity);}

（3）ArrayList的初始化：

    （1.1）无参初始化：ArrayList arrayList = new ArrayList();

    （1.2）单参初始化：ArrayList arrayList1 = new ArrayList(20);

    （1.3）传入Collection集合对象初始化（Arrays.asList()为工具类提供的快速传入元素的方法）：ArrayList arrayList2 = new ArrayList(Arrays.asList(\"张三\",\"李四\")); 

（4）ArrayList的添加元素方法：

（4.1）boolean add(E，e)添加元素：添加指定元素到集合尾部.

（4.2）void add(int index，E element)添加新元素到集合指定的下标位置

（4.3）boolean addAll(Collectionc) 添加集合C内所有元素到当前集台

（4.4）boolean addAll(int index,Collectionc)：从指定的位置开始，将指定collection 中的所有元素插入到此列表中

 ArrayList arrayList=new ArrayList(); boolean b1 = arrayList.add(\"g关羽\"); boolean b2 = arrayList.add(\"z张飞\"); boolean b3 = arrayList.add(\"d大乔\"); boolean b4 = arrayList.add(\"g关\"); System.out.println(\"第一次添加:\"+ b1); System.out.println(\"第二次添加:\"+ b4); arrayList.add(2,\"l李白\"); System.out.println(arrayList); List list = Arrays.asList(\"a阿拉善\",\"b北京\",\"d丹东\"); boolean b6 =arrayList.addAll(0,list); System.out.println(\"添加集合是否成功:\"+b6); System.out.println(arrayList);

（5）快速生成集合列表：使用工具类Arrays.asList（）方法快速生成集合：List list= Arrays.asList(\"李四\",\"王麻子\",\"王麻子\",\"王五\");

（6）集合的查看操作：

（6.1）int size() 查看集合的长度，具体元素的个数

（6.2）E get(int index)：获取集合指定下标的元素

  (6.3)   int indexOf(Object c)查找指定元素的下标，如果不存在返回-1；

（6.4）boolean contains(object c)  判断集合中是否存在指定元素

（6.5）boolean isEmpty()：判断集合是否为空。

（6.6）List subList(int fromIndex, int toIndex) 截取指定下标的元素：

（6.7）boolean equals(object o) 判断两个集合的内容是否相同

 ArrayList arrayList = new ArrayList(); arrayList.add(\"张三\"); System.out.println(arrayList); //使用工具类生成List集合 List list= Arrays.asList(\"李四\",\"王麻子\",\"王麻子\",\"王五\"); arrayList.addAll(list); System.out.println(\"集合的内容为：\"+arrayList); //查看 //1、int size() 查看集合的长度，具体元素的个数 System.out.println(\"长度：\"+arrayList.size()); //2、E get(int index) String item =arrayList.get(0); System.out.println(\"首元素：\"+item); System.out.println(\"尾元素:\"+arrayList.get(arrayList.size()-1)); //3、int indexOf(Object c)查找指定元素的下标，如果不存在返回-1； int index = arrayList.indexOf(\"王麻子\"); System.out.println(\"元素下标为:\"+index); //4.boolean contains(object c) boolean b = arrayList.contains(\"王麻子\"); System.out.println(\"元系是否存在:\"+b); //5.boolean isEmpty() boolean b1 = arrayList.isEmpty(); System.out.println(\"是否为空:\"+b1); //16.截取集合 List subArrayList = arrayList.subList(0,arrayList.size()); System.out.println(\"载取后的集合为:\"+subArrayList); //7.boolean equals(object o) boolean b2 =arrayList.equals(subArrayList); System.out.println(\"集合和截取后的集合是否相等:\"+b2);

（7）集合的遍历：

（7.1）for 循环遍历  

（7.2）增强for(foreach)遍历

（7.3）Iterator iterator():普通迭代器遍历

（7.4）ListIterator listIterator() 和ListIterator listIterator(int index)（带参数的可以逆序遍历）List迭代器遍历

package com.yuan.arraylistclass;import java.util.*;public class Demo05 { public static void main(String[] args) { ArrayList arrayList = new ArrayList(); //使用工具类生成List集合 arrayList.addAll(Arrays.asList(\"张三\", \"李四\", \"王麻子\", \"王麻子\", \"王五\")); System.out.println(\"集合的内容为：\" + arrayList); //遍历集合: // 1.for for (int i = 0; i < arrayList.size(); i++) { System.out.print(arrayList.get(i) + \"\"); } System.out.println(); //2.foreach for (String str : arrayList) { System.out.print(str + \"__\"); } System.out.println(); //3、迭代器 //3.1获取迭代器对象： Iterator itor = arrayList.iterator(); //判断是否有下一个 while (itor.hasNext()) { //获取下一个 String item = itor.next(); System.out.println(item + \"**\"); } System.out.println(); //3.2获跟list送代器对象 ListIterator listIterator = arrayList.listIterator(arrayList.size()); //判前是否有上一个元素 while (listIterator.hasPrevious()) { //获取上一个 String item = listIterator.previous(); System.out.println(item); } }}

（8）删除集合元素：

（8.1）E remove(int index):根据指定索引删除元素并把删除的元素返回.

（8.2）boolean remove(Object o):从集合中删除指定的元素，删除一个就返回

（8.3）void clear（):删除集合中的所有元素，此集合仍旧存在，集合元素长度变0

（8.4）boolean removeAll(Collection c)--- 差集：从集合中删除一个指定的集合元素：
删除A集合中存在B集合中的所有相同的元素，如果有删除返回True，谁调用操作的是就是谁

（8.5）boolean retainAll(Collection c)   --交集：保留集合A和集合B中相同的元素，删除不同的元素，谁调用操作的是就是谁

 ArrayList arrayList = new ArrayList(); //使用工具类生成List集合 arrayList.addAll(Arrays.asList(\"张三\", \"李四\", \"王麻子\", \"王麻子\", \"王五\")); System.out.println(\"集合的内容为：\" + arrayList);  //E remove(int index):根据指定索引删除元素并把删除的元素返回 String item = arrayList.remove( 0); System.out.println(\"删除的元素为:\"+item); //boolean remove(Object o):从集合中删除指定的元素，删除一个就返回 boolean b= arrayList.remove(\"王五\"); System.out.println(\"删除的元素是否成功:\"+b); //void clear():删除集合中的所有元素，此集合仍旧存在，集合元素长度变0 arrayList.clear(); System.out.println(\"操作后的集合为:\"+arrayList);

 //交集差集： ArrayList list1 =new ArrayList(); ArrayList list2 = new ArrayList(); list1.addAll(Arrays.asList(\"朱元璋\",\"朱祁镇\",\"朱祁镇\",\"朱棣\",\"朱高炽\")); list2.addAll(Arrays.asList(\"孙皇后\",\"朱祁镇\",\"朱棣\",\"李时珍\",\"郑和\")); System.out.println(\"list1:\"+list1); System.out.println(\"list2:\"+list2); //boolean retainAll(Collection c) --交集 谁调用谁修改// boolean b=list1.retainAll(list2);// System.out.println(b);// System.out.println(\"list1和list2的交集：\"+list1); //boolean removeAll(Collection c) --差集 谁调用谁修改 boolean b1=list1.removeAll(list2); System.out.println(b1); System.out.println(\"list1和list2的差集：\"+list1); 

（9）修改元素：oldE    set(int index, E element)：用指定的元素替代此列表中指定位置上的元素。

String str = arrayList.set(2,\"小敏\");

 （10）其他方法：

（10.1）Object clone() 克隆一个集合，得到的一个长度，个数，内容，顺序完全一致的集合，复制了一份

  (10.2) list.sort()对list中的内容进行排序

  (10.3) object[]toArray()：将集合转为object类型数组

（10.4）T[] toArray(T[] a),返回的数组的长度以集合对象或者传入的参数的长度较长的那个为准。

package com.yuan.arraylistclass;import java.util.ArrayList;import java.util.Arrays;import java.util.Comparator;public class Demo08 { public static void main(String[] args) { //Object clone() 克隆一个集合，得到的一个长度，个数，内容，顺序完全一致的集合，复制了一份 ArrayList list1=new ArrayList(); list1.addAll(Arrays.asList(\"shh孙皇后\",\"zqz朱祁镇\",\"zd朱棣\",\"lsz李时珍\",\"zh郑和\")); //克隆 Object obj=list1.clone(); if(obj instanceof ArrayList){ ArrayListcloneList=(ArrayList)obj; System.out.println(cloneList); } //list.sort()对list中的内容进行排序 list1.sort(new Comparator() { @Override public int compare(String o1, String o2) {  //先按照字符串的长度排，长度相同按内容排  if (o1.length() == o2.length())  return o1.compareTo(o2);  return o1.length() - o2.length(); } }); System.out.println(\"排序后的结果：\"+list1); //object[]toArray() Object[] objs =list1.toArray(); System.out.println(\"转数组后:\"+Arrays.toString(objs)); //T[] toArray(T[] a),返回的数组的长度以集合对象或者传入的参数的长度较长的那个为准 String[] strs =list1.toArray(new String[10]); System.out.println(Arrays.toString(strs)); }}

（11）ArrayList的优缺点：

优点：查效率高，增加和删除的效率比较低   

缺点：添加和删除需要大量移动元素效率，按照内容查询效率低，线程不安全

2、LinkedList类：

        Linkedlist 是List接口的实现类，实现了List等一系列的方法，可以创建单列集合对象，并且LinkedList在底层是双链存储方式，以Node 节点的方式进行存储Node（Node prev, E element, Node next）：数据域：存储实际元素（E item）。前驱指针：指向当前节点的前一个节点（Node prev）。后继指针：指向当前节点的后一个节点（Node next）。在进行插入删除操作时，改变的只有相邻位置的指向，对其他元素不进行操作。

（1）数据结构：LinkedList 有三个成员变量：first :指代的是头节点，last:指代的尾节点，当链表为空时，first 和 last 均为 null。LinkedList可以双向访问，通过任意节点可快速找到其前驱和后继节点，便于双向遍历。增删元素时只需修改节点的指针指向，无需移动大量元素（与数组相比）。节点在内存中可分散存储，无需连续空间，避免数组扩容的性能开销（与ArrayList相比不需要扩容操作）。适合数据频繁的添加和删除操作，写多读少的场景。

（2）初始化：

（2.1）无参初始化：LinkedList LinkedList= new LinkedList();

（2.2）传入Collection集合对象初始化（Arrays.asList()为工具类提供的快速传入元素的方法）：LinkedList linkedlist= new LinkedList(Arrays.asList(\"张三\",\"李四\")); 

 LinkedList linkedlist= new LinkedList(); //使用工具类生成List集合 linklist.addAll(Arrays.asList(\"张三\", \"李四\", \"王麻子\", \"王麻子\", \"王五\")); System.out.println(\"集合的内容为：\" + linklist);

(3)LinledList的常用方法：

和ArrayListdou继承自List接口，拥有list的所有方法，跟ArrayList的用法一样，除此之外还有专属有LinkedList的方法。

（3.1）void addFirst(E e)：在链表头部插入元素

（3.2）void addLast(E e)：在链表尾部插入元素（等价于 add()）

（3.3）E getFirst()：获取头部元素（若为空则抛出异常）

（3.4）E getLast()：获取尾部元素（若为空则抛出异常）

（3.5）E removeFirst()：删除并返回头部元素（若为空则抛出异常）

（3.6）E removeLast()：删除并返回尾部元素（若为空则抛出异常）

 //1、创建LinkedList集合对象 LinkedList list = new LinkedList(); //2、添加元素 list.add(\"孙答应\"); list.add(0, \"狂徒\"); list.addAll(Arrays.asList(\"娘娘\", \"公公\")); list.addAll(1, Arrays.asList(\"小主\", \"一文红\")); list.addFirst(\"甄嬛\"); list.addLast(\"胖橘\"); System.out.println(list); //2、获取元素 String item =list.get(4); System.out.println(\"获取元素\"+item); System.out.println(\"首元素\"+list.getFirst()); System.out.println(\"尾元素\"+list.getLast()); //3、删除 String item1 =list.remove(); //删除首元素 System.out.println(\"删除首元素\"+item1); System.out.println(\"删除首元素\"+list.removeFirst()); System.out.println(\"删除尾元素\"+list.removeLast());

（4）LinkedList的遍历：

（4.1)   for 循环遍历  ---不推荐，链表使用for循环遍历，每遍历一个元素都需要从头开始查找。效率低。

（4.2）增强for(foreach)遍历

（4.3）Iterator iterator():普通迭代器遍历

（4.4）ListIterator listIterator() 和ListIterator listIterator(int index)（带参数的可以逆序遍历）List迭代器遍历

 //1、创建LinkedList集合对象 LinkedList list = new LinkedList(); //2、添加元素 list.add(\"孙答应\"); list.add(0, \"狂徒\"); list.addAll(Arrays.asList(\"娘娘\", \"公公\")); list.addAll(1, Arrays.asList(\"小主\", \"一文红\")); list.addFirst(\"甄嬛\"); list.addLast(\"胖橘\"); System.out.println(list); //2、获取元素 String item =list.get(4); System.out.println(\"获取元素\"+item); System.out.println(\"首元素\"+list.getFirst()); System.out.println(\"尾元素\"+list.getLast()); //3、删除 String item1 =list.remove(); //删除首元素 System.out.println(\"删除首元素\"+item1); System.out.println(\"删除首元素\"+list.removeFirst()); System.out.println(\"删除尾元素\"+list.removeLast()); //4、遍历 //---for循环 --不推荐// for (int i = 0; i < list.size(); i++) {// System.out.println(list.get(i));// } //----foreach for (String str:list) { System.out.println(str); } //----普通迭代器 Iterator itor=list.iterator(); while (itor.hasNext()){ System.out.println(itor.next()+\"-\"); } //----List迭代器 ListIterator listIterator=list.listIterator(3); //从下表3开始从后往前遍历 while (listIterator.hasPrevious()){ System.out.println(listIterator.previous()+\"*\"); }

（5）LinkList的优缺点：

优点：插入、删除元素效率高   

缺点：遍历和随机访问效率低下

二、ArrayList与LinkList的异同：

1、存储方式：

LinkedList：基于双向链表实现，节点通过指针连接，内存可不连续

ArrayList:   基于动态数组实现，需要连续的内存空间

2、索引/指针：

LinkedList：依赖节点的 prev/next 指针

ArrayList:    依赖数组索引（直接访问）

3、增删元素本质：

LinkedList：修改指针指向，增删只需修改指针，中间 / 头部操作效率高，需先定位节点。

ArrayList:    可能需要移动大量元素，在尾部增删效率高，但中间 / 头部增删需移动元素

4、随机访问性能：

LinkedList：差，需从表头 / 表尾遍历

ArrayList:    好，通过索引直接访问

5、适用场景：

LinkedList：读少写多

ArrayList:    读多写少

总结：若需频繁通过索引访问元素（如查询操作多），优先选择 ArrayList。若需频繁在列表中间进行插入 / 删除操作，优先选择 LinkedList。