前端进阶:链表的概念和应用

为了实现链表以及链表的操纵，起首我们必要先界说链表的根基布局，第一步就是界说节点的数据布局。我们知道一个节点会有本身的值以及指向下一个节点的引用，以是可以这样界说节点：

let Node = function(el) { 

      this.el = el; 

      this.next = null; 

 } 

接下来我们界说一下链表的根基骨架：

// 单向链表, 每一个元素都有一个存储元素自身的节点和一个指向下一个元素引用的节点构成 

function linkedList() { 

  let Node = function(el) { 

      this.el = el; 

      this.next = null; 

  } 

  let length = 0 

  let head = null  // 用来存储第一个元素的引用 

  // 尾部添加元素 

  this.append = (el) => {}; 

  //插入元素 

  this.insert = (pos, el) => {}; 

  // 移除指定位置的元素 

  this.removeAt = (pos) => {}; 

  // 移除指定节点 

  this.remove = (el) => {}; 

  // 查询节点地址位置 

  this.indexOf = (el) => {}; 

  // 判定链表是否为空 

  this.isEmpty = () => {}; 

  // 返回链表长度 

  this.size = () => {}; 

  // 将链表转化为数组返回 

  this.toArray = () => {}; 

} 

由以上代码我们可以知道链表的初始长度为0，头部元素为null，接下来我们实现添加节点的成果。

追加节点的时辰起首必要知道头部节点是否存在，假如不存在直接赋值，存在的话则从新部开始遍历，直到找到下一个节点为空的节点，再赋值，并将链表长度+1，代码如下：

// 尾部添加元素 

this.append = (el) => { 

    let node = new Node(el), 

        current; 

    if(!head) { 

      head = node 

    }else { 

      current = head; 

      while(current.next) { 

        current = current.next; 

      } 

      current.next = node; 

    } 

    length++ 

}; 

实现插入节点逻辑起首我们要思量界线前提，假如插入的位置在头部可能比尾部位置还大，我们就没须要从新遍历一遍处理赏罚了，这样可以进步机能，以是我们可以这样处理赏罚：

//插入元素 

this.insert = (pos, el) => { 

    if(pos >=0 && pos <= length) { 

      let node = new Node(el), 

          previousNode = null, 

          current = head, 

          curIdx = 0; 

      if(pos === 0) { 

        node.next = current; 

        head = node; 

      }else { 

        while(curIdx++ < pos) { 

          previousNode = current; 

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!