iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 16
3

今天要介紹一個對我而言非常陌生的資料結構 Linked List。它不像 Array 在 javaScript 有內建的方法,所以弄懂它真的花了非常多功夫。若有理解錯誤地方要麻煩高手幫我指證了
https://ithelp.ithome.com.tw/upload/images/20190917/20106426Hn1aFsMtHx.jpg

Linked List?

不必以連續空間來儲存串列中的元素。由多個節點 (node) 所組成,而每個 node 至少包含資料 (ele) 欄及連結欄位 (next),透過某個 node 的連結欄位可以取得下一個 node

想知道更精確解釋可以看維基百科

Linked List 是一個方便動態增加與刪除的 data structure,也不像 Array 資料是連續的。每個元素(Linked List 裡叫節點 Node ) 都只存在自己的值、跟指向下一個的指標

class LinkedListNode{
	constructor(ele){
		this.next = null; // 指向下一個
		this.ele = ele // 自己
	}
}

https://ithelp.ithome.com.tw/upload/images/20190917/20106426tdvWFPFzGt.jpg
生活中的例子就是火車,Node 就像是火車的車廂。
Linked List 常常拿來跟 Array 做比較。我整理了一個表格如下
https://ithelp.ithome.com.tw/upload/images/20190917/20106426OCWlmYYlyP.png
看到這裡應該稍微對 Linked List 有基本認識了,接下來就來介紹它的特性方法


建立 Linked List

javaScript 並沒有內建 linked list,所以我們只好用物件來來模擬。
首先會建立兩個東西,一個是 Node(火車的個別車廂),一個是 List(火車)

Node 的屬性有

  • ele (資料)
  • next (指向下一個 node)

List 的屬性有

  • head: 最前面的 node 是誰
  • length: 總共有幾個
class LinkedListNode{
	constructor(ele){
		this.next = null;
		this.ele = ele
	}
}
class LinkedList {
	constructor(){
		this.head = null
		this.length = 0
	}
  // method here
  // ....
}

Linked List 方法

下列就是我們要建立的方法

append(ele):  從尾部增加一個 node
insert(position, ele): 從特定位置增加一個 node
removeAt(position): 刪除特定位置的 node
remove (ele): 移除某個 node
indexOf(ele):  回傳此 node 是否存在,不存在回傳 -1
toString(): 把 List 物件內容轉換成字串
size(): 回傳總共有幾個 node 在 list 內

append(ele)

從尾部增加元素 (node),尾部新增元素會有兩種可能

  • List 裡完全沒 node 所以會被增加到第一個, head 也會指到 newNode (head = newNode)
  • List 裡已經有其他 node,所以先 while loop 找到最後一個再 current.next = newNode ,怎麼知道哪一個是最後一個? node.next = null 就是最後一個

https://ithelp.ithome.com.tw/upload/images/20190917/20106426CHYko5T1kD.jpg

append(ele){
	let newNode = new LinkedListNode(ele);

	// 判斷 nodelist 是不是空的
	if(this.head == null){
		// 1. 是空的
		this.head = newNode
	}else{
		// 2. 不是空的
		// loop nodelist 到最後一個然後加進去 
        // 最後一個就是 current.next == null
		let current = this.head;
		while(current.next != null){
			current = current.next
		}
        current.next = newNode 
	}
	this.length ++;
}

insert(position, ele)

在特定位置(position) 插入 node,也是有兩種可能

  • 插入最前面。也就是當 position = 0 時
  • 其他。while loop 找到 position 位置,把本來的 node (current) 替換成要插入的 node(newNode) ,然後 newNode.next 指向本來的 node(current)

https://ithelp.ithome.com.tw/upload/images/20190917/201064269Ai3iHOHB2.jpg

insert (position, ele){
	// 判斷極限值
	if(position > -1 && position <= this.length){
	  let newNode = new LinkedListNode(ele)
	  let current = this.head;
      
	  // 1.1 判斷是否為 head
	  if(position == 0){
		newNode.next = current;
	    this.head = newNode;
		}else{
			// 1.2 loop current = previous  找到 position = index
            let previous;
            let index = 0;
            while(index != position){
                index ++;
                previous = current;
                current = current.next;
            }
	    newNode.next = current;
	    previous.next = newNode;
	  }
	  this.length ++;
	  return true;
	}else{
        return false;
	}
}

removeAt (position)

刪除特定位置 position 的 node,有下列兩種情況

  • 是 List 的 head 被移除,那就把本來的 head.next = head
  • 其他,把前一個 previous.next = current.next

https://ithelp.ithome.com.tw/upload/images/20190917/20106426TCP8ldL0N5.jpg

removeAt (position){
	// 判斷極限值
	if(position > -1 && position < nodelist.length){
	// 1. 繼續下去
	// 判斷是第一個(head)被刪掉還是其他
	let current = this.head
	if(position == 0){
        // 1.1
	    this.head = head.next
	}else{
		// 1.2
	    let index = 0;
	    let previous;
        
	    // loop 到 position 然後
	    while(position != index){
            index ++;
            previous = current;
            current = current.next;
		}
		previos.next = current.next
	}
	this.length --;
	return current.ele;
    
	}else{
        // 2. sorry 不能執行這個方法喔 
        return false
	}
}

remove (ele)

移除某個 node

remove (ele){
	// 結合這上面寫好的方法
	let index = this.indexOf(ele)
	return this.removeAt(index)
}

indexOf (ele)

回傳 ele 是否為空 空得回傳 -1

indexOf (ele){
	// 慢慢找,找到回傳 index
	let index = -1;
	let current = this.head
	while(current){
        index ++;
        if(current.ele == ele){
            return index;
        }
        current = current.next
	}
	return -1;
}

toString()

toString 會透過 while 迴圈把 LinkedList 物件內容轉換成字串

toString(){
	let current = this.head
	let string = ''
	while(current){
        string += current.ele
		current = current.next
	}
	return string
}

size()

回傳長度

size(){
	return this.length;
}

Double linked list

node 多了一個 prev,而 list 也多一個 tail。可以避免一般 Linked List 只能從前面循序存。
https://ithelp.ithome.com.tw/upload/images/20190917/201064265M8URqs94k.jpg

class LinkedListNode{
	constructor(ele){
		this.next = null;
		this.prev = null;
		this.ele = ele
	}
}
class LinkedList {
	constructor(){
		this.head = null
		this.tail = null
		this.length = 0
	}
	methodHere(){}
}

Double linked list 方法就不再文章一一列出來了。大家有興趣也可以參考 DS with JS — Linked Lists — II

坦白說我不知道前端哪邊會用到 Linked List XD (假如知道的人可以跟我說)。但特性比起 Array 的確大大減少浪費記憶體的狀況。模擬 Linked List 時也順便訓練自己的思考模式,因為它幾乎每種方法都有兩個以上可能,不像前幾天的資料結構這麼單純。

下一篇會來看有關 Linked List 的 LeetCode 啦

如有錯誤或需要改進的地方,拜託跟我說。
我會以最快速度修改,感謝您

上一篇
佇列 Queue
下一篇
[LeetCode #206] Linked List
系列文
前端工程師用 javaScript 學演算法32
0
afjini
iT邦新手 5 級 ‧ 2019-09-17 11:13:09

我也想知道哪裡用得到 Linked List!

hannahpun iT邦新手 5 級 ‧ 2019-09-17 13:10:20 檢舉

畢竟 javaScript 就是 Array 到底啊/images/emoticon/emoticon10.gif

0
pjchender
iT邦新手 5 級 ‧ 2020-05-12 10:41:04

好棒的圖示,謝謝!

我要留言

立即登入留言