副标题#e#

为了实现链表以及链表的操作，首先我们需要先定义链表的基本结构，第一步就是定义节点的数据结构。我们知道一个节点会有自己的值以及指向下一个节点的引用，所以可以这样定义节点：

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，接下来我们实现添加节点的功能。

2.2 实现添加节点

追加节点的时候首先需要知道头部节点是否存在，如果不存在直接赋值，存在的话则从头部开始遍历，直到找到下一个节点为空的节点，再赋值，并将链表长度+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++ 

}; 

2.3 实现插入节点

实现插入节点逻辑首先我们要考虑边界条件，如果插入的位置在头部或者比尾部位置还大，我们就没必要从头遍历一遍处理了，这样可以提高性能，所以我们可以这样处理：

//插入元素 

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; 

#p#副标题#e#

          current = current.next; 

        } 

        node.next = current; 

        previousNode.next = node; 

        length++; 

        return true 

      } 

    }else { 

      return false 

    } 

}; 

2.4 根据节点的值查询节点位置

根据节点的值查询节点位置实现起来比较简单，我们只要从头开始遍历，然后找到对应的值之后记录一下索引即可：

// 查询节点所在位置 

this.indexOf = (el) => { 

    let idx = -1, 

        curIdx = -1, 

        current = head; 

    while(current) { 

      idx++ 

      if(current.el === el) { 

        curIdx = idx 

        break; 

      } 

      current = current.next; 

    } 

    return curIdx 

}; 

这里我们之所以要用idx和curIdx两个变量来处理，是因为如果用户传入的值不在链表里，那么idx的值就会有问题，所以用curIdx来保证准确性。

2.5 移除指定位置的节点

移除指定位置的节点也需要判断一下边界条件，可插入节点类似，但要注意移除之后一定要将链表长度-1，代码如下：

// 移除指定位置的元素 

this.removeAt = (pos) => { 

    // 检测边界条件 

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

      let previousNode = null, 

               current = head, 

               curIdx = 0; 

      if(pos === 0) { 

        // 如果pos为第一个元素 

        head = current.next 

      }else { 

        while(curIdx++ < pos) { 

          previousNode = current; 

#p#副标题#e#

          current = current.next; 

        } 

        previousNode.next = current.next; 

      } 

      length –; 

      return current.el 

    }else { 

      return null 

    } 

}; 

2.6 移除指定节点

移除指定节点实现非常简单，我们只需要利用之前实现好的查找节点先找到节点的位置，然后再用实现过的removeAt即可，代码如下：

// 移除指定节点 

this.remove = (el) => { 

  let idx = this.indexOf(el); 

  this.removeAt(idx); 

}; 

2.7 获取节点长度

这里比较简单，直接上代码：

// 返回链表长度 

this.size = () => { 

  return length 

}; 

2.8 判断链表是否为空

判断链表是否为空我们只需要判断长度是否为零即可：

// 返回链表长度 

this.size = () => { 

  return length 

}; 

2.9 打印节点

打印节点实现方式有很多，大家可以按照自己喜欢的格式打印，这里笔者直接将其打印为数组格式输出，代码如下：

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

this.toArray = () => { 

    let current = head, 

        results = []; 

    while(current) { 

      results.push(current.el); 

      current = current.next; 

    } 

    return results 

};  

这样，我们的单向链表就实现了，那么我们可以这么使用：

let link = new linkedList() 

// 添加节点 

link.append(1) 

link.append(2) 

// 查找节点 

link.indexOf(2) 

// … 

3.原生javascript实现一条个双单向链表

有了单向链表的实现基础，实现双向链表也很简单了，我们无非要关注的是双向链表的节点创建，这里笔者实现一个例子供大家参考：

let Node = function(el) { 

      this.el = el; 

      this.previous = null; 

      this.next = null; 

 } 

let length = 0 

let head = null  // 用来存储头部元素的引用 

let tail = null  // 用来存储尾部元素的引用 

#p#副标题#e##p#分页标题#e#

由代码可知我们在节点中会有上一个节点的引用以及下一个节点的引用，同时这里笔者添加了头部节点和尾部节点方便大家操作。大家可以根据自己的需求实现双向链表的功能，这里笔者提供一份自己实现的代码，可以参考交流一下：

// 双向链表, 每一个元素都有一个存储元素自身的节点和指向上一个元素引用以及下一个元素引用的节点组成 

function doubleLinkedList() { 

  let Node = function(el) { 

      this.el = el; 

      this.previous = null; 

      this.next = null; 

  } 

  let length = 0 

  let head = null  // 用来存储头部元素的引用 

  let tail = null  // 用来存储尾部元素的引用 

 

  // 尾部添加元素 

  this.append = (el) => { 

    let node = new Node(el) 

    if(!head) { 

      head = node 

    }else { 

      tail.next = node; 

      node.previous = tail; 

    } 

    tail = node; 

    length++ 

  }; 

  // 插入元素 

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

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

      let node = new Node(el); 

      if(pos === length – 1) { 

        // 在尾部插入 

        node.previous = tail.previous; 

        node.next = tail; 

        tail.previous = node; 

        length++; 

        return true 

      } 

      let current = head, 

          i = 0; 

      while(i < pos) { 

        current = current.next; 

        i++ 

      } 

      node.next = current; 

      node.previous = current.previous; 

      current.previous.next = node; 

      current.previous = node; 

      length ++; 

      return true     

    }else { 

      throw new RangeError(`插入范围有误`) 

    } 

  }; 

  // 移除指定位置的元素 

  this.removeAt = (pos) => { 

    // 检测边界条件 

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

      throw new RangeError(`删除范围有误`) 

    }else { 

      if(length) { 

        if(pos === length – 1) { 

          // 如果删除节点位置为尾节点,直接删除,节省查找时间 

          let previous = tail.previous; 

          previous.next = null; 

          length –; 

          return tail.el 

        }else { 

          let current = head, 

              previous = null, 

              next = null, 

              i = 0; 

          while(i < pos) { 

#p#副标题#e#

            current = current.next 

            i++ 

          } 

          previous = current.previous; 

          next = current.next; 

          previous.next = next; 

          length –; 

          return current.el 

        } 

      }else { 

        return null 

      } 

    } 

  }; 

  // 移除指定节点 

  this.remove = (el) => { 

    let idx = this.indexOf(el); 

    this.removeAt(idx); 

  }; 

  // 查询指定位置的链表元素 

  this.get = (index) => { 

    if(index < 0 || index >= length) { 

      return undefined 

    }else { 

      if(length) { 

        if(index === length – 1) { 

          return tail.el 

        } 

        let current = head, 

            i = 0; 

        while(i < index) { 

          current = current.next 

          i++ 

        } 

        return current.el 

      }else { 

        return undefined 

      } 

    } 

  } 

  // 查询节点所在位置 

  this.indexOf = (el) => { 

    let idx = -1, 

        current = head, 

        curIdx = -1; 

    while(current) { 

      idx++ 

      if(current.el === el) { 

        curIdx = idx; 

        break; 

      } 

      current = current.next; 

    } 

    return curIdx 

  }; 

  // 判断链表是否为空 

  this.isEmpty = () => { 

    return length === 0 

  }; 

  // 返回链表长度 

  this.size = () => { 

    return length 

  }; 

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

  this.toArray = () => { 

    let current = head, 

        results = []; 

    while(current) { 

      results.push(current.el); 

      current = current.next; 

    } 

    return results 

  };