数据结构——单向链表

一、什么是链表

链表包括数据和指向下一个连接点的对象的引用,类似火车的结构

数组结构的缺点：

• 创建数组需要申请连续的内存空间，并且在大多数编程语言中大小都是固定的
• 扩容数组则非常消耗性能
• 在数组的开头或中间插入和删除数据的成本很高，要进行大量数据的位移

链表结构的特点：

• 链表的的元素在内存中不必是连续的空间，实现灵活的内存动态管理
• 不必在创建时确定大小，可以无限延伸
• 链表插入和删除数据的效率很高，时间复杂度可以达到O(1)

链表结构的缺点：

• 访问任何一个元素都要从头开始
• 无法通过下标直接访问元素，无法直接找到对应元素

综上所述，频繁插入删除操作就使用链表，如果需要使用下标查找元素，就使用数组

二、链表结构的封装

1、链表的相关操作

append(data)：向链表尾部添加一个新的项

insert(position, data)：向链表的特定位置插入一个新的项

remove(data)：从列表中移除一项

get(position):获取对应位置的元素

update(positon,newData):修改每个位置的元素

indexOf(data)：返回元素在列表中的索引。如果列表中没有该元素则返回-1

removeAt(data)：从链表的特定位置移除一项

isEmpty()：如果链表中不包含任何元素则返回true，否则则返回false

size()：返回链表包含的元素个数

toString()：由于链表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值

2、实现封装

/**
 * 封装一个链表类
*/

function LinkedList() {
  // 内部类，保存数据和下一个节点的指向
  function Node(data) {
    this.data = data
    this.next = null  // 先不传入节点引用
  }
  // 属性
  this.head = null // 链表的开头，指向第一个节点
  this.length = 0  // 记录链表的长度

  // 1、节点追加的方法
  LinkedList.prototype.append = function (data) {
    // 创建新节点
    let newNode = new Node(data)

    // 判断是否添加的是第一个节点
    if (this.length == 0) {
      this.head = newNode
    } else {
      let flag = this.head  // 第一个节点地址
      // 找到现有的最后一个节点
      while (flag.next) {
        flag = flag.next  // 只有最后一个节点的next属性才null
      }
      // 添加节点，并将节点的地址储存到上一个节点的next属性中
      flag.next = newNode
    }

    // 修改节点的长度
    this.length += 1
  }

  // 2、toString方法
  LinkedList.prototype.toString = function () {
    // 从第一个节点开始获取所有的data
    let flag = this.head
    let result = ''
    while (flag) {
      result += flag.data + ' '
      flag = flag.next
    }
    return result
  }

  // 3、insert方法
  LinkedList.prototype.insert = function (position, data) {
    // 根据位置插入，先判断位置是否合理
    if (position < 0 || position > this.length) return false

    // 创建节点
    let newNode = new Node(data)

    // 判断是否是插入到第一个节点
    if (position == 0) {
      // 将原本第一个节点的位置保存到新节点，新节点的位置保存到head
      newNode.next = this.head
      this.head = newNode
    } else {
      let index = 0
      // 待插入位置的原节点默认值（head）
      let flag = this.head
      // 待插入位置的前一个节点(默认为空)
      let previous = null
      // 找到对应位置的节点和对应位置的上一个节点
      while (index++ < position) {
        previous = flag
        flag = flag.next
      }
      newNode.next = flag
      previous.next = newNode
    }

    this.length += 1
    return true
  }

  // 4、get方法
  LinkedList.prototype.get = function (position) {
    // 根据位置插入，先判断位置是否合理
    if (position < 0 || position >= this.length) return null
    // 获取对应索引的数据
    let flag = this.head
    let index = 0
    while (index < position) {
      flag = flag.next
      index++
    }
    return flag.data
  }

  // 5、indexOf方法
  LinkedList.prototype.indexOf = function (data) {
    let flag = this.head
    let index = 0
    while (flag) {
      if (flag.data == data) {
        return index
      }
      flag = flag.next
      index += 1
    }
    return -1 // 没有找到
  }

  // 6、update方法
  LinkedList.prototype.update = function (position, newData) {
    // 根据位置插入，先判断位置是否合理
    if (position < 0 || position >= this.length) return false

    // 查找节点
    let flag = this.head
    let index = 0
    while (index < position) {
      flag = flag.next
      index++
    }
    // 修改对应的data
    flag.data = newData
    return true
  }

  // 7、removeAt方法(通过索引删除)
  LinkedList.prototype.removeAt = function (position) {
    // 根据位置插入，先判断位置是否合理
    if (position < 0 || position >= this.length) return null

    // 判断是否删除第一个节点
    let flag = this.head  // 当前遍历到的节点
    if (position == 0) {
      this.head = this.head.next
    } else {
      let index = 0 // 索引
      let previous = null   // 当前遍历节点的前一个节点
      while (index < position) {
        previous = flag
        flag = flag.next
        index++
      }
      previous.next = flag.next
    }
    // 修改长度
    this.length -= 1
    return flag.data
  }

  // 8、remove方法(通过数据删除)
  LinkedList.prototype.remove = function (data) {
    // 获取data所在的位置
    let position = this.indexOf(data)
    // 根据位置信息删除节点
    return this.removeAt(position)
  }

  // 9、isEmpty方法
  LinkedList.prototype.isEmpty = function () {
    return this.length == 0
  }

  // 10、size方法
  LinkedList.prototype.size = function (data) {
    return this.length
  }
}

3、运行结果

let res = new LinkedList()
// 插入数据
res.append('a')
res.append('b')
res.append('c')
res.append('d')
// 返回字符串
console.log(res.toString())   // a b c d
// 在索引为2的位置插入'ok'
res.insert(2, 'ok')
console.log(res.toString())   // a b ok c d
// 在链表末尾插入'我'
res.insert(res.length, '我')
console.log(res.toString())   // a b ok c d 我
// 根据索引获取数据
console.log(res.get(0)) // a
console.log(res.get(res.length - 1)) // 我
// 找到数据对应的索引
console.log(res.indexOf('a')) // 0
console.log(res.indexOf('ok')) // 2
// 修改索引为2的值为'no'
res.update(2, 'no')
console.log(res.toString()) // a b no c d 我
// 删除索引为3的值
console.log(res.removeAt(3))  // c
console.log(res.toString())   // a b no d 我
// 删除'我'
console.log(res.remove('我')) // 我
console.log(res.toString())   // a b no d
// 删除一个不存在的'中国'
console.log(res.remove('中国')) // null
// 判断链表是否为空
console.log(res.isEmpty())  // false
// 链表长度
console.log(res.size())   // 4