JS实现双链表

链表结构是我们在面试中经常会被问起的较为基础的数据结构问题，起初学习数据结构使用的是 C++语言，最近在做前端面试题的过程中没碰到了需要用 js 实现双链表的需求，百度出来的文章发现可很多错误，于是索性自己重新写了，并且列出了一些错误点，这里给大家较为详细的一步步看一下实现思想和步骤，相较于 C++语言，js 的实现可以说是很简单了，不需要创建繁琐的对象，更加直观易懂； 首先我们来看一下双向链表的结构图： 在这里插入图片描述每个结点包含三部分，指向前一个结点的指针（pre），指向后一个节点的指针（next），以及自己的数据部分（element）,于是我们就可以先写出结点对象

function Node:定义结点对象

function Node(element) {
  this.element = element
  this.next = null
  this.previous = null
}

然后我们开始实现插入链表的算法 在这里插入图片描述

（声明）下面函数中的 this 是我们最后初始化链表的实例，这里大家不要疑惑。可以拉到最下面我们初始化链表那里，相信你会明白呦

function insert:插入节点

function insert(newelement, currentelement) {
  var newNode = new Node(newelement)
  var currentNode = this.find(currentelement)
  if (currentNode === 'error') {
    console.log('无法插入，要插入节点不存在')
    return
  }
  if (currentNode.next != null) {
    newNode.next = currentNode.next
    currentNode.next = newNode
    newNode.previous = currentNode
    newNode.next.previous = newNode
  } else {
    currentNode.next = newNode
    newNode.previous = currentNode
  }
}

function find:找到插入位置

function find(element) {
  var currentNode = this.head
  while (currentNode.element != element) {
    /*如果找到最后一个节点还没有找到我们的插入点，那么我们就会返回错误*/
    if (currentNode.next == null) {
      console.log('can not find this node; maybe not have this node')
      return 'error'
    }
    currentNode = currentNode.next
  }
  return currentNode
}

接下来是移除结点的实现，如果看懂了插入节点的实现，那么移除就会很简单了，相信大家都可以很快明白，这里就直接贴出实现代码；

function remove:移除一个结点

function remove(element) {
  var currentNode = this.find(element)
  if (currentNode === 'error') {
    console.log('要移除节点不存在')
    return
  }
  /*首先是不是头尾节点的情况*/

  if (currentNode.next != null && currentNode.previous != null) {
    currentNode.previous.next = currentNode.next
    currentNode.next.previous = currentNode.previous
    currentNode.next = null
    currentNode.previous = null
  } else if (currentNode.previous == null) {
    /*当是头节点的时候*/
    this.head = currentNode.next
    currentNode.next.previous = null
    currentNode.next = null
  } else if (currentNode.next == null) {
    /*当是尾节点的时候 */

    currentNode.previous.next = null
    currentNode.previous = null
  }
}

截止到这里我们基本功能已经有了，下面使我们根据自己需要可以自定义一些其他函数

function lastNode：找到最后一个节点

function lastNode() {
  var head = this.head
  while (head.next != null) {
    head = head.next
  }
  return head //这里head在尾节点的位置
}

function append:将要添加的结点放在链表末尾

function append(element) {
  var lastnode = this.lastNode()
  var newNode = new Node(element)
  lastnode.next = newNode
  newNode.previous = lastnode
}

function showlist：将链表所有的结点打印出来

function showlist() {
  var head = this.head
  do {
    console.log(head.element)
    head = head.next
  } while (head != null)
  // 大家可以看一下下面注释内容存在什么问题，留给大家思考一下
  // while (head.next != null) {
  //   console.log(head.element)
  //   head = head.next
  // }
}

接下来是对链表进行初始化，这也是上述函数中所有this所代表的实例

function initlist:初始化链表，并将所有方法注册到链表中

function initlist() {
  this.head = new Node('one')
  this.find = find
  this.insert = insert
  this.remove = remove
  this.showlist = showlist
  this.lastNode = lastNode
  this.append = append
}

var list = new initlist()
list.insert('two', 'one')
list.insert('four', 'two')
list.insert('three', 'two')

// console.log(list.head.next)
list.showlist()
list.append('A')
list.append('B')
list.insert('B2', 'B')
list.showlist()
console.log(list.lastNode())
// list.remove('one')
// list.showlist()
console.log(list.find('A').previous)
// console.log(list.find('four').previous)
// console.log(list.head.element)

下面是运行结果： 在这里插入图片描述

源码：

function Node(element) {
  this.element = element
  this.next = null
  this.previous = null
}
function find(element) {
  var currentNode = this.head
  while (currentNode.element != element) {
    if (currentNode.next == null) {
      console.log('can not find this node; maybe not have this node')
      return 'error'
    }
    currentNode = currentNode.next
  }
  return currentNode
}
function insert(newelement, currentelement) {
  var newNode = new Node(newelement)
  var currentNode = this.find(currentelement)
  if (currentNode === 'error') {
    console.log('无法插入，要插入节点不存在')
    return
  }
  if (currentNode.next != null) {
    newNode.next = currentNode.next
    currentNode.next = newNode
    newNode.previous = currentNode
    newNode.next.previous = newNode
  } else {
    currentNode.next = newNode
    newNode.previous = currentNode
  }
}
function remove(element) {
  var currentNode = this.find(element)
  if (currentNode === 'error') {
    console.log('要移除节点不存在')
    return
  }
  /*首先是不是头尾节点的情况*/

  if (currentNode.next != null && currentNode.previous != null) {
    currentNode.previous.next = currentNode.next
    currentNode.next.previous = currentNode.previous
    currentNode.next = null
    currentNode.previous = null
  } else if (currentNode.previous == null) {
    /*当是头节点的时候*/
    this.head = currentNode.next
    currentNode.next.previous = null
    currentNode.next = null
  } else if (currentNode.next == null) {
    /*当是尾节点的时候 */

    currentNode.previous.next = null
    currentNode.previous = null
  }
}
function showlist() {
  var head = this.head
  do {
    console.log(head.element)
    head = head.next
  } while (head != null)
  // while (head.next != null) {
  //   console.log(head.element)
  //   head = head.next
  // }
}
function initlist() {
  this.head = new Node('one')
  this.find = find
  this.insert = insert
  this.remove = remove
  this.showlist = showlist
  this.lastNode = lastNode
  this.append = append
}
function append(element) {
  var lastnode = this.lastNode()
  var newNode = new Node(element)
  lastnode.next = newNode
  newNode.previous = lastnode
}
function lastNode() {
  var head = this.head
  while (head.next != null) {
    head = head.next
  }
  return head
}
var list = new initlist()
list.insert('two', 'one')
list.insert('four', 'two')
list.insert('three', 'two')

// console.log(list.head.next)
list.showlist()
list.append('A')
list.append('B')
list.insert('B2', 'B')
list.showlist()
console.log(list.lastNode())
// list.remove('one')
// list.showlist()
console.log(list.find('A').previous)
// console.log(list.find('four').previous)
// console.log(list.head.element)

← JS 中 AMD、CMD、CommonJS、ES6 Module 的区别 JS 类型隐式转换 →

# 源码：

源码：