周亚博的个人博客

  • 首页
  • 盛夏光年
  • 陪风去荡
  • 布响丸啦
我频繁记录着 因为生活值得
  1. 首页
  2. 陪风去荡
  3. 正文

数据结构——单向链表

2022-08-12 115点热度 0人点赞 0条评论

一、什么是链表

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

image-20220812171453997

数组结构的缺点:

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

链表结构的特点:

  • 链表的的元素在内存中不必是连续的空间,实现灵活的内存动态管理
  • 不必在创建时确定大小,可以无限延伸
  • 链表插入和删除数据的效率很高,时间复杂度可以达到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
标签: 单向链表 数据结构
最后更新:2022-08-12

粥呀Bo

所谓惊喜,就是苦苦等候的兔子来了,后面却跟着狼

点赞
< 上一篇
下一篇 >

文章评论

取消回复
目录
  • 一、什么是链表
  • 二、链表结构的封装
        • 1、链表的相关操作
        • 2、实现封装
        • 3、运行结果

COPYRIGHT © 2022 zhouyaker.cn. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

陕ICP备2022009272号