关于算法-数据结构:数据结构与算法学习链表及其常用方法封装

42次阅读

共计 3266 个字符，预计需要花费 9 分钟才能阅读完成。

链表和数组一样，能够用于存储一系列的元素，然而链表和数组的实现机制齐全不同，链表相似于火车：有一个火车头，火车头会连贯一个节点，节点上有乘客（相似于数据），并且这个节点会连贯下一个节点，以此类推

数组：

要存储多个元素，数组（或称为列表）可能是最罕用的数据结构
咱们之前说过，简直每一种编程语言都有默认实现数组构造
然而数组也有很多毛病：
数组的创立通常须要申请一段间断的内存空间（一整块的内存），并且大小是固定的（大多数编程语言数组都是固定的），所以当以后数组不能满足容量需要时，须要扩容（个别状况下是申请一个更大的数组，而后将元素组中的元素赋值过来）
而且在数组结尾或两头地位插入数据的老本很高，须要进行大量元素的位移
只管咱们学过的 js 的 Array 类办法能够帮咱们做这些事，但背地的原理仍然是这样的

链表的劣势

要存储多个元素，另外一个抉择就是链表
但不同数组，链表的元素在内存中不用是间断的空间
链表的每个元素由一个存储元素自身的节点和一个指向下一个元素的援用（有些语言成为指针或者连贯）组成。
内存空间不是必须间断的，能够充沛利用计算机的内存，实现灵便的内存动静治理
链表不用在创立时就确定大小，并且大小能够有限的延长上来
链表再插入和删除数据时，工夫复杂度能够达到 O(1), 绝对数组效率高很多

链表拜访任何一个地位的元素时，都须要从头开始拜访（无奈跳过第一个元素去拜访任何一个元素）
无奈通过下标间接拜访元素，须要从头一个个拜访，直到找到对应的元素

append(data): 向列表尾部增加一个新的项
insert（position，data）: 向列表的特定地位插入一个新的项
get(position)：获取对应地位的元素
indexOf（data）: 返回元素在列表中的索引。如果列表中没有该元素则返回 -1
update(positon,data): 批改某个地位的元素
removeAt（position）：从列表的特定地位移除一项
remove（data）: 从列表中移除一项
isEmpty（）：如果链表中不蕴含任何元素，返回 true, 如果链表长度大于 0 则返回 false
Size（）：返回链表蕴含的元素个数。与数组的 length 属性类似
toString（）：将链表中的数据转换为字符串

class CreateData {constructor(data) {
    this.data = data;
    this.next = null
 }
}
class LinkedList {constructor() {
    this.head = '';
    this.length = 0;
  }
  append(data) {let newData = new CreateData(data);
    if (this.head === '') {
      newData.next = this.head;
      this.head = newData;
    } else {
      let current = this.head;
      while (current.next) {current = current.next}
      current.next = newData
 }
    this.length++;
  }
  insert(position, data) {if (position < 0 || position > this.length) return false
    let newData = new CreateData(data);
    if (position === 0) {
      newData.next = this.head;
      this.head = newData
 } else {
      let index = 0;
      let current = this.head;
      let prev = null;
      while (index++ < position) {
        prev = current
 current = current.next;
      }
      prev.next = newData;
      newData.next = current
 }
    this.length++
  }
  get(position) {if (position < 0 || position >= this.length) return null;
    let current = this.head;
    let index = 0;
    while (index++ < position) {current = current.next}
    return current.data;
  }
  indexOf(data) {
    let current = this.head;
    let index = 0;
    while (current.data !== data) {if (!current.next) return -1
        current = current.next;
      index += 1;
    }
    return index
 }
  update(position, data) {if (position < 0 || position >= this.length) return false;
    let newData = new CreateData(data);
    let current = this.head;
    let index = 0;
    while (index++ < position) {current = current.next;}
    current.data = data
  }
  removeAt(position) {if (position < 0 || position >= this.length) return false;
    if (position === 0) {
      let current = this.head;
      this.head = current.next
 } else {
      let current = this.head;
      let index = 0;
      let prev = null;
      while (index++ < position) {
        prev = current;
        current = current.next;
      }
      prev.next = current.next
 }
    this.length -= 1;
  }
  remove(data) {let i = this.indexOf(data);
    this.removeAt(i)
  }
  isEmpty() {return this.length > 0 ? false : true;}
  size() {return this.length}
  toString() {
    let current = this.head;
    let str = '';
    while (current) {
      str += current.data + ',';
      current = current.next
 }
    return str.slice(0, str.length - 1)
  }
}

let linkedList = new LinkedList();
linkedList.append('小强');
linkedList.append('小红');
linkedList.append('小花');
console.log('链表向最初增加一项', linkedList)
linkedList.insert(1, '小李');
console.log('链表向指定地位插入一项', linkedList)
console.log('依据索引获取某一项的值', linkedList.get(3))
console.log('依据某一项值获取对应索引', linkedList.indexOf('小花'))
linkedList.update(2, '小明')
console.log('依据索引替换传进去的值', linkedList)
linkedList.removeAt(2)
console.log('依据索引删除某一项',linkedList)
linkedList.remove('小强')
console.log('依据某一项值删除数据',linkedList)
console.log('查看是否为空', linkedList.isEmpty())
console.log('查看链表元素的个数', linkedList.size())
console.log('将链表内的元素转化成字符串', linkedList.toString())

天行健，小人以自暴自弃

正文完