Java中ArrayList與LinkedList的作用是什么

Java中ArrayList與LinkedList的作用是什么，針對(duì)這個(gè)問(wèn)題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問(wèn)題的小伙伴找到更簡(jiǎn)單易行的方法。

1.1，鏈表

鏈表:linked list,由一系列結(jié)點(diǎn)node（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。我們常說(shuō)的鏈表結(jié)構(gòu)有單向鏈表與雙向鏈表，那么這里給大家介紹的是單向鏈表。

簡(jiǎn)單的說(shuō)，采用該結(jié)構(gòu)的集合，對(duì)元素的存取有如下的特點(diǎn)：

多個(gè)結(jié)點(diǎn)之間，通過(guò)地址進(jìn)行連接。例如，多個(gè)人手拉手，每個(gè)人使用自己的右手拉住下個(gè)人的左手，依次類推，這樣多個(gè)人就連在一起了。

查找元素慢：想查找某個(gè)元素，需要通過(guò)連接的節(jié)點(diǎn)，依次向后查找指定元素。

增刪元素快：

增加元素：只需要修改連接下個(gè)元素的地址即可。

刪除元素：只需要修改連接下個(gè)元素的地址即可。

1.2，紅黑樹

紅黑樹是一種自平衡二叉查找樹，是計(jì)算機(jī)科學(xué)領(lǐng)域中的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實(shí)現(xiàn)關(guān)聯(lián)數(shù)組，存儲(chǔ)有序的數(shù)據(jù)。

紅黑樹本身就是一顆二叉查找樹，將節(jié)點(diǎn)插入后，該樹仍然是一顆二叉查找樹。也就意味著，樹的鍵值仍然是有序的。

紅黑樹的約束:

節(jié)點(diǎn)可以是紅色的或者黑色的。  根節(jié)點(diǎn)是黑色的。  葉子節(jié)點(diǎn)(特指空節(jié)點(diǎn))是黑色的。  每個(gè)紅色節(jié)點(diǎn)的子節(jié)點(diǎn)都是黑色的。  任何一個(gè)節(jié)點(diǎn)到其每一個(gè)葉子節(jié)點(diǎn)的所有路徑上黑色節(jié)點(diǎn)數(shù)相同。

紅黑樹的特點(diǎn):

速度特別快,趨近平衡樹,查找葉子元素最少和最多次數(shù)不多于二倍。

二，List接口

2.1，簡(jiǎn)介

java.util.List接口繼承自Collection接口，是單列集合的一個(gè)重要分支，習(xí)慣性地會(huì)將實(shí)現(xiàn)了List接口的對(duì)象稱為L(zhǎng)ist集合。在List集合中允許出現(xiàn)重復(fù)的元素，所有的元素是以一種線性方式進(jìn)行存儲(chǔ)的，在程序中可以通過(guò)索引來(lái)訪問(wèn)集合中的指定元素。另外，List集合還有一個(gè)特點(diǎn)就是元素有序，即元素的存入順序和取出順序一致。

那么List接口有什么特點(diǎn)。

它是一個(gè)元素存取有序的集合。例如，存元素的順序是1、2、3。那么集合中，元素的存儲(chǔ)就是按照1、2、3的順序完成的）。  它是一個(gè)帶有索引的集合，通過(guò)索引就可以精確的操作集合中的元素（與數(shù)組的索引是一個(gè)道理）。  集合中可以有重復(fù)的元素，通過(guò)元素的equals方法，來(lái)比較是否為重復(fù)的元素。

2.2，常用方法

List接口繼承Collection接口，因此在父類接口中的方法，List子接口全部都有，并且還增加通過(guò)索引的方式操作數(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集合對(duì)象 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) // 在指定位置進(jìn)行元素替代（改） // 修改指定位置元素 list.set(0, "三毛"); System.out.println(list); // String get(int index) 獲取指定位置元素 // 跟size() 方法一起用來(lái)遍歷的 for(int i = 0;i<list.size();i++){  System.out.println(list.get(i)); } //還可以使用增強(qiáng)for for (String string : list) {  System.out.println(string); } }}

三，Array List（JDK8）

Array List底層是基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的，何以動(dòng)態(tài)。在于它是一個(gè)可變的數(shù)組，根據(jù)實(shí)際情況它的容量可自動(dòng)擴(kuò)充，類似于在C語(yǔ)言中動(dòng)態(tài)申請(qǐng)內(nèi)存的原理。（題外話：記得有一次面試，面試官問(wèn)我arraylist是怎么實(shí)現(xiàn)的，我說(shuō)是一個(gè)動(dòng)態(tài)數(shù)組。然后把他嚇一跳，說(shuō)一句讓我想清楚再說(shuō)。我還以為說(shuō)錯(cuò)了，接著沉淀5秒鐘，就是一個(gè)可自動(dòng)擴(kuò)容的動(dòng)態(tài)數(shù)組）。

其特點(diǎn)是增刪慢，查詢快。因?yàn)槭腔跀?shù)組實(shí)現(xiàn)那么就會(huì)存在索引，增刪就是對(duì)數(shù)據(jù)的更新，導(dǎo)致索引也會(huì)發(fā)生相應(yīng)變化。但是存在索引值，所以對(duì)于查詢數(shù)據(jù)來(lái)說(shuō)就很快了。如圖：

3.1，數(shù)組實(shí)現(xiàn)

為什么說(shuō)底層是一個(gè)數(shù)組，請(qǐng)看源碼：

ArrayList在初始化時(shí)默認(rèn)的數(shù)組容量為10，源碼如下：

3.2，構(gòu)造方法

1，定義無(wú)參構(gòu)造方法，初始化默認(rèn)為10的空列表。

2，有參構(gòu)造，并且自定義初始化容量的大小。

3，將數(shù)據(jù)類型轉(zhuǎn)換為數(shù)組類型。

分析：

1，elementData = c.toArray();將元素轉(zhuǎn)化成數(shù)組。

2，判斷數(shù)組大小是否為0，否則將默認(rèn)EMPTY_ELEMENTDATA賦值給數(shù)組。

3，接著里面的if判斷，判斷elementData是否成功轉(zhuǎn)換為數(shù)組，如果成功則調(diào)用Arrays.copyOf方法將元素值，數(shù)組大小，及數(shù)組類復(fù)制值到elementData數(shù)組中。

完成以上初始化步驟之后，接著我們可以調(diào)用add方法完成數(shù)據(jù)添加。

3.3，add方法

先介紹沒(méi)有指定索引的數(shù)據(jù)添加，請(qǐng)看add源碼：

分析：

1，ensureCapacityInternal(size + 1);這個(gè)方法是判斷在添加數(shù)據(jù)之前，數(shù)組的容量是否夠用。這里就看下源碼的實(shí)現(xiàn)吧。

判斷是否要擴(kuò)容。

說(shuō)明：

首先size默認(rèn)為0，然后size+1將參數(shù)傳過(guò)來(lái)。判斷if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)是不是第一次添加元素，如果是，則選取默認(rèn)的容量大小10，正式將數(shù)組容量初始化為10.接著調(diào)用ensureExplicitCapacity(minCapacity);這里是判斷是否需要進(jìn)行擴(kuò)容。這里我們假設(shè)不需要擴(kuò)容，接著說(shuō)完add方法最后一步。

2，elementData[size++] = e;最后執(zhí)行這一步，將元素e添加到elementData數(shù)組中，并且大小加1，并完成元素添加。

3.4，擴(kuò)容機(jī)制

上面我們說(shuō)到在數(shù)組不擴(kuò)容情況下元素是如何進(jìn)行添加的，再來(lái)說(shuō)說(shuō)如何進(jìn)行擴(kuò)容。接著上面ensureExplicitCapacity(int minCapacity)這個(gè)方法，判斷如果超出默認(rèn)容量大小時(shí)，便調(diào)用grow(minCapacity);方法開始進(jìn)行擴(kuò)容。

在這里先指出擴(kuò)容的機(jī)制其實(shí)就是數(shù)組的復(fù)制，創(chuàng)建一個(gè)新的數(shù)組，將小容量數(shù)組的元素復(fù)制到容量較大的數(shù)組中，以此完成數(shù)組的擴(kuò)容。

接著我們看源碼的實(shí)現(xiàn)：

分析：

1，獲取舊數(shù)組的大小。

2，將大小擴(kuò)大1.5倍。

3，新容量小于參數(shù)指定容量，修改新容量。

4，新容量大于最大容量，并指定新容量。

5，調(diào)用copyOf進(jìn)行復(fù)制。

完成擴(kuò)容。

四，線程不安全

Array List是線程不安全的，這點(diǎn)很重要，也是面試最常問(wèn)的問(wèn)題。那為什么是不安全的呢，下面簡(jiǎn)單總結(jié)以下。

情況一：

假設(shè)現(xiàn)在有A，B兩個(gè)線程同時(shí)執(zhí)行add方法，而現(xiàn)在size = 9，于是：

1，A經(jīng)過(guò)以上步驟發(fā)現(xiàn)初始化容量為10，不需要進(jìn)行數(shù)組擴(kuò)容。

2，同時(shí)B也在執(zhí)行add方法，它判斷數(shù)組初始化容量也是10（size的值還是9），于是不進(jìn)行數(shù)組擴(kuò)容。接著A便執(zhí)行add方法，元素添加成功后，size = 10；此時(shí)B開始執(zhí)行add方法，但這個(gè)時(shí)候數(shù)組元素已經(jīng)添加滿了，B再添加就會(huì)造成數(shù)組下標(biāo)越界異常。

情況二：

elementData[size++] = e;這一步也有可能出現(xiàn)問(wèn)題。

列表大小為0，即size=0。 線程A開始添加一個(gè)元素，值為A。此時(shí)它執(zhí)行第一條操作，將A放在了elementData下標(biāo)為0的位置上。 接著線程B剛好也要開始添加一個(gè)值為B的元素，且走到了第一步操作。此時(shí)線程B獲取到size的值依然為0，于是它將B也放在了elementData下標(biāo)為0的位置上。 而最終size大小為：

線程A開始將size的值增加為1線程B開始將size的值增加為2

針對(duì)這種情況，可以使用以下方式解決：

List<String> list1 = Collections.synchronizedList(new ArrayList<String>());

五，Linked List

linked list數(shù)據(jù)存儲(chǔ)的結(jié)構(gòu)是雙向鏈表結(jié)構(gòu)。方便元素添加、刪除的集合，但是查詢較慢。

LinkedList中常用方法：

public void addFirst(E e):將指定元素插入此列表的開頭。  public void addLast(E e):將指定元素添加到此列表的結(jié)尾。  public E getFirst():返回此列表的第一個(gè)元素。  public E getLast():返回此列表的最后一個(gè)元素。  public E removeFirst():移除并返回此列表的第一個(gè)元素。  public E removeLast():移除并返回此列表的最后一個(gè)元素。  public E pop():從此列表所表示的堆棧處彈出一個(gè)元素。  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); }}

關(guān)于Java中ArrayList與LinkedList的作用是什么問(wèn)題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒(méi)有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識(shí)。