数据结构与算法之链表及常用操作

什么是链表？

链表是一种用于存储数据的线性结构，链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同

链表类似于火车：有一个火车头，火车头会连接一个节点，节点上有乘客（类似于数据），并且这个节点会连接下一个节点，以此类推   

链表的特点：

1.存储多个元素

2.链表中的元素在内存中不必是连续的空间

3.链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用zucheng

相对于数组，链表的一些优势

1.内存空间不是必须连续的，可以充分利用计算机的内存，实现灵活的内存动态管理

2.链表不必在创建时就确定大小，并且大小可以无限的延伸下去

3.链表在插入和删除数据时，时间复杂度可以达到O（1），相对数组效率高很多

单向链表的封装：

<script>
    // 封装链表类
    function LinkList() {
      // 内部的类：节点类
      function Node(data) {
        this.data = data
        this.next = null
      }
      // 属性
      this.head = null
      this.length = 0
    }
</script>

链表的常见操作：

append(element):向列表尾部添加一个新的项

insert(position,element):向列表的特定位置插入一个新的项

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

indexOf(element):返回元素在列表中的索引，如果列表中没有该元素则返回-1

update(positon):修改某个位置的元素

removeAt(positon):从列表的特定位置移除一项

remove(element):从列表中移除一项

isEmpty():如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false

size():返回链表包含的元素个数，与数组的length属性类似

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

append方法：

 <script>
    // 封装链表类
    function LinkList() {
      // 内部的类：节点类
      function Node(data) {
        this.data = data
        this.next = null
      }
      // 属性
      this.head = null
      this.length = 0
      // 追加方法
      LinkList.prototype.append = function (data) {
        // 创建新的节点
        let newNode = new Node(data)
        // 判断是否添加的是第一个节点
        if(this.length == 0) { //是第一个节点
          this.head = newNode
        } else { //不是第一个节点
          //找到最后一个节点
          let current = this.head
          while(current.next) {
            current = current.next
          }
          // 最后节点的next指向新的节点
          current.next = newNode
        }
        // length+1
        this.length += 1
      }
    }
  </script>

insert方法:

// insert方法
      LinkList.prototype.insert = function (positon,data) {
        // 对positon进行越界判断
        if(positon < 0 || positon > this.length) return false
        // 根据data创建newNode
        let newNode = new Node(data)
        // 判断插入的位置是否是第一个
        if(positon == 0) {
          newNode.next = this.head
          this.head = newNode
        } else {
          let index = 0
          let current = this.head
          let previous = null
          while(index++ < position) {
            previous = current
            current = current.next
          }
          newNode.next = current
          previous.next = newNode
        }
      }

GET方法：

 // get方法
      LinkList.prototype.get = function (positon) {
        // 越界判断
        if(positon < 0 || positon >= this.length) return null
        // 获取对应的data
        let current = this.head
        let index = 0
        while(index++ < positon) {
          current = current.next
        }
        return current.data
      }