[Day19][資結]LinkedList 與 Queue

2022 iThome 鐵人賽

DAY 19

Software Development

櫛風風的「完全不會寫程式，從零開始的 Kotlin 教學」系列第 19 篇

14th鐵人賽

櫛風

2022-10-04 22:40:06

1018 瀏覽

分享至

今天介紹的資料結構叫做LinkedList。

他跟mutablelist一樣是可以增加資料的，只是他儲存的方式有點不一樣。

陣列的資料是一格格來排的，所以可以很方便的去取得資料，但linkedlist其實是一個資料指一個資料，所以在刪除資料上會比較方便。

我們這裡介紹五個method，分別是在前面新增東西addFirst()，在後面新增東西addLast()，刪除第一項removeFirst()、刪除最後項removeLast()，跟判斷是否為空isEmpty()（我也不太清楚為什麼前面兩個是empty，這卻叫isEmpty）

當然他還是能像陣列一樣使用[]取得特定某一格，不過他取得的速度會比陣列慢喔。

具體的原理我們就先不解釋了，先記得「功能上如果比較常取特定格，那就用陣列；如果很常增刪就用LinkedList」，真的想知道的話，上網搜尋「陣列跟LinkedList的差別」，應該會有很多資料。

import java.util.LinkedList

fun main(){
    var a = LinkedList<Int>()
    a.addFirst(12)
    a.addLast(13)
    println("${a[1]}")
    a.removeFirst()
    a.removeLast()
    if(a.isEmpty()==false){
        println("a is not empty.")
    }
}

聰明的小夥伴可能已經發現了，其實在使用addLast跟removeFirst，跟我們前面介紹的Stack功能其實是一樣的喔。

所以我們這邊順便介紹另外一個資結，Queue佇列。

他的概念跟Stack某些地方剛好反過來，Queue是「最後放的，最後拿出來」，就像是排隊一樣，所以很常被拿來做排隊相關的程式，後面的BFS也會用到。

但是Queue的宣告比較特別，他是利用一個叫做interface的概念來做的，原理是什麼我們也不討論，知道怎麼宣告就好。

import java.util.Queue
import java.util.LinkedList

fun main(){
    var q: Queue<Int> = LinkedList<Int>()

}

沒錯，我們後面其實塞的是一個LinkedList，不過透過前面的Queue可以把他變成queue來使用。（所以queue跟linkedlist都要import喔）

queue的method有這些，在後面新增項add()、在查看第一項peek()、刪除最前面remove()、判斷是否為空isEmpty()。

那我們簡單來做一個排隊程式吧。


import java.util.Queue
import java.util.LinkedList

fun main(){
    var q: Queue<Int> = LinkedList<Int>()
    q.add(1)
    q.add(2)
    q.add(3)

    while(q.isEmpty() == false){
        print("${q.peek()} ")
        q.remove()
    }
}