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<E>接口的實現類，實現了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<String> arrayList = new ArrayList<>();

? ? （1.2）單參初始化：ArrayList<String> arrayList1 = new ArrayList<>(20);

? ? （1.3）傳入Collection集合對象初始化（Arrays.asList()為工具類提供的快速傳入元素的方法）：ArrayList<String> 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(Collection<?extendsE>c) 添加集合C內所有元素到當前集臺

（4.4）boolean addAll(int index,Collection<?extends E>c)：從指定的位置開始，將指定collection 中的所有元素插入到此列表中

        ArrayList<String> 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<String> list = Arrays.asList("a阿拉善","b北京","d丹東");boolean b6 =arrayList.addAll(0,list);System.out.println("添加集合是否成功:"+b6);System.out.println(arrayList);

（5）快速生成集合列表：使用工具類Arrays.asList（）方法快速生成集合：List<String> 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<E> subList(int fromIndex, int toIndex) 截取指定下標的元素：

（6.7）boolean equals(object o) 判斷兩個集合的內容是否相同

        ArrayList<String> arrayList = new ArrayList<>();arrayList.add("張三");System.out.println(arrayList);//使用工具類生成List集合List<String> 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<String> 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<E> iterator():普通迭代器遍歷

（7.4）ListIterator<E> listIterator() 和ListIterator<E> listIterator(int index)（帶參數的可以逆序遍歷）List迭代器遍歷

package com.yuan.arraylistclass;import java.util.*;public class Demo05 {public static void main(String[] args) {ArrayList<String> arrayList = new ArrayList<>();//使用工具類生成List集合arrayList.addAll(Arrays.asList("張三", "李四", "王麻子", "王麻子", "王五"));System.out.println("集合的內容為：" + arrayList);//遍歷集合:// 1.forfor (int i = 0; i < arrayList.size(); i++) {System.out.print(arrayList.get(i) + "");}System.out.println();//2.foreachfor (String str : arrayList) {System.out.print(str + "__");}System.out.println();//3、迭代器//3.1獲取迭代器對象：Iterator<String> itor = arrayList.iterator();//判斷是否有下一個while (itor.hasNext()) {//獲取下一個String item = itor.next();System.out.println(item + "**");}System.out.println();//3.2獲跟list送代器對象ListIterator<String> 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<String> 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():刪除集合中的所有元素，此集合仍舊存在，集合元素長度變0arrayList.clear();System.out.println("操作后的集合為:"+arrayList);

       //交集差集： ArrayList<String> list1 =new ArrayList<>();ArrayList<String> 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<String> list1=new ArrayList<>();list1.addAll(Arrays.asList("shh孫皇后","zqz朱祁鎮","zd朱棣","lsz李時珍","zh鄭和"));//克隆Object obj=list1.clone();if(obj instanceof ArrayList){ArrayList<String>cloneList=(ArrayList<String>)obj;System.out.println(cloneList);}//list.sort()對list中的內容進行排序list1.sort(new Comparator<String>() {@Overridepublic 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<E>接口的實現類，實現了List<接口>等一系列的方法，可以創建單列集合對象，并且LinkedList在底層是雙鏈存儲方式，以Node<E> 節點的方式進行存儲Node（Node<E> prev, E element, Node<E> next）：數據域：存儲實際元素（E item）。前驅指針：指向當前節點的前一個節點（Node<E> prev）。后繼指針：指向當前節點的后一個節點（Node<E> next）。在進行插入刪除操作時，改變的只有相鄰位置的指向，對其他元素不進行操作。

（1）數據結構：LinkedList 有三個成員變量：first :指代的是頭節點，last:指代的尾節點，當鏈表為空時，first?和?last?均為?null。LinkedList可以雙向訪問，通過任意節點可快速找到其前驅和后繼節點，便于雙向遍歷。增刪元素時只需修改節點的指針指向，無需移動大量元素（與數組相比）。節點在內存中可分散存儲，無需連續空間，避免數組擴容的性能開銷（與ArrayList相比不需要擴容操作）。適合數據頻繁的添加和刪除操作，寫多讀少的場景。

（2）初始化：

（2.1）無參初始化：LinkedList<String> LinkedList= new LinkedList<>();

（2.2）傳入Collection集合對象初始化（Arrays.asList()為工具類提供的快速傳入元素的方法）：LinkedList<String> linkedlist= new LinkedList<>(Arrays.asList("張三","李四"));?

        LinkedList<String> linkedlist= new LinkedList<>();//使用工具類生成List集合linklist.addAll(Arrays.asList("張三", "李四", "王麻子", "王麻子", "王五"));System.out.println("集合的內容為：" + linklist);

(3)LinledList的常用方法：

和ArrayListdou繼承自List<E>接口，擁有list<E>的所有方法，跟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<String> 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<E> iterator():普通迭代器遍歷

（4.4）ListIterator<E> listIterator() 和ListIterator<E> listIterator(int index)（帶參數的可以逆序遍歷）List迭代器遍歷

  //1、創建LinkedList集合對象LinkedList<String> 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));
//        }//----foreachfor (String str:list) {System.out.println(str);}//----普通迭代器Iterator<String> itor=list.iterator();while (itor.hasNext()){System.out.println(itor.next()+"-");}//----List迭代器ListIterator<String> listIterator=list.listIterator(3);  //從下表3開始從后往前遍歷while (listIterator.hasPrevious()){System.out.println(listIterator.previous()+"*");}

（5）LinkList的優缺點：

優點：插入、刪除元素效率高? ?

缺點：遍歷和隨機訪問效率低下