js实现链表_javascript中的链表结构

时间: 2018-11-28阅读: 1522标签: 算法

1.定义

很多编程语言中数组的长度是固定的,就是定义数组的时候需要定义数组的长度,所以当数组已经被数据填满的时候,需要再加入新的元素就很困难。只能说在部分变成语言中会有这种情况,在JavaScript中和php中数组的长度是可以任意增加的。在数组中添加和删除元素也是比较麻烦,因为要将数组中其他元素向前或者向后平移,这个在JavaScript中也不是问题,javascript中有一个很方便的方法splice()方法很方便的就可以添加或删除元素。

但是凡是都是相对的,javascript中的数组也有自己的问题,他们被是成了对象,与其他语言(比如c++和java)相比它的效率很低。

如果在实际的使用中发现数组的效率很慢,就可以考虑使用链表来代替。数组还有个优势是可以根据键值很方便的访问数组的值,除此之外,链表在任何场合都可以代替数组。如果需要随机地访问元素,数组仍然是更好的选择。

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

数组元素靠它们的位置进行引用,链表元素则是靠相互之间的关系进行引用。在数组中会说这个元素是数组中的第几个元素,但是在链表中就说这个元素是某个元素的后面一个元素。遍历链表就是跟着链表从链表的头元素(head)一直走到尾元素(但是不包含链表的头借点,头通常用来作为链表的接入点)。还有一个问题,链表的尾元素指向一个null节点。如下图


许多链表的实现都在链表前面有一个特殊的节点,叫做头节点。最后一个节点指向null,所有最后再加上一个null节点。如下图


在链表中插入一个节点的效率很高。向链表中插入一个节点,需要修改它前面的节点,使其指向新加入的节点,而新加入的节点则指向前面指向的节点。如下图展示的是在eggs后面加上cookies节点。如下图


从链表中删除一个节点也很简单,将待删除的元素的前驱节点指向待删除的后续节点,同时将待删除元素指向null来释放。下图是一个巧合删除是的null元素前面的一个元素。如下图



2.代码实现

在下面的链表实现中有两个类。node类用来标识节点,LinkedList类提供插入节点,删除节点,显示链表节点元素的方法,以及一些其他的辅助方法。

Node类包含两个属性,element用来保存节点上的数据,next用来保存指向下一个节点的链接。我们使用一个构造函数来创建节点,改构造函数设置了这两个属性的值。如下:

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

LinkedList类提供了对链表进行操作的方法,该类的功能包含插入节点,在链表中查找给定的节点。该类也有一个构造函数,链表只有一个属性,那就是使用一个node对象来保存该链表的头结点,代码如下:

function LList(){
    this.head = new Node('head');
    this.find = find;
    this.insert = insert;
    //this.remove = remove;
    this.display = display;
}

head节点的next属性被初始华为null,当有新元素插入时,next会指向新的元素。

插入节点的方法是insert,该方法向链表中插入新节点的时候,需要明确指出在那个节点的前面或者后面插入。这里先讨论在一个已知节点的后面插入元素。在元素后面插入元素的时候不,需要先找到“后面”的节点。为此创建一个辅助方法find(),该方法遍历链表,查找指定的数据,如果找到该数据,就返回保存该数据的节点,find()方法的实现的代码如下:

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

find()方法演示了如何在链表上移动。首先创建一个新节点,并将链表的头节点赋给这个新创建的节点。然后再链表上进行循环,如果当前节点的element属性和我们要找的信息不符合,就从当前节点移动到下一个节点。如果查找成功个,该方法返回包含该数据的节点,否则返回null。

一旦找到“后面”的节点,就可以将新节点插入链表了。首先,将新节点的next属性设置为“后面”节点对应的值,然后设置“后面”节点的next属性指向新的节点,insert()定义如下:

//插入一个元素
function insert(newElement, item){
    var newNode = new Node(newElement);
    var current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
}

最后,我们定义一个打印链表元素的方法,如下:

function display(){
    var currNode = this.head;
    while (!(currNode.next == null)){
        document.write(currNode.next.element + ' ');
        currNode = currNode.next;
    }
}

这个方法首先将链表的头赋给一个变量,然后循环遍历链表,当前节点的next属性为null的时候循环结束。为了只显示包含数据的节点,我们使用currNode.next.element表达式来访问节点中的数据。

最后我们用下面的代码来测试链表。在链表中保存几个美国城市"Conway","Russellville","Alma"并将他们打印出来,完整代码如下:

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

function LList(){
    this.head = new Node('head');
    this.find = find;
    this.insert = insert;
    //this.remove = remove;
    this.display = display;
}

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

//插入一个元素
function insert(newElement, item){
    var newNode = new Node(newElement);
    var current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
}

function display(){
    var currNode = this.head;
    while (!(currNode.next == null)){
        document.write(currNode.next.element + ' ');
        currNode = currNode.next;
    }
}


//测试程序
var cities = new LList();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.insert("Alma", "Russellville");
cities.display();


来源:https://www.cnblogs.com/tylerdonet/p/5880088.html


站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

链接: https://www.fly63.com/article/detial/1441

js实现:在字符串中找出第一个只出现一次的字符

在给出一个字符串,找出第一个只出现一次的字符。思路分析:可以用对象保存字符出现的次数。将值删除,用 indexOf 查找还有没有相同字符,并查找之前删过的字符,indexOf 的第二个参数,从当前值往后搜索,并查找之前已经查过的字符

indexOf实现引申出来的各种字符串匹配算法

我们在表单验证时,经常遇到字符串的包含问题,比如说邮件必须包含indexOf。我们现在说一下indexOf。这是es3.1引进的API ,与lastIndexOf是一套的。可以用于字符串与数组中。一些面试经常用问数组的indexOf是如何实现的

js算法-查找斐波纳契数列中第N个数

所谓的斐波纳契数列是指前2个数是 0 和 1 ,第 i 个数是第 i-1 个数和第i-2 个数的和。下面我们来用js获取菲波那契数列的第N个数为多少:递归、闭包+缓存、直接计算出该数列的值得数组,然后再从数组中取值 、直接使用数学表达式

原生js数值开根算法

理论上来讲,开根后的值为x,那么x^2=n,即可以将其转换为数学问题,令y=x^2-n,那么只需要求方程与x轴正方向的焦点就可以得出想要的结果,我们作x=a与方程交于(a^2-n),求得他的切线与x轴的交点

js算法_八皇后问题的JavaScript解法

关于八皇后问题的 JavaScript 解法,八皇后问题是一个以国际象棋为背景的问题,八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为 n×n ,而皇后个数也变成n 。当且仅当n = 1或n ≥ 4时问题有解

Js实现首字母大写

一小段字母文本可以手动输入进行字母大小写的改变,如果是一大段文本只好借助程序来实现,中字母大小写转换是基本功能。 返回一个字符串,确保字符串的每个单词首字母都大写,其余部分小写

js算法_奇偶分割数组

分割一个整数数组,使得奇数在前偶数在后。 比如:给定 [1, 2, 3, 4],返回 [1, 3, 2, 4]。思路分析:排序好的数组:找到奇数进行操作。乱序的数组:使用sort方法进行排序+提取奇数

为什么我认为数据结构与算法对前端开发很重要?

一个具有层级结构的数据,实现这个功能非常容易,因为这个结构和组件的结构是一致的,递归遍历就可以了。但是,由于后端通常采用的是关系型数据库,所以返回的数据通常会是这个样子:前端这边想要将数据转换一下其实也不难,因为要合并重复项

JS实现快速排序算法

快速排序的基本思想是选择数组中的一个元素作为关键字,通过一趟排序,把待排序的数组分成两个部分,其中左边的部分比所有关键字小,右边的部分比所有关键字大。然后再分别对左右两边的数据作此重复操作,直到所有元素都有序,就得到了一个完全有序的数组。

Js哈希摘要算法

最近在看一些NPM库的时候总是看到各种哈希签名算法,之前工作中也有用到过签名算法,但并没有深入理解过其中的原理,于是找了点资料稍微了解了一下,总结了这篇文章。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!