JavaScript【資料結構與演算法】(二) 單向鏈表-有解無憂

鏈表的優勢

鏈表中的元素在記憶體中不必是連續的空間
鏈表的每一個元素由一個存盤元素本身的節點和一個指向下一個元素的參考
鏈表在創建的時候不需要確定大小，大小可以無線延伸下去

單向鏈表的一些基本操作

鏈表得有一個head指向第一個節點，其次每個節點中有data和next,next指向下一個節點

append(element): 在尾部添加一個新的項
insert(position,ele): 向鏈表的特定位置插入一個新的項
get(position): 獲取對應位置的元素
indexOf(ele): 回傳元素在鏈表中的索引，如果沒有該元素則回傳-1
update(position，ele): 修改某個位置的元素
removeAt(position): 從串列的特定位置移除一項
remove(ele): 從鏈表中移除一項
isEmpty(): 是否為空
size(): 鏈表長度
toString(): 輸出元素的值

鏈表操作的封裝

鏈表的基本實作

function LinkedList() {
 this.head = null
 this.length = 0

 //節點類
 function Node(data) {
   this.data = data
   this.next = null
 }
}

1.append

LinkedList.prototype.append = function (data) {
  //先創建這個節點
  let newNode = new Node(data)
  //如果添加的為第一個節點,將head指標指向該節點的data
  if (this.length == 0) {
    this.head = newNode
  } else {
    let current = this.head
    while (current.next) {
      //找下一個
      current = current.next
    }
    //最后節點的next指向新的節點
    current.next = newNode
  }
  this.length++
}

2.insert

LinkedList.prototype.insert = function (position, data) {
  //對position進行越界判斷和長度判斷
  if (position < 0 || position > this.length) return false

  //創建節點
  let newNode = new Node(data)
  //如果是插入在第一個
  if (position == 0) {
    newNode.next = this.head
    this.head = newNode
  } else { //如果不是插入第一個
    let index = 0 //自己定義一個位置
    let current = this.head //先讓current為第一個節點
    while (index++ < position - 1) { //3
      current = current.next
    }
    newNode.next = current.next
    current.next = newNode
  }
  this.length++
  return true
}

3.get

LinkedList.prototype.get = function (position) {
  //對position進行越界判斷和長度判斷
  if (position < 0 || position >= this.length) return false

  //創建一個空的字符用來接收
  let str = ""
  let index = 0 //自己定義一個位置
  let current = this.head //先讓current為第一個節點
  while (index++ < position) {
    current = current.next
  }
  str += current.data
  return str
}

4.indexOf

LinkedList.prototype.indexOf = function (data) {
  //從第一個開始找
  let index = 0
  //一個鏈表中可能存在幾個相同的幾個值，將其位置全部存放在一個陣列中
  let arr = []
  let current = this.head
  while (index < this.length) {
    //符合的位置全部push到陣列中
    if (current.data == data) {
      arr.push(index)
    }
    current = current.next
    index++
  }
  // return index
  // 回圈結束后再根據陣列中的數來做判斷
  if (arr.length == 0) {
    return -1
  } else if (arr.length == 1) { //如果只有一個的話就不回傳陣列，直接回傳這個位置
    return arr[0]
  } else {
    return arr
  }
}

5.update

LinkedList.prototype.update = function (position, data) {
  //對position進行越界判斷和長度判斷
  if (position < 0 || position >= this.length) return false

  let index = 0 //自己定義一個位置
  let current = this.head //先讓current為第一個節點
  while (index++ < position) {
    current = current.next
  }
  current.data = data
}

6.removeAt

LinkedList.prototype.removeAt = function (position) {
  //對position進行越界判斷和長度判斷
  if (position < 0 || position >= this.length) return false

  let index = 0 //前一個的位置
  let current = this.head //先讓current為第一個節點
  //如果洗掉的是第一個節點
  if(position === 0) {
    this.head = this.head.next 
  }else {
    while (index++ < position - 1) {//找到要洗掉節點的前一個節點
      current = current.next
    }
        /**
   * 將鏈表斷開
   */
    let mid = current.next
    current.next = mid.next
    mid.next = null
  }
  this.length -= 1
  return true
}

7.remove

LinkedList.prototype.remove = function(ele) {
  //直接呼叫indexOf()與removeAt()
  const position = this.indexOf(ele)
  console.log(position);
  if(position === -1) {
    return false
  }else if(position instanceof Array) {
    position.forEach((item) => {
      this.removeAt(item)
      this.remove(ele)
    })
  }else {
    this.removeAt(position)
  }
  return true
}

8.toString

LinkedList.prototype.toString = function () {
 let current = this.head
 let listString = ""
 while (current) {
   listString += current.data + " "
   current = current.next
 }
 return listString
}

完整代碼實作

function LinkedList() {
  this.head = null
  this.length = 0

  //節點類
  function Node(data) {
    this.data = data
    this.next = null
  }

  //1.追加方法
  LinkedList.prototype.append = function (data) {
    //先創建這個節點
    let newNode = new Node(data)
    //如果添加的為第一個節點,將head指標指向該節點的data
    if (this.length == 0) {
      this.head = newNode
    } else {
      let current = this.head
      while (current.next) {
        //找下一個
        current = current.next
      }
      //最后節點的next指向新的節點
      current.next = newNode
    }
    this.length++
  }

  //2.toString方法
  LinkedList.prototype.toString = function () {
    let current = this.head
    let listString = ""
    while (current) {
      listString += current.data + " "
      current = current.next
    }
    return listString
  }

  //3.insert方法
  LinkedList.prototype.insert = function (position, data) {
    //對position進行越界判斷和長度判斷
    if (position < 0 || position > this.length) return false

    //創建節點
    let newNode = new Node(data)
    //如果是插入在第一個
    if (position == 0) {
      newNode.next = this.head
      this.head = newNode
    } else { //如果不是插入第一個
      let index = 0 //自己定義一個位置
      let current = this.head //先讓current為第一個節點
      while (index++ < position - 1) { //3
        current = current.next
      }
      newNode.next = current.next
      current.next = newNode
    }
    this.length++
    return true
  }

  //4.get方法
  LinkedList.prototype.get = function (position) {
    //對position進行越界判斷和長度判斷
    if (position < 0 || position >= this.length) return false

    //創建一個空的字符用來接收
    let str = ""
    let index = 0 //自己定義一個位置
    let current = this.head //先讓current為第一個節點
    while (index++ < position) {
      current = current.next
    }
    str += current.data
    return str
  }

  //5.update方法
  LinkedList.prototype.update = function (position, data) {
    //對position進行越界判斷和長度判斷
    if (position < 0 || position >= this.length) return false

    let index = 0 //自己定義一個位置
    let current = this.head //先讓current為第一個節點
    while (index++ < position) {
      current = current.next
    }
    current.data = data
  }

  //6.indexOf方法
  LinkedList.prototype.indexOf = function (data) {
    //從第一個開始找
    let index = 0
    //一個鏈表中可能存在幾個相同的幾個值，將其位置全部存放在一個陣列中
    let arr = []
    let current = this.head
    while (index < this.length) {
      //符合的位置全部push到陣列中
      if (current.data == data) {
        arr.push(index)
      }
      current = current.next
      index++
    }
    // return index
    // 回圈結束后再根據陣列中的數來做判斷
    if (arr.length == 0) {
      return -1
    } else if (arr.length == 1) { //如果只有一個的話就不回傳陣列，直接回傳這個位置
      return arr[0]
    } else {
      return arr
    }
  }

  //7.removeAt(position)
  LinkedList.prototype.removeAt = function (position) {
    //對position進行越界判斷和長度判斷
    if (position < 0 || position >= this.length) return false

    let index = 0 //前一個的位置
    let current = this.head //先讓current為第一個節點
    //如果洗掉的是第一個節點
    if(position === 0) {
      this.head = this.head.next 
    }else {
      while (index++ < position - 1) {//找到要洗掉節點的前一個節點
        current = current.next
      }
          /**
     * 將鏈表斷開
     */
      let mid = current.next
      current.next = mid.next
      mid.next = null
    }
    this.length -= 1
    return true
  }

  //8.remove()
  LinkedList.prototype.remove = function(ele) {
    //直接呼叫indexOf()與removeAt()
    const position = this.indexOf(ele)
    console.log(position);
    if(position === -1) {
      return false
    }else if(position instanceof Array) {
      position.forEach((item) => {
        this.removeAt(item)
        this.remove(ele)
      })
    }else {
      this.removeAt(position)
    }
    return true
  }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/295671.html

標籤：其他

上一篇：魯振江近期學習總結

下一篇：JavaScript學習之煙花特效實作（面向物件）

JavaScript【資料結構與演算法】(二) 單向鏈表

目錄

鏈表的優勢

單向鏈表的一些基本操作

鏈表操作的封裝

鏈表的基本實作

1.append

2.insert

3.get

4.indexOf

5.update

6.removeAt

7.remove

8.toString

完整代碼實作