前言
大家好,我是你們的老朋友青戈,知道你們想我了,所以我又來了?
Java的資料結構是面試考察的重點,只要參與過Java面試的同學相信都有所體會。面試官問這類問題的時候往往是想檢視你是否研究過Java中常用資料類型的底層結構,而不是只是簡單的停留在"會使用"的層次。那麼在面試的過程中我們要如何把這個問題說好,讓面試官滿意呢?
本期我將針對Java高頻考點ArrayList和LinkedList
的原理進行分析,希望能幫助你。
ArrayList和LinkedList簡介
ArrayList
底層是一個Object類型的數組,初始容量是10,支援動態擴容,擴容後的容量是目前容量的1.5倍,它的最大容量是Integer.MAX_VALUE - 8(但是仍可以擴容到Integer.MAX_VALUE),對於空出的8位,目前的解釋是避免一些機器記憶體溢出,減少出錯幾率
。
LinkedList
底層是雙向鍊錶,初始容量是0,擴容只需新建節點進行指標指向即可。
為了簡化成口頭可表述的語言,方便同學們在面試的時候向面試官解釋,我這裡就不貼源碼輔助說明了,有興趣的同學可以自己翻源碼看看內部的構造和方法,加深對這塊的理解。
區別
# ArrayList隨機存取效率很高,因為元素的儲存是有序的,透過下標index可以知道所查詢資料在記憶體中的位置,尋址快,時間複雜度O(1); #LinkedList查詢效率較低,它在查詢指定資料的時候需要遍歷鍊錶逐一查詢,時間複雜度O(n)。
插入
ArrayList在尾部插入的效率比較高,時間複雜度O(1),但在其他位置插入效率則比較低,需要進行大量的資料移動,時間複雜度O(n); #LinkedList在頭部和尾部插入元素的效率比較高,時間複雜度為O(1),但在中間指定位置插入元素,需要先遍歷找到元素的位置,再插入,時間複雜度O(n)。
刪除
#ArrayList移除元素除了結尾節點之外都伴隨著需要進行大量的資料移動,時間複雜度O(n); LinkedList刪除元素效率相對較高,只需要改變指標的指向,但是刪除元素需要遍歷查詢出資料的位置,時間複雜度O (n)。
記憶體空間
#ArrayList基於數組實現,每次擴容後容量是固定的,所以在尾部會預留一部分的空間; LinkedList是基於雙向鍊錶實現,所以每個節點除了保存資料之外還需要保存前後節點的指針,會消耗一部分空間。
擴充機制
#ArrayList每次擴容需要把原數組的元素複製到新的陣列裡面去; LinkedList是鍊錶,不存在擴容的說法。
相同點
執行緒安全性
#ArrayList和LinkedList都是線程不安全的,多線程環境下容易造成髒讀的問題,可以使用Collections.synchronizedList()
方法保證線程的安全性
#儲存特點
儲存的元素都是有順序的,都是可以重複的,新增元素都是儲存到List的結尾處。
以上是幾乎所有Java面試都會問到的問題:說ArrayList和LinkedList的差別的詳細內容。更多資訊請關注PHP中文網其他相關文章!

熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

AI Hentai Generator
免費產生 AI 無盡。

熱門文章

熱工具

MantisBT
Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

Dreamweaver Mac版
視覺化網頁開發工具

ZendStudio 13.5.1 Mac
強大的PHP整合開發環境

MinGW - Minimalist GNU for Windows
這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

SublimeText3漢化版
中文版,非常好用