Open in app

Sign in

Write

Sign in

[資料結構] 學習筆記 — 1. Singly Linked List 單向資料鏈結

Amber Fragments
20 min readDec 11, 2022

--

定義

  • 一種帶有 head、tail、length 特性的資料結構
  • Linked list 由節點（node）組成，而每一個節點有自身的值（value）和指標（pointer），指標可以指向另一個節點或者 null
  • Linked list 沒有 index
source: JavaScript Algorithms and Data Structures Masterclass

因為沒有 index，所以當我們想要拿到中間某筆資料的時候，我們必須從第一個開始往下找。

Linked list 有點像電梯，我們要從一樓到四樓必須從一樓、二樓、三樓一層層走，最後才能抵達第四層樓。

Linked list vs. Array

linked list 跟 array 相當相似，所以我們可以看下它們之間的差異：

Linked list

  • 沒有 index
  • 透過 next 與下一個節點連結
  • 不允許從中間任意取出資料

Array

  • 有 index
  • insertion 和 deletion 可能是昂貴的：昂貴表示需要比較高的時間複雜度，所以如果我們的資料需要頻繁的 insertion 和 deletion，我們會考慮使用 singly linked list
  • 允許從中間任意取值

創建

這邊創建兩個 class，一個是 Node 節點，一個是 SinglyLinkedList。SinglyLinkedList 可以由數個 Node 節點連結而成。

每一個 Node 的 property 有兩個，它本身的值（value），和它指向的下一個 Node。

SinglyLinkedList 的 property 則包括起點（head）、終點（tail）和長度（length）。

// piece of data -- val
// reference to next node -- next

class Node {
    constructor(val) {
        this.val = val
        this.next = null
    }
}

class SinglyLinkedList {
    constructor() {
        this.length = 0
        this.head = null
        this.tail = null
    }
}

Push：從 linked list 的最後新增一個節點

  • push function 會有一個 argument 為要新增節點的 value
  • 建立一個節點，並指定它的 value 為 input argument
  • 指定它是 tail.next 以及新 tail
  • list 的長度加一

Edge case

  • 如果原本的 linked list 是空的，新增一個節點同時指定它是 linked list 的 head 跟 tail。

class SinglyLinkedList {
    constructor() {
        // ...
    }

    push(val) {
        var newNode = new Node(val)
        if(!this.head) {
            this.head = newNode
            this.tail = this.head
        } else {
            this.tail.next = newNode
            this.tail = newNode
        }
        this.length++
        return this
    }
}

Pop：移除 linked list 最後一個節點

  • 先寫出 traverse method（遍歷 linked list）
  • 透過遍歷找到最後一個節點以及倒數第二個節點
  • 指定 linked list 的 tail 是倒數第二個節點，並且 tail 的 next 為空（null）
  • linked list 的長度減一

Edge case

  • 如果 list 本來就沒有節點，回傳 undefined
  • 如果移除最後一個節點後，list 為空（原本只有一個節點），將 list 的 head 跟 tail 都指定為 null
class SinglyLinkedList {
    constructor() {
        // ...
    }

    push(val) {
        // ...
    }

    traverse() {
        var current = this.head
        while(current) {
            current = current.next
        }
    }

    pop() {
        if(!this.head) return undefined
        var current = this.head
        var newTail = current

        while(current.next) {
            newTail = current
            current = current.next
        }
        this.tail = newTail
        this.tail.next = null
        this.length--

        if(this.length === 0) {
            this.head = null
            this.tail = null
        }
        return current
    }
}

Shift：移除 head

  • 先記錄原有的 head
  • 指定 head 是「原本 head 的 next Node」
  • list 的長度減一

Edge case

  • 如果 list 本來就沒有節點，回傳 undefined
  • 如果移除最後一個節點後，list 為空，將 list 的 tail 都指定為 null
    註：這邊跟上面的 pop 不一樣，不需要指定 head 為 null 的原因是因為在「指定 head 是原本 head 的 next」的時候，如果原本只有一個 Node，它的 next 就是 null 了。
class SinglyLinkedList {
    constructor() {
        // ...
    }

    push(val) {
        // ...
    }

    traverse() {
        // ...
    }

    pop() {
        // ...
    }

    shift() {
        if(!this.head) return undefined
        var currentHead = this.head
        this.head = currentHead.next
        this.length--
        if(this.length === 0) {
            this.tail = null
        }
        return  currentHead
    }
}

Unshift：從 linked list 的起始新增一個節點

比起 pop，singly linked list 的 unshift 步驟蠻單純的！

  • unshift function 會有一個 argument 為要新增節點的 value
  • 建立一個節點 newNode，並指定它的 value 為 input argument
  • 指定 newNode 的 next 是 head（singly linked list 原本的 head）
  • 指定 list head 是 newNode（指定新的 head）
  • list 長度加一

Edge case

  • 如果 list 本來為空，指定 head 跟 tail 是 newNode。
class SinglyLinkedList {
    constructor() {
        // ...
    }

    push(val) {
        // ...
    }

    traverse() {
        // ...
        }
    }

    pop() {
        // ...
    }

    shift() {
        // ...
    }

    unshift(val) {
        var newNode = new Node(val)
        if (!this.head) {
            this.head = newNode
            this.tail = this.head
        } else {
          newNode.next = this.head
          this.head = newNode
        }
        this.length++
        return this
    }
}

Get：取得某個位置的資料

因為 Linked List 沒有 index，所以我們必須使用 traverse 來取得指定位置的 Node。

  • get function 會有一個 index argument
  • 遍歷 index 的次數來找到指定位置的 node 並且回傳該 node 的 value

Edge case

  • 如果 index 小於零或大於 list 的長度，回傳 null
class SinglyLinkedList {
    constructor() {
        // ...
    }

    push(val) {
        // ...
    }

    traverse() {
        // ...
        }
    }

    pop() {
        // ...
    }

    shift() {
        // ...
    }

    unshift(val) {
        // ...
    }

    get(index) {
        if(index < 0 || index >= this.length) return null
        var counter = 0
        var current = this.haad
        while (counter !== index) {
            current = current.next
            current++
        }
        return current
    }
}

Set：改變 list 中特定 index 節點的值為新值

  • set function 會有兩個 arguments，一個是指定的 index，一個是要更新的 value
  • 因為前面我們已經寫好了 get method，所以我們可以使用 get 取得指定的 index node，然後重新給與它的 value 為 input value

Edge case

  • 如果使用 get 沒有找到指定 index 的 node，回傳 null
class SinglyLinkedList {
    constructor() {
        // ...
    }

    push(val) {
        // ...
    }

    traverse() {
        // ...
        }
    }

    pop() {
        // ...
    }

    shift() {
        // ...
    }

    unshift(val) {
        // ...
    }

    get(index) {
        // ...
    }

    set(index, val) {
        var foundNode = this.get(index)
        if(foundNode) {
            foundNode.val = val
            return true
        }
        return false
    }
}

Insert：在 list 中特定位置插入指定值

  • insert function 會有兩個 arguments，一個是指定的 index，一個是要建立的新 node 的 value
  • 建立一個新 newNode，並且給與 input value
  • 使用前面寫好的 get method，取得「index - 1」的 node，這邊先取名為 preNode
  • 將 preNode 的 next 存在 temp 變數裡（原來的 next）
  • 將 preNode 的 next 指向 newNode（重新建立 preNode 跟 newNode 的連結）
  • 將 newNode 的 next 指向 temp（建立 newNode 跟它下一個的連結）
  • list 的長度加一
  • 回傳 true

Edge case

  • 如果 index 小於零或大於 list 的長度，回傳 false
  • 如果 index 就是 list 的長度，那我們可以直接使用 push，回傳 true
  • 如果 index 是 0，可以直接使用 unshift，回傳 true
class SinglyLinkedList {
    constructor() {
        // ...
    }

    push(val) {
        // ...
    }

    traverse() {
        // ...
        }
    }

    pop() {
        // ...
    }

    shift() {
        // ...
    }

    unshift(val) {
        // ...
    }

    get(index) {
        // ...
    }

    set(index, val) {
        // ...
    }

    insert(index, val) {
        if (index < 0 || index > this.length) return false
        if (index === this.length) return !!this.push(val)
        if (index === 0) return !!this.unshift(val)

        var newNode = new Node(val)
        var prev = this.get(index - 1)
        var temp = prev.next
        prev.next = newNode
        newNode.next = temp
        this.length++
        return true
    }
}

Remove：移除特定位置的節點

  • remove function 會有一個指定的 index arguments
  • 使用前面寫好的 get method，取得「index - 1」的 node，這邊先取名為 preNode
  • 指定 preNode 的 next 為「preNode.next.next」
  • list 的長度減一
  • 回傳移除的 node 的值

Edge case

  • 如果 index 小於零或大於 list 的長度，回傳 undefined
  • 如果 index 等於 list length - 1，使用 pop
  • 如果 index 等於 0，使用 shift
class SinglyLinkedList {
    constructor() {
        // ...
    }

    push(val) {
        // ...
    }

    traverse() {
        // ...
        }
    }

    pop() {
        // ...
    }

    shift() {
        // ...
    }

    unshift(val) {
        // ...
    }

    get(index) {
        // ...
    }

    set(index, val) {
        // ...
    }

    insert(index, val) {
        // ...
    }

    remove(index) {
        if(index < 0 || index >= this.length) return undefined
        if(index === 0) return this.shift()
        if(index === this.length - 1) return this.pop()

        var prevNode = this.get(index - 1)
        var removed = prevNode.next
        prevNode.next = removed.next
        this.length--
        return removed
    }
}

Reverse：反轉 linked list

  • swap head 跟 tail
  • 創建兩個變數 next 跟 prev
  • 建立一個 node 變數並且先給予它 head 的值
  • 寫一個遍歷 list 的迴圈，在迴圈裡面重複做：
    ◼︎ 將 node.next 先存進 next 變數裡（next = node.next）
    ◼︎ 將 node.next 指向 prev（node.next = prev）
    ◼︎ 讓 prev 成為 node（prev = node）
    ◼︎ 讓 node 成為 next（node = next）
恩，如果讀到這段覺得 loop 內容很模糊，沒問題的，Colt 也是這麼覺得😅
概念就是先記錄 node.next（避免 loop 迷路），然後就重複將 node next 指向 prev
然後重新設定 prev 跟 node

大概是醬～

Edge case

  • 如果 index 小於零或大於 list 的長度，回傳 undefined
class SinglyLinkedList {
    constructor() {
        // ...
    }

    push(val) {
        // ...
    }

    traverse() {
        // ...
        }
    }

    pop() {
        // ...
    }

    shift() {
        // ...
    }

    unshift(val) {
        // ...
    }

    get(index) {
        // ...
    }

    set(index, val) {
        // ...
    }

    insert(index, val) {
        // ...
    }

    remove(index) {
        // ...
    }

    reverse() {
        var node = this.head
        this.head = this.tail
        this.tail = node

        var next
        var prev = null
        for(let i = 0; i < this.length; i++) {
            next = node.next
            node.next = prev
            prev = node
            node = next
        }
        return this
    }

    // Colt 多加的，方便教學XD
    print() {
        var arr = []
        var current = this.head
        while (current) {
            arr.push(current.val)
            current = current.next
        }
        console.log(arr)
    }   
}

Big O of Singly Linked List

  • Insertion：O(1)
  • Removal：It depends… O(1) or O(n)
  • Searching：O(n)
  • Access：O(n)

這裡面最讓我困惑的是 Insertion 的 Big O 是 O(1) ？？？？？因為依照剛才上課的內容，我們需要先遍歷找到某個 index 的 node，才去新增節點，這樣想的話應該是 O(n) 才對吧！？

不過查了一下 cheet sheet 也是這麼寫的，窩豪困惑😫？？？

source: Know Thy Complexities

然後就找到了 Stack Overflow 的這篇 QA：

Q: Why singly linked list has a insertion and deletion time complexity of O(1) ?

A: The explanation for this is, that the big O notation in the linked table refers to the function implementation itself, not including the list traversal to find the previous reference node in the list.

If you follow the link to the wikipedia article of the Singly-LinkedList implementation it becomes more clear:

function insertAfter(Node node, Node newNode)
function removeAfter(Node node)

The above function signatures already take the predecessor node as argument (same for the other variants implicitly).

Finding the predecessor is a different operation and may be O(n) or other time complexity.

意思是「Singly linked list 的 big O 不考慮遍歷的 function 部分，只考慮 insert 的動作」。

OK，非常不貼近直覺 🫠，世界上最遠的距離是數學與我的距離。

完整 Singly Linked List Code

// piece of data -- val
// reference to next node -- next

class Node {
    constructor(val) {
        this.val = val
        this.next = null
    }
}

class SinglyLinkedList {
    constructor() {
        this.length = 0
        this.head = null
        this.tail = null
    }

    push(val) {
        var newNode = new Node(val)
        if(!this.head) {
            this.head = newNode
            this.tail = this.head
        } else {
            this.tail.next = newNode
            this.tail = newNode
        }
        this.length++
        return this
    }

    traverse() {
        var current = this.head
        while(current) {
            console.log(current.val)
            current = current.next
        }
    }

    pop() {
        if(!this.head) return undefined
        var current = this.head
        var newTail = current

        while(current.next) {
            newTail = current
            current = current.next
        }
        this.tail = newTail
        this.tail.next = null
        this.length--

        if(this.length === 0) {
            this.head = null
            this.tail = null
        }
        return current
    }

    shift() {
        if(!this.head) return undefined
        var currentHead = this.head
        this.head = currentHead.next
        this.length--
        if(this.length === 0) {
            this.tail = null
        }
        return  currentHead
    }

    unshift(val) {
        var newNode = new Node(val)
        if (!this.head) {
            this.head = newNode
            this.tail = this.head
        } else {
          newNode.next = this.head
          this.head = newNode
        }
        this.length++
        return this
    }

    get(index) {
        if(index < 0 || index >= this.length) return null
        var counter = 0
        var current = this.haad
        while (counter !== index) {
            current = current.next
            current++
        }
        return current
    }

    push(val) {
        var newNode = new Node(val)
        if(!this.head) {
            this.head = newNode
            this.tail = this.head
        } else {
            this.tail.next = newNode
            this.tail = newNode
        }
        this.length++
        return this
    }

    set(index, val) {
        var foundNode = this.get(index)
        if(foundNode) {
            foundNode.val = val
            return true
        }
        return false
    }

    insert(index, val) {
        if (index < 0 || index > this.length) return false
        if (index === this.length) return !!this.push(val)
        if (index === 0) return !!this.unshift(val)

        var newNode = new Node(val)
        var prev = this.get(index - 1)
        var temp = prev.next
        prev.next = newNode
        newNode.next = temp
        this.length++
        return true
    }

    remove(index) {
        if(index < 0 || index >= this.length) return undefined
        if(index === 0) return this.shift()
        if(index === this.length - 1) return this.pop()

        var prevNode = this.get(index - 1)
        var removed = prevNode.next
        prevNode.next = removed.next
        this.length--
        return removed
    }
}

Singly Linked List 的 code 超長的！但還是蠻有趣～下一個資料結構是它的雙胞胎 Doubly Linked List～

上一篇：[資料結構] 學習筆記 — 0. JavaScript Class

下一篇：[資料結構] 學習筆記 — 2. Doubly Linked List 雙向資料鏈結

Data Structures
Singly Linked List
JavaScript
資料結構

--

--

Amber Fragments

Written by Amber Fragments

129 Followers

願你的每段回憶都是琥珀色的甜美瞬間

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams