链表在js中的实现

摘要：最近在看数据结构与算法，但是一直搞不明白在代码中的实现。今天结合找到的一些资料总结一下链表在中的实现。这种结构允许在迭代期间有效地从序列中的任何位置插入或删除元素。

最近在看js数据结构与算法，但是一直搞不明白在代码中的实现。今天结合找到的一些资料总结一下链表在js中的实现。
首先说下链表，在计算机科学中, 一个链表是数据元素的线性集合, 元素的线性顺序不是由它们在内存中的物理位置给出的。相反，每个元素指向下一个元素。它是由一组节点组成的数据结构,这些节点一起表示序列。在最简单的形式下，每个节点由数据和到序列中下一个节点的引用(换句话说，链接)组成。这种结构允许在迭代期间有效地从序列中的任何位置插入或删除元素。关于链表更多的说明请参考链接描述

大致了解了链表的概念之后我们就看下链表在js代码中的实现：

单向链表

//这里element存放的是该节点上的数据，next存放的是指向下一个节点的链接
function Node(element){
    this.element = element;
    this.next = null;
}
//接下来构建一个List类
function List(node){
    this.node = new Node(node);
    //查找节点
    this.find = function(target){
        var current = this.node;
        while(current.element != target){
            current = current.next;
            if(!current){
                return false;
            }
        }
        return current;
    };
    //插入节点
    this.insert = function(newNode, target){
        var newnode = new Node(newNode);
        var current = this.find(target);
        newnode.next = current.next;
        current.next = newnode;
    };
    //查找前一个节点
    this.findPre = function(item){
        var current = this.node;
        while(!current.next && current.next.element != item){
            current = current.next; 
        }
        return current;
    };
    //删除节点
    this.delete = function(target){
        var deltarget = this.find(target); 
        this.findPre(deltarget).next = deltarget.next;
    };
}

执行查找节点操作，可见如下输出：

执行插入节点操作，可见：

执行删除节点操作，可见：

双向链表

在计算机科学中, 一个双向链表(doubly linked list) 是由一组称为节点的顺序链接记录组成的链接数据结构。每个节点包含两个字段，称为链接，它们是对节点序列中上一个节点和下一个节点的引用。开始节点和结束节点的上一个链接和下一个链接分别指向某种终止节点，通常是前哨节点或null，以方便遍历列表。如果只有一个前哨节点，则列表通过前哨节点循环链接。它可以被概念化为两个由相同数据项组成的单链表，但顺序相反。

function Node(element){
    this.pre = null;
    this.element = element;
    this.next = null;
}
function List(node){
    this.node = new Node(node);
    this.find = function(target){
        var current = this.node;
        while(current.element != target){
            current = current.next;
            if(current == null){
                return false;
            }
        }
        return current;
    };
    this.insert = function(newNode, target){
        var target = this.find(target);
        var newNode = new Node(newNode);
        newNode.next = target.next;
        newNode.pre = target;
        target.next = newNode;
    };
    this.delete = function(delNode){
        var delNode = this.find(delNode);
        delNode.next.pre = delNode.pre;
        delNode.pre.next = delNode.next;
    };
}
var list = new List("a");
list.insert("b", "a");
list.insert("c", "b");
list.delete("b");
console.log(list);