链表在js中的实现

发布时间:2019-06-06 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了链表在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;
    };
}

执行查找节点操作,可见如下输出:

链表在js中的实现

执行插入节点操作,可见:

链表在js中的实现

执行删除节点操作,可见:

链表在js中的实现

双向链表

在计算机科学中, 一个双向链表(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);

脚本宝典总结

以上是脚本宝典为你收集整理的链表在js中的实现全部内容,希望文章能够帮你解决链表在js中的实现所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。
标签: