摘要：前言本章為重讀學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的系列文章，該章節(jié)主要講述數(shù)據(jù)結(jié)構(gòu)鏈表，以及實(shí)現(xiàn)鏈表的過(guò)程和原理。鏈表，是存儲(chǔ)有序的元素集合。鏈表中的元素在內(nèi)存中并不是連續(xù)放置的，每個(gè)元素由一個(gè)存儲(chǔ)自身的元素節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用指針或鏈接組成。

傷情最是晚涼天，憔悴廝人不堪言；
邀酒摧腸三杯醉.尋香驚夢(mèng)五更寒。
釵頭鳳斜卿有淚，荼蘼花了我無(wú)緣；
小樓寂寞新雨月.也難如鉤也難圓。

本章為重讀《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》的系列文章，該章節(jié)主要講述數(shù)據(jù)結(jié)構(gòu)-鏈表，以及實(shí)現(xiàn)鏈表的過(guò)程和原理。

鏈表，為什么要有這種數(shù)據(jù)結(jié)構(gòu)呢？當(dāng)然，事出必有因！

數(shù)組-最常用、最方便的數(shù)據(jù)結(jié)構(gòu)，But，當(dāng)我們從數(shù)組的起點(diǎn)或中間插入或移動(dòng)項(xiàng)的成本很高，因?yàn)槲覀冃枰苿?dòng)數(shù)組元素。

鏈表，是存儲(chǔ)有序的元素集合。鏈表中的元素在內(nèi)存中并不是連續(xù)放置的，每個(gè)元素由一個(gè)存儲(chǔ)自身的元素節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用(指針或鏈接)組成。

這個(gè)是重點(diǎn)，注意，圈起來(lái)，面試肯定考！

我們要實(shí)現(xiàn)鏈表的結(jié)構(gòu)以及對(duì)應(yīng)的方法，大致為：元素插入、移除、獲取鏈表長(zhǎng)度、查詢?cè)?、是否為空等?..更詳細(xì)可看代碼實(shí)現(xiàn)邏輯。

數(shù)據(jù)結(jié)構(gòu)越來(lái)越復(fù)雜嘍...注意領(lǐng)會(huì)精神...

/**
 * Node 節(jié)點(diǎn)類，用于生成自身節(jié)點(diǎn)與下一個(gè)元素的引用
 */
class Node {
  constructor(element) {
    this.element = element
    this.next = undefined
  }
}

/**
 * defaultEquals() 用于比較兩個(gè)非對(duì)象類的值是否相等
 */
function defaultEquals (a, b) {
  return a === b
}

/**
 * LinkedList 鏈表
 * 特點(diǎn)：鏈表存儲(chǔ)有序的元素集合，但元素在內(nèi)存中并不連續(xù)存放。每個(gè)元素有一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用
 */
class LinkedList {
  constructor (equalsFn = defaultEquals) {
    // 鏈表長(zhǎng)度
    this.count = 0
    // 第一個(gè)元素引用
    this.head = undefined
    // 用于比較元素是否相等，默認(rèn)為defaultEquals，允許傳入自定義的函數(shù)來(lái)比較兩個(gè)對(duì)象是否相等。
    this.equalsFn = equalsFn
  }
}

注意：equalsFn參數(shù)，在比較對(duì)象類元素時(shí)，需要傳遞自定義方法來(lái)比較兩個(gè)對(duì)象的的值是否相等。

push()

向鏈表的尾部添加元素

/**
 * push() 添加元素到鏈表
 * @param {*} element 待添加的元素
 */
push (element) {
  let node = new Node(element)
  let current
  // 判斷鏈表是否為空
  if (this.head == null) {
    this.head = node
  } else {
    // 查詢最后的元素 - 特點(diǎn) current.next == null
    current = this.head
    while (current.next != null) {
      current = current.next
    }
    // 將最后元素的下一個(gè)元素引用指向node
    current.next = node
  }
  this.count++
} 

getElementAt()

獲取指定索引位置的元素

/**
 * getElementAt() 返回索引位置元素
 * @param {Number} index 索引位置
 * @returns {*} node
 */
getElementAt (index) {
  // 判斷索引是否有效
  if (index < 0 || index > this.count) {
    return undefined
  }
  let node = this.head
  for (let i = 0; i < index && node != null; i++) {
    node = node.next
  }
  return node
}

insert()

在任意索引位置插入元素

/**
 * insert() 在任意位置插入元素
 * @param {*} element 待插入的元素
 * @param {Number} index 指定的索引位置
 * @returns {Boolean}
 */
insert (element, index) {
  // 判斷是否為合法index
  if (index < 0 || index > this.count) {
    return false
  }
  // 實(shí)例化節(jié)點(diǎn)
  let node = new Node(element)
  // 插入-第一個(gè)位置
  if (index === 0) {
    let current = this.head
    node.next = current
    this.head = node
  } else {
    // 查找到指定索引位置的前一個(gè)元素
    let previous = this.getElementAt(index - 1)
    let current = previous.next

    // 將上一個(gè)元素的next引用指向當(dāng)前新添加的node，將node的next引用指向current，則完成插入
    previous.next = node
    node.next = current
  }
  // 鏈表長(zhǎng)度+1
  this.count++
  return true
}

removeAt()

移除指定索引位置的元素
實(shí)現(xiàn)邏輯：判斷是否為鏈表第一項(xiàng)，若為第一項(xiàng)，則將this.head指向第二個(gè)元素即可；如果不是第一項(xiàng)，則獲取索引index位置的上一位置索引元素previous，以及下一位置索引元素current.next，將previous.next指向current.next即可

/**
 * removeAt() 移除指定位置的元素
 * @param {Number} index
 * @returns {*} element 移除的元素
 */
removeAt (index) {
  // 判斷是否是合法索引
  if (index < 0 || index > this.count) {
    return undefined
  }

  let current = this.head

  // 考慮是否是鏈表第一項(xiàng)
  if (index === 0) {
    this.head = current.next
  } else {
    // 方法一、 使用for循環(huán)迭代獲取指定索引位置的元素
    // 用于獲取上一位置元素
    // let previous
    // for (let i = 0; i < index; i++) {
    //   previous = current
    //   current = current.next
    // }
    // // 跳過(guò)當(dāng)前元素，將上一個(gè)元素的next指向下一個(gè)元素
    // previous.next = current.next

    // 方法二、借助getElementAt()方法
    // 查詢?cè)撍饕恢玫纳弦粋€(gè)元素
    let previous = this.getElementAt(index - 1)
    // 跳過(guò)中間元素，將上一個(gè)元素的next指向下一個(gè)元素
    current = previous.next
    previous.next = current.next
  }
  this.count--
  return current.element
}

indexOf()

查詢?cè)氐乃饕恢?p>實(shí)現(xiàn)邏輯：迭代元素，比較每一個(gè)元素與目標(biāo)元素是否相等；特別需要注意的是，對(duì)象類的值請(qǐng)傳入自定義的方法進(jìn)行比較是否相等s

/**
 * indexOf() 查詢?cè)氐乃饕恢? * @param {*} element 待查詢的元素
 * @returns {Number} index 索引位置，不存在則返回-1
 */
indexOf (element) {
  let current = this.head
  for (let i = 0; i < this.count && current != null; i++) {
    // 判斷兩個(gè)元素是否相同
    if (this.equalsFn(element, current.element)) {
      return i
    }
    current = current.next
  }
  return - 1
}

remove()

移除指定的元素

/**
 * remove() 移除元素
 * @param {*} element 待移除的元素
 * @returns {*} element 移除的元素
 */
remove (element) {
  // 獲取索引位置
  let index = this.indexOf(element)
  // 移除指定索引位置的元素
  return this.removeAt(index)
}

size()

獲取鏈表長(zhǎng)度

/**
 * size() 返回鏈表長(zhǎng)度
 * @returns {Number} 鏈表長(zhǎng)度
 */
size () {
  return this.count
}

isEmpty()

判斷鏈表是否為空

/**
 * isEmpty() 判斷鏈表是否為空
 * @returns {Boolean}
 */
isEmpty () {
  return this.count === 0
}

getHead()

獲取鏈表首位元素

/**
 * getHead() 獲取鏈表首位元素
 * @returns {*}
 */
getHead () {
  if (this.head != null) {
    return this.head.element
  }
  return undefined
}

clear()

清空鏈表

/**
 * clear() 清空鏈表
 */
clear () {
  this.count = 0
  this.head = undefined
}

toString()

鏈表字符串處理

/**
 * toString() 鏈表字符串化展示
 * @returns {String}
 */
toString () {
  // 判斷是否為空
  if (this.isEmpty()) {
    return ""
  }
  let objStr = `${this.head.element}`
  let current = this.head.next
  for (let i = 1; i < this.count; i++) {
    objStr = `${objStr},${current.element}`
    current = current.next
  }
  return objStr
}

let linkedList = new LinkedList()

console.log(linkedList.isEmpty()) // true

// push 尾部壓入元素
linkedList.push(15)
linkedList.push(20)
/*
  LinkedList {
    count: 2,
    head: Node {
      element: 15,
      next: Node {
        element: 20,
        next: undefined
      }
    },
    equalsFn: [Function: defaultEquals]
  }
*/
console.log(linkedList)

console.log(linkedList.isEmpty()) // false

// getElementAt() 指定索引位置的元素
let node = linkedList.getElementAt(1)
console.log(node)

// insert() 任意索引位置插入元素
linkedList.insert(22, 1)
linkedList.insert(33, 1)
console.log(linkedList.toString()) // 15,33,22,20

// removeAt() 移除指定索引位置的元素
console.log(linkedList.removeAt(1)) // 33

// remove() 移除元素
console.log(linkedList.remove(15)) // 15

console.log(linkedList.toString()) // 22,20

console.log(linkedList.getHead()) // 22

console.log(linkedList.size()) // 2
console.log(linkedList.toString()) // 22,20

console.log(linkedList.isEmpty()) // false

linkedList.clear()
console.log(linkedList.isEmpty()) // true

再次強(qiáng)調(diào)下：如果鏈表中存儲(chǔ)的是對(duì)象類型值，請(qǐng)務(wù)必傳入指定的比較函數(shù)equalsFn自行進(jìn)行比較，You should know why!

以上就是胡哥今天給大家分享的內(nèi)容，喜歡的小伙伴記得收藏、轉(zhuǎn)發(fā)、點(diǎn)擊右下角按鈕在看，推薦給更多小伙伴呦，歡迎多多留言交流...

胡哥有話說(shuō)，一個(gè)有技術(shù)，有情懷的胡哥！京東開放平臺(tái)首席前端攻城獅。與你一起聊聊大前端，分享前端系統(tǒng)架構(gòu)，框架實(shí)現(xiàn)原理，最新最高效的技術(shù)實(shí)踐！

長(zhǎng)按掃碼關(guān)注，更帥更漂亮呦！關(guān)注胡哥有話說(shuō)公眾號(hào)，可與胡哥繼續(xù)深入交流呦！