单链表

  1. function LinkedList() {
  3.     // Node辅助类，表示要加入列表的项，element是即将添加到列表的值，next是指向列表中下一个节点项的指针
  4.     let Node = function (element) {
  5.         this.element = element
  6.         this.next = null
  7.     }
  9.     let length = 0
  10.     let head = null
  12.     // 向链表尾部追加元素
  13.     this.append = function (element) {
  14.         let node = new Node(element)
  15.         let current
  16.         if (head === null) { // 列表中第一个节点
  17.             head = node
  18.         } else {
  19.             current = head
  20.             while (current.next) {
  21.                 current = current.next // 找到最后一项，是null
  22.             }
  23.             current.next = node // 给最后一项赋值
  24.         }
  25.         length++ // 更新列表的长度
  26.     }
  28.     // 从链表中移除指定位置元素
  29.     this.removeAt = function (position) {
  30.         if (position > -1 && position < length) { // 值没有越界
  31.             let current = head
  32.             let previous, index = 0
  33.             if (position === 0) { //  移除第一项
  34.                 head = current.next
  35.             } else {
  36.                 while (index++ < position) {
  37.                     previous = current
  38.                     current = current.next
  39.                 }
  40.                 previous.next = current.next // 将previous与current的下一项连接起来，跳过current，从而移除
  41.             }
  42.             length-- // 更新列表的长度
  43.             return current.element
  44.         } else {
  45.             return null
  46.         }
  47.     }
  49.     // 在链表任意位置插入一个元素
  50.     this.insert = function (position, element) {
  51.         if (position >= 0 && position <= length) { // 检查越界值
  52.             let node = new Node(element),
  53.                 current = head,
  54.                 previous,
  55.                 index = 0
  56.             if (position === 0) { // 在第一个位置添加
  57.                 node.next = current
  58.                 head = node
  59.             } else {
  60.                 while (index++ < position) {
  61.                     previous = current
  62.                     current = current.next
  63.                 }
  64.                 node.next = current // 在previous与current的下一项之间插入node
  65.                 previous.next = node
  66.             }
  67.             length++
  68.             return true
  69.         } else {
  70.             return false
  71.         }
  72.     }
  74.     // 把链表内的值转换成一个字符串
  75.     this.toString = function (separator = ' ') {
  76.         let current = head,
  77.             string = ''
  78.         while (current) {
  79.             string += current.element + separator
  80.             current = current.next
  81.         }
  82.         let lastSeparator = string.lastIndexOf(separator);
  83.         return string.substr(0, lastSeparator);
  84.     }
  86.     // 在链表中查找元素并返回索引值
  87.     this.indexOf = function (element) {
  88.         let current = head,
  89.             index = 0
  90.         while (current) {
  91.             if (element === current.element) {
  92.                 return index
  93.             }
  94.             index++
  95.             current = current.next
  96.         }
  97.         return -1
  98.     }
  100.     // 从链表中移除指定元素
  101.     this.remove = function (element) {
  102.         let index = this.indexOf(element)
  103.         return this.removeAt(index)
  104.     }
  106.     this.isEmpty = function () {
  107.         return length === 0
  108.     }
  110.     this.size = function () {
  111.         return length
  112.     }
  114.     this.getHead = function () {
  115.         return head
  116.     }
  117. }
  118. let list = new LinkedList()
  119. list.append(1)
  120. list.append(2)
  121. console.log(list.toString('->')) // 1 2
  122. list.insert(0, 'hello')
  123. list.insert(1, 'world')
  124. console.log(list.toString()) // hello world 1 2
  125. list.remove(1)
  126. list.remove(2)
  127. console.log(list.toString()) // hello world