>[success] # 實現一個鏈表 ~~~ 1.首先鏈表不是一個連續的內存空間，針對這條我們采取'對象形式'，即有多少個鏈表 項則對應生成多少個'對象' 2.每個元素由'一個存儲元素本身的節點'和'一個指向下一個元素的引用'（也稱指針或鏈接）組成,因此針對 '第一條每個對象來說，需要存儲兩個東西，一個是本身該結點要存的值，與其相鄰的下一個結點對象' 3.如果當前鏈表為空，它的頭部和尾部都為'undefind',有值它的尾部應該為'undefind'，要注意的是鏈表是 通過'頭結點依次向下找到我們需要的元素'，因此頭結點的存儲很重要 ~~~ * 鏈表效果圖  * 針對第二條解釋的效果圖  >[info] ## 實現一個鏈表 ~~~ 1.我們的鏈表要具備的方法： push(element)：向鏈表尾部添加一個新元素。 insert(element, position)：向鏈表的特定位置插入一個新元素。 getElementAt(index)：返回鏈表中特定位置的元素。如果鏈表中不存在這樣的元素，則返回 undefined。 remove(element)：從鏈表中移除一個元素。 indexOf(element)：返回元素在鏈表中的索引。如果鏈表中沒有該元素則返回-1。 removeAt(position)：從鏈表的特定位置移除一個元素。 isEmpty()：如果鏈表中不包含任何元素，返回 true，如果鏈表長度大于 0則返回 false。 size()：返回鏈表包含的元素個數，與數組的 length 屬性類似。 toString()：返回表示整個鏈表的字符串。由于列表項使用了 Node 類，就需要重寫繼 承自 JavaScript 對象默認的 toString 方法，讓其只輸出元素的值。 ~~~ >[danger] ##### 代碼實現 ~~~ 1.在上面的分析時候，說過鏈表是非連續的空間，我們需要給'每個節點創建對象',并且這個節點存儲的兩個東西 '當前節點的值'，'當前節點對應的下一個節點內存指向'，因此根據這兩點創建一個類 // 保存Node 節點 指針 class Node { constructor(element){ this.element = element this.next = undefined } } 比較元素的公共方法 function defaultEquals(a, b) { return a === b; } ~~~ ~~~ class LinkedList{ // 在使用鏈表初始化的時候，需要參數 // count 記錄當前鏈表有多少元素 // head 當前鏈表頭結點 有頭結點才能依次往下找 constructor(equalsFn = defaultEquals){ this.equalsFn = equalsFn this.count = 0 // 鏈表中的元素數量 this.head = undefined // 保存引用 } // 添加元素 /* 要注意有兩點考 1.如果當前頭部為undefined說明鏈表此時無數據，要插入的元素則直接為頭結點并且要記錄 2.如果頭結點有數據要依次循環找到要插入結點的位置 */ push(element){ // 創建每一個結點儲存對象 const node = new Node(element) let current if(this.head == null){ this.head = node }else{ current = this.head while(current.next!=null){ current = current.next } current.next = node } this.count ++ // 增加鏈表數據個數 } // 目標索引位置獲取當前元素 /* 有兩種情況 1.當前索引為無效索引返回undefined 2.當前索引為有效索引 返回當前結點 */ getElementAt(index){ if(index<=this.count && index>= 0){ let node = this.head for(let i=0;i<index;i++){ node = node.next } return node } return undefined } // 刪除指定元素通過坐標 /* 1.首先判斷刪除的元素是否存在 2.如果刪除的是首位應該重新給head 規定新的賦值 3.如果是其他位置需要將刪除項前后結點重新連接 */ removeAt(index){ // 判斷是否越界 if(index<this.count && index>=0){ // 判斷是否是頭部元素 let current = this.head if(index === 0){ this.head = current.next }else{ // 獲取刪除項的前一位 const previous = this.getElementAt(index-1) current = previous.next // 讓相鄰的相互連接 previous.next = current.next } this.count -- return current.element } return undefined } // 插入和刪除 邏輯思維方式類似的 insert(element, index) { if (index >= 0 && index <= this.count) { const node = new Node(element); if (index === 0) { const current = this.head; node.next = current; this.head = node; } else { const previous = this.getElementAt(index - 1); node.next = previous.next; previous.next = node; } this.count++; return true; } return false; } // 查詢鏈表中元素的位置 indexOf(element) { let current = this.head; for (let i = 0; i < this.size() && current != null; i++) { if (this.equalsFn(element, current.element)) { return i; } current = current.next; } return -1; } // 刪除鏈表中刪除的元素 remove(element) { const index = this.indexOf(element); return this.removeAt(index); } isEmpty() { return this.size() === 0; } size() { return this.count; } getHead() { return this.head; } clear() { this.head = undefined; this.count = 0; } toString() { if (this.head == null) { return ''; } let objString = `${this.head.element}`; let current = this.head.next; for (let i = 1; i < this.size() && current != null; i++) { objString = `${objString},${current.element}`; current = current.next; } return objString; } } ~~~