鏈結串列(Linked List)& 陣列(Array)


「鏈結串列(linked list)」與「陣列(array)」都是線性資料結構,但兩者儲存與連接資料的方式不同,造就不同的操作方式與時間複雜度,各有其適合的使用時機。


資料儲存方式

「鏈結串列」中的資料都存在「節點(node)」中,節點除「資料(data)」外,另有「指標域(next)」,指標域中的「指標(pointer)」指向下一筆資料或「空值(null)」,每筆資料的儲存空間並不連續。

「陣列」以連續的記憶體空間儲存資料,每筆資料會對應其各自的「索引值(index number)」。


其他鏈結串列結構

除上述的「單向鏈結串列(singly linked list)」外,另可依照是否呈環狀、以及指標是否為雙向,區分為下列幾種不同的鏈結串列結構:

環狀鏈結串列(circular linked list, CLL)

單向鏈結串列延伸,最後一個節點指向第一個節點。

雙向鏈結串列(doubly linked list, DLL)

有頭有尾,每個節點都會同時往前往後指向相鄰資料。若欲處理的節點在鏈結串列後半段,從尾端出發可更快抵達。

雙向環狀鏈結串列(doubly circular linked list, DCLL)

雙向鏈結串列延伸,每個節點都同時往兩邊指向相鄰資料,無所謂頭尾之分。


操作方式

由於「鏈結串列」的每筆資料都是獨立的,針對當中的任一筆資料進行操作相對容易;相較之下,「陣列」當中的所有資料可視為一體,若要針對非尾端的資料進行操作,則「牽一髮而動全身」,會連帶影響記憶體中的其他資料。


鏈結串列(linked list)

只要調整鏈結串列特定節點的「指標」,就可以操作資料,其他節點都不會受到影響。在下列的操作說明中,皆以「單向鏈結串列」為範例。

從尾新增節點/push()

共可分為下列兩種情況:

  1. 鏈結串列中沒有節點:新增的節點就放在「head」。
  2. 鏈結串列中有其他節點:新增的節點會從「head」跑到最尾端,並連在既有的最後一個節點之後,成為最末端的節點。.

新增節點後,鏈結串列的長度+1。

從尾移除節點/pop()

共可分為下列三種情況:

  1. 鏈結串列中沒有節點:沒有任何節點可供移除,回傳「null」。
  2. 鏈結串列當中只有「head」一個節點:「head」變為「null」,長度變為 0。
  3. 鏈結串列中有超過一個節點:將倒數第二個節點改為指向「null」,就可使倒數第二個節點變成最後一個節點,鏈結串列長度–1;原本的最後一個節點仍存在於記憶體中,但不再與鏈結串列相連。

從頭新增節點/unshift()

共可分為下列兩種情況:

  1. 鏈結串列中沒有節點:新增的節點就放在「head」。
  2. 鏈結串列中有其他節點:「head」指向新的節點,新節點指向原本的第一個節點,使新節點變成第一個節點,原本的所有節點皆往後移一個位置。

新增節點後,鏈結串列的長度+1。

從頭移除節點/shift()

共可分為下列三種情況:

  1. 鏈結串列中沒有節點:沒有任何節點可移除,回傳「null」。
  2. 鏈結串列當中只有「head」一個節點:「head」變為「null」,長度變為 0。
  3. 鏈結串列中有超過一個節點:將「head」改為指第二個節點,長度–1;原本的第一個節點仍存在於記憶體中,但不再與鏈結串列相連。

從中間新增節點/insert()

共可分為下列四種情況:

  1. 欲插入位置超出鏈結串列範圍:無法新增節點,回傳「null」。
  2. 剛好放在鏈結串列最前面的位置:直接套用上述「unshift()」方法。
  3. 剛好放在鏈結串列最後面的位置:直接套用上述「push()」方法。
  4. 放在鏈結串列中間位置:假設要放在第 k 個位置,則將第 (k-1) 個節點連到新節點、新節點連到原第 (k+1) 個節點;完成後,原第 (k+1) 個節點起的每一個節點都往後移一個位置,鏈結串列的長度+1。

從中間移除節點/remove()

共可分為下列四種情況:

  1. 欲插入位置超出鏈結串列範圍:無法移除節點,回傳「null」。
  2. 剛好移除鏈結串列最前面的位置:直接套用上述「shift()」方法。
  3. 剛好移除鏈結串列最後面的位置:直接套用上述「pop()」方法。
  4. 移除鏈結串列中間位置:假設要移除第i個節點,則將第 (i-1) 個節點連到原本第 (i+2) 個節點,鏈結串列的長度–1;移除的節點仍存在於記憶體中,但不再與鏈結串列相連。

取得節點資訊/get()

可輸入索引值(鏈結串列並沒有真正的「索引值」,因此這裡稱的索引值比較像是自訂給這些節點的標示號碼),從最前面的節點開始依序尋找,直到下列兩種情況之一:

  1. 尋找的資料不在鏈結串列中:從頭找到最後一個節點皆無對應資料,回傳「null」。
  2. 節點在鏈結串列第 n 個位置:從第一個節點開始一路往下找,直到找到第 n 個節點為止。


陣列(array)

所有資料都是陣列中的元素,彼此相連,每個元素也都已經設定好對應的索引值。

從尾新增元素/push()

直接用「push()」方法完成。

從尾移除元素/pop()

直接用「pop()」方法完成,若陣列中無元素則回傳空陣列。

從頭新增元素/unshift()

直接用「unshift()」方式完成,但剩餘的每個元素都會被往後移動。

從頭移除元素/shift()

直接用「shift()」方式完成,但剩餘的每個元素都會被往前移動;若陣列中無元素則回傳空陣列。

從中間新增、移除元素/splice()

選定要新增與移除的位置索引值,再填入欲移除的元素數量,最後依序填入欲新增的元素內容;該元素之後的每個元素索引值都會改變。

若只要新增,則在選定索引值後,欲移除元素數量設為 0,再填入欲新增的元素內容,新增的元素與排在其後的元素索引值都會變大。

若只要移除,則在選定索引值後,填入欲移除的元素數量即可,移除處後每個元素的索引值都會變小。

取得資料/get()

直接輸入索引值即可完成。


程式碼範例(JavaScript)

下列程式碼內容皆可與上方的圖說對照。

鏈結串列:

建立「節點(Node)」與「鏈結串列(LinkedList)」這兩個物件時,將「建構子(contructor)」放進一「類別宣告(class declaration)」中,以完成初始化。

在「LinkedList」中,設定八個方法(methods)以便操作,包含上述的「push()」、「pop()」、「unshift()」、「shift()」、「insert()」、「remove()」與「get()」,另設定「printAll()」顯示鏈結串列全部資料。與陣列不同的是,這些方法名稱都是我們自己定義的,可以自行更改。

以下程式碼以「單向鏈結串列(singly linked list)」為例:

//製作一個節點,每個節點包含「value」與「next」兩屬性
class Node {
    constructor(value){
        this.value = value;
        this.next = null;
    }
}

//製作一個鏈結串列與相關的操作方法(method)
class LinkedList{
    //鏈結串列包含「head」與「length」兩屬性
    constructor(){
        this.head = null;
        this.length = 0;
    }

    //從尾新增節點
    push(value){
        let newNode = new Node(value);                //設新增的節點為newNode
        if(this.length === 0){                        //若原鏈結串列長度為0,則直接將newNode設為head
            this.head = newNode;
        } else {                                      //若原鏈結串列長度不為0,則從head走到最後一個節點,再把newNode接上
            let currentNode = this.head;
            while(currentNode.next != null){
                currentNode = currentNode.next;
            }
            currentNode.next = newNode;
        }
        this.length++;                                 //增加新節點後,長度+1
    }

    //從尾移除節點
    pop(){
        if(this.length === 0){                         //若原鏈結串列為空,則不移除任何資料,直接回傳null
            return null;
        } else if (this.length === 1){                 //若原鏈結串列只有一筆資料head,直接將head移除並回傳head資訊(已先放在temp中)
            let temp = this.head;
            this.head = null;
            this.length = 0;
            return temp;
        } else {                                       //若原鏈結串列有多筆資料,則走到第this.length-2個節點,將其指向null後,回傳被移除的第this.length-1個節點資訊(已先放在temp中)
            let currentNode = this.head;
            for(let i = 1; i <= this.length-2; i++){
                currentNode = currentNode.next;
            }
            let temp = currentNode.next;
            currentNode.next = null;
            this.length--;                              //移除節點後,長度-1
            return temp;
        }
    }

    //從頭新增節點
    unshift(value){
        let newNode = new Node(value);                  //設新增的節點為newNode
        if(this.length === 0){                          //若原鏈結串列長度為0,則直接將newNode設為head
            this.head = newNode;
        } else {                                        //若原鏈結串列長度不為0,則將newNode設為head後,將其指向原本的head(已先放在temp中)
            let temp = this.head;
            this.head = newNode;
            this.head.next = temp;
        }
        this.length++;                                  //增加新節點後,長度+1
    }

    //從頭移除節點
    shift(){
        if(this.length === 0){                           //若原鏈結串列為空,則不移除任何資料,直接回傳null
            return null;
        } else if (this.length === 1){                   //若原鏈結串列只有一筆資料head,直接將head移除並回傳head資訊(已先放在temp中)
            let temp = this.head;
            this.head = null;
            this.length = 0;
            return temp;
        } else {                                         //若原鏈結串列有多筆資料,則將head改為原head.next,並回傳原head資訊(已先放在temp中)
            let temp = this.head;
            this.head = this.head.next;
            this.length--;                               //移除節點後,長度-1
            return temp;
        }
    }

    //從中間新增節點
    insert(index, value){                              
        if(index < 0 || index >= this.length){          //若欲新增的位置不在鏈結串列範圍中,直接回傳null
            return null;
        } else if (index === 0){                        //若欲新增的位置剛好在鏈結串列的頭,直接套用unshift()方法
            return this.unshift(value);
        } else if (index === this.length-1) {           //若欲新增的位置剛好在鏈結串列的尾,直接套用push()方法
            return this.push(value);
        } else {                                        //若欲新增的位置在鏈結串列中間,則從頭走到第index-1個節點,將其指向newNode,並讓newNode指向原本第index個節點
            let newNode = new Node(value);              
            let currentNode = this.head;
            for(let i = 0; i < index-1; i++){
                currentNode = currentNode.next;
            }
            newNode.next = currentNode.next;
            currentNode.next = newNode;
            this.length++;                               //增加新節點後,長度+1
            return;
        }
    }

    //從中間移除節點
    remove(index){
        if(index < 0 || index >= this.length){           //若欲移除的位置不在鏈結串列範圍中,直接回傳null
            return null;
        } else if (index === 0) {                        //若欲移除的位置剛好在鏈結串列的頭,直接套用shift()方法
            return this.shift();
        } else if (index === this.length-1){             //若欲移除的位置剛好在鏈結串列的尾,直接套用pop()方法
            return this.pop();
        } else {                                         //若欲移除的位置在鏈結串列中間,則從頭走到第index-1個節點,將其指向第index+1個節點,並回傳原第index個節點資訊(已先放在temp中)
            let currentNode = this.head;
            for(let i = 0; i < index-1; i++){
                currentNode = currentNode.next;
            }
            let temp = currentNode.next;
            currentNode.next = currentNode.next.next;
            this.length--;                               //移除節點後,長度-1
            return temp;
        }
    }

    //取得節點資訊
    get(index){
        if(index < 0 || index >= this.length){           //若欲查詢位置不在鏈結串列範圍中,直接回傳null
            return null;
        } else {                                         //其他情況則從head走到第index項,再顯示第index項的值
            let currentNode = this.head;
            for(let i = 0; i<=index-1; i++){
                currentNode = currentNode.next;
            }
            console.log(currentNode.value);
        }
    }

    //顯示鏈結串列完整資訊
    printAll(){
        if(this.length === 0){                           //若鏈結串列為空,則直接顯示為空
            console.log("nothing in the linked list");
            return;
        } else {                                         //其他情況則從head逐一顯示至最後一個節點
            let currentNode = this.head;
            while(currentNode !== null){
                console.log(currentNode.value);
                currentNode = currentNode.next;
            }
        }
    }
}

陣列:

所有的新增與移除資料方式皆為陣列既有的「方法(method)」,程式碼相對簡潔許多,但不可更改方法名稱;若要顯示完整陣列資訊或特定索引值位置的值,只要使用「console.log()」即可。

//宣告一陣列變數,將其命名為Array
let Array = [1,2,3];

Array.push(4, 5);              //從尾新增兩筆資料(4,5),Array變成[1,2,3,4,5]
Array.pop();                   //從尾移除一筆資料,Array變成[1,2,3,4]
Array.unshift(-2, -1, 0);      //從頭新增三筆資料(-2,-1,0),Array變成[-2,-1,0,1,2,3,4]
Array.shift();                 //從頭移除一筆資料,Array變成[-1,0,1,2,3,4]
Array.splice(1, 1, "Origin");  //從索引值1處移除1筆資料,並在該處新增"Origin"這筆資料,Array變成[-1,"Origin",1,2,3,4]
console.log(Array[4]);         //顯示索引值為4的資料,結果為3
console.log(Array);            //顯示完整Array資訊,結果為[-1,"Origin",1,2,3,4]

比較

「鏈結串列」與「陣列」各有不同的優劣勢,可根據不同操作的「時間複雜度」挑選較適合者。

以下比較中的「鏈結串列」皆屬「單向鏈結串列」。

時間複雜度比較說明

可以分為「從頭」、「從尾」、「從中間」操作,另有「取得資料」,共包含四種處理方式。

從頭(unshift() / shift())

  1. 鏈結串列:直接處理最前面的節點,其他節點不影響,時間複雜度為 O(1)。
  2. 陣列:處理最前面的元素後,其他所有元素都要改變索引值,時間複雜度為 O(n)。

從尾(push()/ pop())

  1. 鏈結串列:從第一個節點走到最後一個節點後才處理,時間複雜度為 O(n)。
  2. 陣列:直接在最尾端處理,時間複雜度為 O(1)。

從中間(insert() / remove() / splice())

  1. 鏈結串列:從第一個節點走到指定的節點處後再處理,時間複雜度為 O(n)。
  2. 陣列:可直接抵達欲處理的位置,但調整後,該位置之後每個元素的索引值都要改變,時間複雜度依然為 O(n)。

取得資料(get())

  1. 鏈結串列:從第一個節點開始走,直到抵達指定位置,時間複雜度為 O(n)。
  2. 陣列:給定索引值後,可以直接抵達指定位置,時間複雜度為 O(1)。

時間複雜度比較表


「鏈結串列」與「陣列」時間複雜度比較表,黃字代表同操作較優者

空間複雜度

  1. 鏈結串列:O(n),需要的儲存空間隨資料筆數變多而呈線性增加。
  2. 陣列:O(1),設定好大小之後,需要的儲存空間即固定,不會因為資料變多而需要更多儲存空間。

優缺點與使用時機比較

鏈結串列(linked list)

優點:

  1. 更動任何資料皆不影響其他筆資料。
  2. 使用記憶體空間的方式較為動態,不用定義儲存空間大小、也不怕存滿。

缺點:

  1. 須使用額外記憶體空間儲存「pointer」。
  2. 讀取資料時,僅能從一端開始依序尋找,時間複雜度較高;若使用雙向鏈結串列,雖可降低時間複雜度,但需要更多記憶體空間儲存另一方向的「pointer」。

使用時機:資料變動頻繁,無法預測要先提供多少記憶體空間。

陣列(array)

優點:

  1. 不須儲存「pointer」, 較節記憶體空間。
  2. 尋找資料時,可透過索引值直接抵達對應元素。

缺點:

  1. 更動非尾端元素時,更動處之後每個元素的索引值都要一併改變。
  2. 須預設連續的記憶體空間大小,有存滿風險,或者要重新設定。

使用時機:資料變動少、需快速查詢資料。


參考資料

  1. Linked List
#資料結構 #鏈結串列 #陣列







你可能感興趣的文章

Kotlin 讀書會

Kotlin 讀書會

從 JavaScript 踏入程式語言

從 JavaScript 踏入程式語言

Checked and Unchecked Exception in Java

Checked and Unchecked Exception in Java






留言討論