Java中Array List與Linked List的實現(xiàn)分析
一,前言
先來一張Collection集合圖。
今天分享一些關(guān)于Collection集合中的List,講真的集合這東西在網(wǎng)上真是老生常談了。說實話連本人都覺得膩了(哈哈),但是話又說回來,整個集合體系對于我們實際開發(fā)來說是非常重要的,所以還是有必要系統(tǒng)總結(jié)下。
不過在此之前先說說兩種數(shù)據(jù)結(jié)構(gòu),鏈表和紅黑樹。
1.1,鏈表
鏈表:linked list,由一系列結(jié)點node(鏈表中每一個元素稱為結(jié)點)組成,結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分:一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域,另一個是存儲下一個結(jié)點地址的指針域。我們常說的鏈表結(jié)構(gòu)有單向鏈表與雙向鏈表,那么這里給大家介紹的是單向鏈表。
簡單的說,采用該結(jié)構(gòu)的集合,對元素的存取有如下的特點:
多個結(jié)點之間,通過地址進行連接。例如,多個人手拉手,每個人使用自己的右手拉住下個人的左手,依次類推,這樣多個人就連在一起了。
查找元素慢:想查找某個元素,需要通過連接的節(jié)點,依次向后查找指定元素。
增刪元素快:
- 增加元素:只需要修改連接下個元素的地址即可。
刪除元素:只需要修改連接下個元素的地址即可。
1.2,紅黑樹
紅黑樹是一種自平衡二叉查找樹,是計算機科學領(lǐng)域中的一種數(shù)據(jù)結(jié)構(gòu),典型的用途是實現(xiàn)關(guān)聯(lián)數(shù)組,存儲有序的數(shù)據(jù)。
紅黑樹本身就是一顆二叉查找樹,將節(jié)點插入后,該樹仍然是一顆二叉查找樹。也就意味著,樹的鍵值仍然是有序的。
紅黑樹的約束:
- 節(jié)點可以是紅色的或者黑色的。
- 根節(jié)點是黑色的。
- 葉子節(jié)點(特指空節(jié)點)是黑色的。
- 每個紅色節(jié)點的子節(jié)點都是黑色的。
- 任何一個節(jié)點到其每一個葉子節(jié)點的所有路徑上黑色節(jié)點數(shù)相同。
紅黑樹的特點:
速度特別快,趨近平衡樹,查找葉子元素最少和最多次數(shù)不多于二倍。
二,List接口
2.1,簡介
java.util.List接口繼承自Collection接口,是單列集合的一個重要分支,習慣性地會將實現(xiàn)了List
接口的對象稱為List集合。在List集合中允許出現(xiàn)重復的元素,所有的元素是以一種線性方式進行存儲的,在程序中可以通過索引來訪問集合中的指定元素。另外,List集合還有一個特點就是元素有序,即元素的存入順序和取出順序一致。
那么List接口有什么特點。
- 它是一個元素存取有序的集合。例如,存元素的順序是1、2、3。那么集合中,元素的存儲就是按照1、2、3的順序完成的)。
- 它是一個帶有索引的集合,通過索引就可以精確的操作集合中的元素(與數(shù)組的索引是一個道理)。
- 集合中可以有重復的元素,通過元素的equals方法,來比較是否為重復的元素。
2.2,常用方法
List接口繼承Collection接口,因此在父類接口中的方法,List子接口全部都有,并且還增加通過索引的方式操作數(shù)據(jù)。
public void add(int index, E element)
: 將指定的元素,添加到該集合中的指定位置上。public E get(int index)
:返回集合中指定位置的元素。public E remove(int index)
: 移除列表中指定位置的元素, 返回的是被移除的元素。public E set(int index, E element)
:用指定元素替換集合中指定位置的元素,返回值的更新前的元素。
public class ListDemo { public static void main(String[] args) { // 創(chuàng)建List集合對象 List<String> list = new ArrayList<>(); // 往尾部添加 指定元素 list.add("ABC"); list.add("張三"); list.add("李四"); System.out.println(list); // add(int index,String s) 往指定位置添加 list.add(1,"DEF"); System.out.println(list); // String remove(int index) 刪除指定位置元素 返回被刪除元素 // 刪除索引位置為2的元素 System.out.println("刪除索引位置為2的元素"); System.out.println(list.remove(2)); System.out.println(list); // String set(int index,String s) // 在指定位置進行元素替代(改) // 修改指定位置元素 list.set(0, "三毛"); System.out.println(list); // String get(int index) 獲取指定位置元素 // 跟size() 方法一起用來遍歷的 for(int i = 0;i<list.size();i++){ System.out.println(list.get(i)); } //還可以使用增強for for (String string : list) { System.out.println(string); } } }
三,Array List(JDK8)
Array List底層是基于動態(tài)數(shù)組實現(xiàn)的,何以動態(tài)。在于它是一個可變的數(shù)組,根據(jù)實際情況它的容量可自動擴充,類似于在C語言中動態(tài)申請內(nèi)存的原理。(題外話:記得有一次面試,面試官問我arraylist是怎么實現(xiàn)的,我說是一個動態(tài)數(shù)組。然后把他嚇一跳,說一句讓我想清楚再說。我還以為說錯了,接著沉淀5秒鐘,就是一個可自動擴容的動態(tài)數(shù)組)。
其特點是增刪慢,查詢快。因為是基于數(shù)組實現(xiàn)那么就會存在索引,增刪就是對數(shù)據(jù)的更新,導致索引也會發(fā)生相應變化。但是存在索引值,所以對于查詢數(shù)據(jù)來說就很快了。如圖:
3.1,數(shù)組實現(xiàn)
為什么說底層是一個數(shù)組,請看源碼:
ArrayList在初始化時默認的數(shù)組容量為10,源碼如下:
3.2,構(gòu)造方法
1,定義無參構(gòu)造方法,初始化默認為10的空列表。
2,有參構(gòu)造,并且自定義初始化容量的大小。
3,將數(shù)據(jù)類型轉(zhuǎn)換為數(shù)組類型。
分析:
1,elementData = c.toArray();
將元素轉(zhuǎn)化成數(shù)組。
2,判斷數(shù)組大小是否為0,否則將默認EMPTY_ELEMENTDATA
賦值給數(shù)組。
3,接著里面的if判斷,判斷elementData是否成功轉(zhuǎn)換為數(shù)組,如果成功則調(diào)用Arrays.copyOf方法將元素值,數(shù)組大小,及數(shù)組類復制值到elementData數(shù)組中。
完成以上初始化步驟之后,接著我們可以調(diào)用add方法完成數(shù)據(jù)添加。
3.3,add方法
先介紹沒有指定索引的數(shù)據(jù)添加,請看add源碼:
分析:
1,ensureCapacityInternal(size + 1);
這個方法是判斷在添加數(shù)據(jù)之前,數(shù)組的容量是否夠用。這里就看下源碼的實現(xiàn)吧。
判斷是否要擴容。
說明:
首先size默認為0,然后size+1將參數(shù)傳過來。判斷if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
是不是第一次添加元素,如果是,則選取默認的容量大小10,正式將數(shù)組容量初始化為10.接著調(diào)用ensureExplicitCapacity(minCapacity);
這里是判斷是否需要進行擴容。這里我們假設不需要擴容,接著說完add方法最后一步。
2,elementData[size++] = e;
最后執(zhí)行這一步,將元素e添加到elementData數(shù)組中,并且大小加1,并完成元素添加。
3.4,擴容機制
上面我們說到在數(shù)組不擴容情況下元素是如何進行添加的,再來說說如何進行擴容。接著上面ensureExplicitCapacity(int minCapacity)
這個方法,判斷如果超出默認容量大小時,便調(diào)用grow(minCapacity);
方法開始進行擴容。
在這里先指出擴容的機制其實就是數(shù)組的復制,創(chuàng)建一個新的數(shù)組,將小容量數(shù)組的元素復制到容量較大的數(shù)組中,以此完成數(shù)組的擴容。
接著我們看源碼的實現(xiàn):
分析:
1,獲取舊數(shù)組的大小。
2,將大小擴大1.5倍。
3,新容量小于參數(shù)指定容量,修改新容量。
4,新容量大于最大容量,并指定新容量。
5,調(diào)用copyOf進行復制。
完成擴容。
四,線程不安全
Array List是線程不安全的,這點很重要,也是面試最常問的問題。那為什么是不安全的呢,下面簡單總結(jié)以下。
情況一:
假設現(xiàn)在有A,B兩個線程同時執(zhí)行add方法,而現(xiàn)在size = 9,于是:
1,A經(jīng)過以上步驟發(fā)現(xiàn)初始化容量為10,不需要進行數(shù)組擴容。
2,同時B也在執(zhí)行add方法,它判斷數(shù)組初始化容量也是10(size的值還是9),于是不進行數(shù)組擴容。接著A便執(zhí)行add方法,元素添加成功后,size = 10;此時B開始執(zhí)行add方法,但這個時候數(shù)組元素已經(jīng)添加滿了,B再添加就會造成數(shù)組下標越界異常。
情況二:
elementData[size++] = e;
這一步也有可能出現(xiàn)問題。
列表大小為0,即size=0。
線程A開始添加一個元素,值為A。此時它執(zhí)行第一條操作,將A放在了elementData下標為0的位置上。
接著線程B剛好也要開始添加一個值為B的元素,且走到了第一步操作。此時線程B獲取到size的值依然為0,于是它將B也放在了elementData下標為0的位置上。
而最終size大小為:
線程A開始將size的值增加為1線程B開始將size的值增加為2
針對這種情況,可以使用以下方式解決:
List<String> list1 = Collections.synchronizedList(new ArrayList<String>());
五,Linked List
linked list數(shù)據(jù)存儲的結(jié)構(gòu)是雙向鏈表結(jié)構(gòu)。方便元素添加、刪除的集合,但是查詢較慢。
LinkedList中常用方法:
- public void addFirst(E e):將指定元素插入此列表的開頭。
- public void addLast(E e):將指定元素添加到此列表的結(jié)尾。
- public E getFirst():返回此列表的第一個元素。
- public E getLast():返回此列表的最后一個元素。
- public E removeFirst():移除并返回此列表的第一個元素。
- public E removeLast():移除并返回此列表的最后一個元素。
- public E pop():從此列表所表示的堆棧處彈出一個元素。
- public void push(E e):將元素推入此列表所表示的堆棧。
- public boolean isEmpty():如果列表不包含元素,則返回true。
public class LinkedListDemo { public static void main(String[] args) { LinkedList<String> link = new LinkedList<String>(); //添加元素 link.addFirst("abc1"); link.addFirst("abc2"); link.addFirst("abc3"); System.out.println(link); // 獲取元素 System.out.println(link.getFirst()); System.out.println(link.getLast()); // 刪除元素 System.out.println(link.removeFirst()); System.out.println(link.removeLast()); while (!link.isEmpty()) { //判斷集合是否為空 System.out.println(link.pop()); //彈出集合中的棧頂元素 } System.out.println(link); } }
六,總結(jié)
1,arraylist增刪慢,查詢快,基于動態(tài)數(shù)組。
2,linkedlist增刪快,查詢慢,基于雙向鏈表。
3,線程都不安全。
關(guān)于list接口中常用的兩個集合就分享到此,對于兩個集合要根據(jù)實際開發(fā)業(yè)務進行合理的選擇,并且要注意線程安全的問題。本來想把set接口也一起寫上,但是我覺得太長了,所以就留到下一篇博客。
好了,以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值,謝謝大家對腳本之家的支持。
相關(guān)文章
Mybatis中and和循環(huán)or混用操作(or轉(zhuǎn)換成in)
這篇文章主要介紹了Mybatis中and和循環(huán)or混用操作(or轉(zhuǎn)換成in),具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-07-07Docker環(huán)境下Spring Boot應用內(nèi)存飆升分析與解決場景分析
當運行一個Spring Boot項目時,如果未設置JVM內(nèi)存參數(shù),Spring Boot默認會采用JVM自身默認的配置策略,接下來通過本文給大家介紹Docker環(huán)境下Spring Boot應用內(nèi)存飆升分析與解決方法,需要的朋友參考下吧2021-08-08Maven及Springboot配置JDK版本,編碼,源碼打包等方式
這篇文章主要介紹了Maven及Springboot配置JDK版本,編碼,源碼打包等方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-12-12java Nio使用NioSocket客戶端與服務端交互實現(xiàn)方式
這篇文章主要介紹了java Nio使用 NioSocket 客戶端與服務端交互實現(xiàn)方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-06-06