今天要介紹一個對我而言非常陌生的資料結構 Linked List。它不像 Array 在 javaScript 有內建的方法，所以弄懂它真的花了非常多功夫。若有理解錯誤地方要麻煩高手幫我指證了

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 // 自己
	}
}

生活中的例子就是火車，Node 就像是火車的車廂。
Linked List 常常拿來跟 Array 做比較。我整理了一個表格如下

看到這裡應該稍微對 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 就是最後一個

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)

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

removeAt (position){
	// 判斷極限值
	if(position > -1 && position < nodelist.length){
	// 1. 繼續下去
	// 判斷是第一個(head)被刪掉還是其他
	let current = this.head
	if(position == 0){
        // 1.1
	    this.head = current.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 只能從前面循序存。

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 啦

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

歡迎追蹤我的部落格，除了技術文也會分享一些在矽谷工作的甘苦。