iT邦幫忙

2021 iThome 鐵人賽

DAY 15
0
自我挑戰組

Java SE系列 第 15

Day15:刀槍與弓箭

初學寫程式的時候,常常會用到陣列(array)的概念,當我們想儲存一堆有順序性的值或變數時,就會把它們裝進一個陣列之中,後續可以拿來跑迴圈或取出需要的值出來。

由於Java有介面與物件繼承的概念,當學到集合(collection)的時候,有發現新大陸的感覺(起碼對我來說是這樣啦),原來把一堆東西裝進某個東西的概念不只有陣列,還有這多麼其他的樣式,甚至單單一個串列(List,相當於陣列array,為了和Java陣列的型別作區別),底下還可以分支出其他實作種類的陣列,整個就像生物學的界門綱目科屬種一樣。今天這篇就要來談談2個最常見的陣列:索引陣列(ArrayList)與鏈結陣列(LinkedList)。

索引陣列就是大家最熟悉的那種陣列了,而它在底層的實作也就如大家最直覺的想像一樣,把所有東西都標上號碼(就是索引,index),然後一個蘿蔔一個坑放在陣列中;我們可以根據索引(index)直接地拿出該索引代表的物件出來。不過如果我們需要調整陣列中元素的位置時,對電腦來說就是一個大工程了,因為原本的元素都站好茅坑了,假設要在中間插一個元素進來,前面的元素不打緊,但後面的可就累了,要站起來全部往後挪一個位置。因為這樣的特性,所以大家常說若這個陣列不太會有寫入資料的需求,比較常讀取的話,就適用索引陣列(ArrayList)

為了解決原本陣列這樣改動位置就需要全部的元素跟著變動的特性,出現了鏈結陣列這樣的東西,要了解鏈結陣列,先有類別型態的概念會比較能理解。
廢話不多說,我們上圖:
LinkedList
鏈結陣列利用變數(stack memory)存取物件(heap memory)位址值的架構,讓陣列不直接存取我們想存放的物件型態本身,而是放入一個類似中介身分的節點物件(node),而在這個節點之中,存放2個變數,1個存放我們本來想放的元素本身,1個存放下一個node物件的位址值。除了node以外,鍵結陣列本身也必須要有一個變數first來存放第一個node物件的位址值。

可能有人會想,搞這麼複雜在幹嘛,直接放我們想放的元素有甚麼問題嗎,還要搞一堆類似路牌的變數存一堆東西幹嘛......

其實目的就是當我們要在陣列中間插一個元素進來時,我們不用再像ArrayList一樣大風吹了!只要把目標位置前一個node的next變數更換成我們插進來的node,然後插進來的node的next再指向下一個node就搞定了!

不過LinkedList的缺點除了看起來概念複雜外(這是對初學的人來說的缺點哈哈哈),實際上也有缺點的,大家可以想想看,如果我們要存取比如說第3個索引值所代表的元素時,該怎麼辦?相較於ArrayList可以直接秒速取出,LinkedList底層運作會開始很笨的從first,一路count到目標的索引值,再取出目標元素。所以就會有這樣的結論:若陣列有大量寫入需求,大於讀取需求時,推薦使用鏈結陣列

其實上文提到的結論也和陣列的大小有關才導致這樣的結果,ArrayList在創立的時候,會必須要一個預設的大小的,而若當我們存取超過這個預設大小時,底層就會再創一個更大的陣列,並開始一一把元素複製過來,消耗多餘的資源;反觀LinkedList,就沒有存放大小的問題了。


上一篇
Day14:鐵口直斷
下一篇
Day16:請說出暗號證明你的身份
系列文
Java SE30

尚未有邦友留言

立即登入留言