05 (1)| javascript实现单链表

在了解链表的基本结构和相关操作的原理，我们可以使用Javascript来实现链表以及其相关的增删该查工作了。

    下面的代码中，我们首先需要定义两个类，Node类：表示单链表中的节点类。LinkedList类中实现了对链表的相关操作。

一、创建链表节点Node类：

function Node(element) {
  this.element = element; //当前节点的数据
  this.next = null; //下一个节点数据
}

一、创建链表操作方法LinkedList类：

首先，我们来一张单链表的图形，后续的操作，我们将通过这张图来进行分析。

image.png

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

1、查找节点

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

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

image.png

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

3、查找某一节点的前一个节点

  findPrevious: function (item) {
    var currNode = this.head;
    while (!(currNode.next == null) && currNode.next.element != item) {
      currNode = currNode.next;
    }
    return currNode;
  },

4、删除某一节点

image.png

  remove: function (item) {
    var prevNode = this.findPrevious(item);
    if (!(prevNode.next == null)) {
      prevNode.next = prevNode.next.next;
    }
  },

5、修改某一节点数据

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

6、在控制台打印所有的节点

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

7、完整的代码

function Node(element) {
  this.element = element; //当前节点的数据
  this.next = null; //下一个节点数据
}

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

LinkedList.prototype = {
  //查找节点
  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;
  },
  //查找某一节点的前一个节点
  findPrevious: function (item) {
    var currNode = this.head;
    while (!(currNode.next == null) && currNode.next.element != item) {
      currNode = currNode.next;
    }
    return currNode;
  },
  // 删除某一节点
  remove: function (item) {
    var prevNode = this.findPrevious(item);
    if (!(prevNode.next == null)) {
      prevNode.next = prevNode.next.next;
    }
  },
  // 修改某一节点数据
  edit: function (item, newItem) {
    var element = this.find(item);
    element.element = newItem;
  },
  // 在控制台打印所有的节点
  display: function () {
    var currNode = this.head;
    while (!(currNode.next == null)) {
      console.log(currNode.element);
      currNode = currNode.next;
    }
    console.log(currNode.element);
  },
};

三、测试代码

//测试
var names = new LinkedList();
names.insert("likek", "head");
names.insert("zhangsan", "likek");
names.insert("lisi", "zhangsan");
names.display();
console.log("------------");
names.remove("zhangsan");
names.display();
console.log("------------");
names.edit("lisi", "antiai");
names.display();

其实理解了链表的结构，我们再对照这链表的结构图，就可以比较直观写出大链表相关的实现逻辑了。