05 (2)| javascript实现双向链表

上一个文章里我们已经了解到链表结构，链表的特点是长度不固定，不用担心插入新元素的时候新增位置的问题。插入一个元素的时候，只要找到插入点就可以了，不需要整体移动整个结构。

这里我们了解一下双向链表的结构。尽管从链表中头节点遍历到尾节点很容易，但是反过来，从后向前遍历就没有那么简单。通过给Node对象增加一个属性，该属性存储指向前驱节点的链接，这样就容易多了。此时祥链表中插入一个节点需要更多的工作，我们需要指出该节点正确的前驱和后续。但是在从链表中删除节点的时候效率更高了，不需要再查找待删除节点的前驱节点了。如下图1演示了双向链表的工作原理。

图1.png

首先是要为Node类增加一个previouse属性，这个属性指向当前节点的前驱：

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

双向链表的insert()方法和单项链表的类似，但是需要设置新节点的previouse属性，是其指向该节点的前驱。该方法的定义如下

function LinkedList() {
  this.head = new Node("head"); // 头节点
}
LinkedList.prototype = {
// some function
}

一、查找节点

  find: function (item) {
    var currNode = this.head;
    while (currNode.element != item) {
      currNode = currNode.next;
    }
    return currNode;
  }

二、向某一元素后面插入新节点

insert: function (newElement, item) {
    var newNode = new Node(newElement);
    var currNode = this.find(item);
    newNode.next = currNode.next;
    currNode.next = newNode;
  }

三、删除节点

双向链表的删除remove()方法币单项链表的效率更高，因为不需要查找前驱节点了。首选需要在链表中找出存储待删除数据的节点，然后设置该节点的next属性，使其指向待删除节点的后续。设置该节点的后续的previouse的属性，使其指向待删除节点的前驱。如下图展示删除节点的过程：

image.png

  remove(item) {
    var currNode = this.find(item);
    currNode.prev.next = currNode.next;
    currNode.next.prev = currNode.prev;
    currNode.next = null;
    currNode.prev = null;
  },

四、寻找最后一个节点

为了实现反向显示链表中元素的任务，需要给链表增加一个工具方法，用来查找链表中最后一个节点。findLast()方法找出链表中最后一个节点，同时免除从前往后遍历之苦。如下：

findLast() {
    var currNode = this.head;
    while (currNode.next != null) {
      currNode = currNode.next;
    }
    return currNode;
  }

五、寻找最后一个节点

dispReverse() {
    var currNode = this.findLast();
    while (currNode.prev != null) {
      console.log(currNode.element);
      currNode = currNode.prev;
    }
    console.log(currNode.element);
  },

六、正向显示链表元素

  // 
  display() {
    var currNode = this.head;
    while (currNode.next != null) {
      console.log(currNode.element);
      currNode = currNode.next;
    }
    console.log(currNode.element);
  }

七、修改链表元素

  edit(item, newItem) {
    var currNode = this.find(item);
    currNode.element = newItem
  }

八、完整的代码

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

function LikedList() {
  this.head = new Node("head");
}

LikedList.prototype = {
  // 查找一个节点
  find(item) {
    var currNode = this.head;
    while (currNode.element != item) {
      currNode = currNode.next;
    }
    return currNode;
  },

  // 插入节点
  insert(newElement, item) {
    var newNode = new Node(newElement);
    var currNode = this.find(item);
    newNode.next = currNode.next;
    newNode.prev = currNode;
    currNode.next = newNode;
  },
  // 修改链表元素
  edit(item, newItem) {
    var currNode = this.find(item);
    currNode.element = newItem;
  },
  // 删除节点
  remove(item) {
    var currNode = this.find(item);
    currNode.prev.next = currNode.next;
    currNode.next.prev = currNode.prev;
    currNode.next = null;
    currNode.prev = null;
  },
  //寻找最后一个节点
  findLast() {
    var currNode = this.head;
    while (currNode.next != null) {
      currNode = currNode.next;
    }
    return currNode;
  },
  // 正向显示链表元素
  display() {
    var currNode = this.head;
    while (currNode.next != null) {
      console.log(currNode.element);
      currNode = currNode.next;
    }
    console.log(currNode.element);
  },
  // 反向显示链表的元素
  dispReverse() {
    var currNode = this.findLast();
    while (currNode.prev != null) {
      console.log(currNode.element);
      currNode = currNode.prev;
    }
    console.log(currNode.element);
  },
};

测试用例

var cities = new LikedList();
console.log("-------链表新增元素------");
cities.insert("likek", "head");
cities.insert("zhangsan", "likek");
cities.display();
console.log("-------反向显示链表元素------");
cities.dispReverse();
console.log("-------寻找最后一个节点------");
console.log(cities.findLast());
console.log("-------删除节点------");
cities.remove("likek");
cities.display();
console.log("-------修改节点------");
cities.edit("zhangsan", "aiguo");
cities.display();