用JS實現單向串列

用原生javascript來實現單向串列，實作了新增、查找、插入到特定位置、移除特定位置節點。
程式碼還有很多改進空間，就……放出來跟大家分享。

結構

會寫兩個類別－串列和節點。

先看節點

class Node {
  constructor(data){
    this.data = data;
    this.index = 0;
    this.next = null;
  }
}

節點的結構很單純，data存放資料，index是這個節點所在位置，next則是指向下一個節點。

串列

class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }
}

串列的結構也很單純，head是串列的起點，length為長度。
接下來介紹串列的方法，這些方法會接收節點作為參數，有時也會接收數字做為index

新增(append)

在串列的末尾新增節點。

思路：
新增節點有兩種狀況，一是若串列為空，那這個新增的節點就會是串列的起點；若是串列不為空，那就加在最後面。

append(node){
  this.length += 1;
//若沒有head
  if(!this.head){
    this.head = node;
  } else {
//使用current來遍歷節點，先將current指派為head
    let current = this.head;
	//運用while迴圈，若是current的next屬性有指向別的節點
    while(current.next){
	// 那current就移到節點的next
      current = current.next;
    }
	// current會這樣從起點開始一個一個移動，直到它移到一個next為null的節點，跳出迴圈
	// 這時current會在串列的尾巴
	//新的元素會成為這個尾巴的next
    current.next = node;
  }
  this.redoIndex();
}

redoIndex 是一個重新計算節點index的函式

編號(index)

我其實不太確定這樣有沒有多此一舉，但是替節點編號會讓之後的插入和移除比較方便，所以我寫了一個給節點編index的函式。

思路：
在上一個函式中，有寫到遍歷節點的方式，這邊也運用到類似的技巧。

 redoIndex(){
//current指派為起點
   let current = this.head;
	// 若是current目前有next
   while(current.next){
	// current的next節點的index = current的index +1
     current.next.index  = current.index +1;
		// 移動current
     current = current.next;
   }
 };

當串列的節點發生變化時，就要執行這個函式再度編號，因此名稱為redoIndex（詞窮）。

查找(findIndex)

既然將節點編號，那就要好好運用。findIndex會接收一個數字作為index，回傳該index的節點。

思路：
使用一樣的遍歷手法，從頭到尾檢查節點的index值，直到找到為止。

 findIndex(index){
// 先檢查傳入的index是否合理，若為負數或超過串列長度就扔錯誤
// 節點的編號從0開始
   if(index < 0 || index + 1 > this.length){
     return new Error('not exist!');
   } else {
	// 遍歷
     let current = this.head;
		// 若是current有next，且current的編號小於傳入的index, 就移動current
     while(current.next && current.index < index){
       current = current.next;
     }
		//current若是移動到index = 傳入index的節點，就會跳出迴圈
		//這時的current就是我們要的節點
     return current;
   }
 };

插入到指定位置(insertAt)

insertAt會接收要插入位置的索引值，以及一個節點物件。

思路：
既然已經實做好根據index找尋節點的函式，就好好運用。
插入指定位置有兩種狀況，插入到第0位和非第0位，若是插入到第0位，就要改變head的值，指派給這個新節點，若是非0位，且不超過這個串列，就改變原本這個index所在位置的節點的next指向，以及該index前一位的next指向。

 insertAt(index, node){
// 檢查index是否可行
	if(index < 0 || index + 1 > this.length){
		return new Error('not exist!');
   };
	// 若要插入到第0位，就將它替換掉原本的head
   if(index === 0){
     node.next = this.head;
     this.head = node;
     this.length += 1;
   }
   else {
	// 若index是合理的數字且不為0，就進行替換
     this.length += 1;
		//先找到該index目前是哪個節點
     let current = this.findIndex(index);
		// 再找到該index上一個節點是誰
     let prev = this.findIndex(index-1);
     console.log(`替換第${index}位`, current);
		//替換: 因為原本位置的節點要往後移, 它會變成傳入node的next
     node.next = current;
		// 該index上一位節點的next則會是傳入的node
     prev.next = node;
   }
   this.redoIndex();
 };

移除特定位置(removeAt)

removeAt會接受一個數字做為參數，代表要移除的位置。

思路：
其實跟插入滿像的，都是改變next這個指標。不過移除會有三種狀況，第一個是移除第0位，也就是起點，那就要重新指派起點；第二個是移除this.length -1位，也就是移除尾巴，那麼尾巴前一位的節點next就應該變成是null，最後就是移除頭尾之間位置的節點，要改變該index及之前節點。

removeAt(index){
// 檢查
  if(index <0 || index + 1 > this.length){
    return new Error('not exist!');
  }
// 若要移除原本的頭
  if(index === 0){
    console.log('去首');
	// 頭會被原本的第二位節點取代
    this.head = this.head.next;
    this.head.index = 0;
	//若是移除尾
  } else if ( index === this.length -1) {
    console.log('去掉尾巴');
	//找到尾巴前一位節點, 重設next
    let prev = this.findIndex(index-1);
    prev.next = null;
  } else {
//若是頭尾之間的數
    console.log('去掉第' + index + '位');
	//找到該index目前的節點
    let current = this.findIndex(index);
	//以及該index的上一位
    let prev = this.findIndex(index -1);
	//由於該index的節點會被刪除, 上一位的next要指向該index的next
    prev.next = current.next;
    
  };
  this.length -= 1;
  this.redoIndex();
}

後記

這周都在忙著找工作和面試的事情，除了體力上累心也好累，這系列可能會變weekly algo吧。

參考

用 JavaScript 學習資料結構和演算法：鏈結串列（Linked List）篇 - by kdchang

# 演算法