iT邦幫忙

2021 iThome 鐵人賽

DAY 9
0
自我挑戰組

每日攝取一點資料結構和演算法系列 第 9

Day9:[資料結構] Linked-List - 鏈結串列

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20210909/20128604ziq12lICcx.jpg

Linked List為抽象的資料結構,概念有點像三國的連環船,一艘船(節點)連結著下一艘船(節點),每個節點除了擁有自己的值之外也記錄自己的下一個節點是指向哪個節點,而Linked List又分為下列幾種

Simple Linked List

單向的Linked List,最後一個節點next指向null
https://ithelp.ithome.com.tw/upload/images/20210909/20128604Io9pLY5cUf.png

Circular Linked List

最後一個節點的next指向第一個,形成一個循環
https://ithelp.ithome.com.tw/upload/images/20210909/201286043mXZOgwrxN.png

Doubly Linked List

雙向的Linked List,可以看到節點除了紀錄next指向誰,也會記錄是誰指向自己
https://ithelp.ithome.com.tw/upload/images/20210909/20128604gojzKyDGz5.png

Linked List v.s Array

https://ithelp.ithome.com.tw/upload/images/20210909/20128604dLWmLjmzkW.png
Linked List為不連續的記憶體空間,因此在存放每個元素的同時 ,也會記錄下一個元素存放的位置,但假設今天想要取得鏈結串列的最後一個元素時 ,就必須從第一個元素開始讀取, 逐一讀到最後一個,讀取效率較為不理想,但是做插入和刪除資料的時候非常快,時間複雜度只有O(1)。

Array為連續的記憶體空間,所以可以直接用索引(index)來取得需要的值 ,讀取相當的快,不過假如要刪除一個元素或新增一個元素都會影響到其他元素的排序,統一往後或是往前挪,因此時間複雜度為O(n),n為陣列長度。

下圖是操作兩者所需的時間複雜度比較
https://ithelp.ithome.com.tw/upload/images/20210909/20128604OmfTsJqb6v.png

那甚麼時候該用Linked List呢?

不需要快速的查詢資料以及有頻繁新增刪除資料的需求

用js實作Linked List

創建一個linked list,初始節點的值為apple並且將next指向banana

class ListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedList {
    constructor(value) {
        //初始的節點命名為head
        this.head = new ListNode(value);
    }
    add(value) {
        const newNode = new ListNode(value);
        //head的next指向新的節點
        this.head.next = newNode;
        console.log("head", this.head);
    }
}

let linkedList = new LinkedList("apple");
linkedList.add("banana");

成功做出一個Linked List!
https://ithelp.ithome.com.tw/upload/images/20210909/201286041hoWjPlrxd.png


上一篇
Day8: [資料結構]Hash Table - 雜湊表
下一篇
Day10: [資料結構] Graph - 圖
系列文
每日攝取一點資料結構和演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言