链表在JS中的实现

定义链表

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继，指向另一个节点的引用叫做链

单向链表

Node类

• element用来保存节点上的数据
• next用来保存指向下一个节点的链接

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

LinkedList类

function LList(){
    this.head = new Node("head");//该链表的头对象
    this.find = find;//查找节点
    this.insert = insert;//插入节点
    this.remove = remove;//删除节点
    this.display = display;//展示链表节点
}

• find
  该方法遍历链表，查找给定数据，如果找到数据，返回保存该数据的节点

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

• insert

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

• display

function display(){
    var currNode = this. head;
    while(!(currNode.next)==null){
        print(currNode.next.element);
        currNode = currNode.next;
    }
}

• findPrevious

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

• remove

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

双向链表

为Node类新增previous属性

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

• insert
  在原有基础上需要设置新节点的previous属性

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

• remove
  不需要再查找上一节点了

function remove(item){
    var currNode = this.find(item);
    if(!(currNode.next == null)){
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous;
        currNode.next = null;
        currNode.previous = null;
    }
}

• 新增findLast方法
  该方法用来查找最后的节点，便于以反序显示链表中元素这类任务

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

• dispReverse

function dispReverse(){
    var currNode = this.head;
    currNode = this.findLast();
    while(!(currNode.previous == null)){
        print(currNode.element);
        currNode = currNode.previous;
    }
}

循环列表

循环列表和单向列表相似，节点类型都是一样的。唯一区别是在创建循环链表是，让其头节点的next属性指向它本身

• 修改LList类的构造函数

function LList(){
    this.head = new Node("head");
    this.head.next = this.head;
    this.find = find;
    this.insert = insert;
    this.display = display;
    this.findPrevious = findPrevious;
    this.remove = remove;
}

• 修改display
  需要检查头节点，当循环到头节点时退出循环

function display(){
    var currNode = this.head;
    while(!(currNode.next == null)&&(currNode.next.element == "head")){
        print(currNode.next.element);
        currNdoe = currNode.next;
    }
}

整理自《数据结构与算法Javascript》