JavaScript -- 链表的JavaScript描述

深碍√TFBOYSˉ_ 2022-04-17 00:50 164阅读 0赞

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

看下图：

![20181110192522308.png][]

header节点不存数据，我每一次就从头开始遍历节点，拿到头就拿到整条链表。

我们可以定义个数据结构用来表示每一个节点。

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

下面介绍增删查三种操作。

增操作：（规定我们每一次在链表尾部添加数据）

this.insert = function (data) {
             let newNode = new Node(data);//新生成一个节点
             let cur = this.head ;
             while (cur.next != null) {//找链表尾
                 cur = cur.next;
             };
             cur.next = newNode;//连起来
        }

删操作：（给定我们一个数据，如果数据在链表中出现，那么删除第一次出现的时候）

![20181110193208226.png][]

this.remove = function (data) {
            let cur = this.head;
            while (cur.next != null) {
                let pre = cur;//因为需要删除cur.next节点，那么cur肯定需要保存，可以看图明白为啥
                cur = cur.next;
                if (cur.element == data) {
                    pre.next = cur.next;//关键
                    break;
                }
            };
        }

如果你需要删除所有的相关值，那么你只需要一个循环即可。

查操作：

this.find = function (data) {
            let cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
                if (cur.element == data ) return true;
            }
            return false;
        }

结合删除操作可以删除所有相关值。

const Node = function (element) {
        this.element = element;
        this.next = null;
    }
    const List = function () {
        this.head = new Node("#head#");
        this.insert = function (data) {
             let newNode = new Node(data);
             let cur = this.head ;
             while (cur.next != null) {
                 cur = cur.next;
             };
             cur.next = newNode;
        }
        this.remove = function (data) {
            let cur = this.head;
            while (cur.next != null) {
                let pre = cur;
                cur = cur.next;
                if (cur.element == data) {
                    pre.next = cur.next;
                    break;
                }
            };
        }
        this.find = function (data) {
            let cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
                if (cur.element == data ) return true;
            }
            return false;
        }
        this.reverse = function () {//反转
            let cur = this.head.next;
            let per = null;
            if (cur == null) return true;
            while (cur.next != null) {
                const p = cur;
                cur = cur.next;
                p.next = per;
                per = p;
            }
            cur.next = per;
            this.head.next = cur;
        }
        this.deleteBackNth = function (n) {//删除链表倒数第 n 个结点
            let fast = this.head;
            let slow = this.head;
            let per = null;
            for (let i = 0; i < n; i++) {
                if (fast.next != null) fast = fast.next;
                else return false;
            }
            while (fast.next != null) {
                per = slow;
                slow = slow.next;
                fast = fast.next;
            }
            if (per == null) {
                const first = this.head.next;
                this.head.next = first.next;
                first.next = null;
            } else {
                per = slow;
                slow = slow.next;
                per.next = slow.next;
                slow.next = null;
            }
        }
        this.isCircle = function () {//是否有环
            let fast = this.head;
            let slow = this.slow;
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) return true;
            }
            return false;
        }
        this.show = function () {
            let cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
                console.log(cur.element);
            }
        }
        
    }

看一下验证代码：

let app = new List();
     
    app.insert(5);
    app.insert(6);
    app.insert(6);
    app.insert(9);
    app.insert(9);
    
    app.remove(6);
     
    app.show();
    
    while (app.find(9)) {
        app.remove(9);
    }
    app.show();

![2018111019462731.png][]

5 6 9 9因为删除了一个6

5 6 因为删除了所有的9

[20181110192522308.png]: /images/20220417/a4c5520ea620402b88fadb36153d7dd3.png
[20181110193208226.png]: /images/20220417/fdcba63fedd3488996a49690d7c22813.png
[2018111019462731.png]: /images/20220417/98191c903b4d4501b424688218a8c814.png

发表评论取消回复

表情：

评论列表（有 0 条评论，164人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构与算法Javascript描述（五）循环链表

循环链表和单向链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让其头节点的next属性指向它本身，即 head.next = head; 如果你希望可以从后向前

我就是我/ 2022年08月21日 02:14/ 0 赞/ 125 阅读

相关数据结构与算法Javascript描述（四）双向链表

尽管从链表的头节点遍历到尾节点很简单，但反过来，从后向前遍历则没那么简单。通过给Node 对象增加一个属性，该属性存储指向前驱节点的链接，这样就容易多了。此时向链表插入一个节点

一时失言乱红尘/ 2022年08月21日 02:13/ 0 赞/ 153 阅读

相关数据结构与算法Javascript描述（三）链表

数组不总是组织数据的最佳数据结构，因为数组的长度是固定的，所以当数组已被数据填满时，要再加入新的元素就会非常困难。在数组中，添加和删除元素也很麻烦，因为需要将数组中的其他元素向

清疚/ 2022年08月21日 02:13/ 0 赞/ 179 阅读

相关 JavaScript单链表

function Linkedlist(){ var Node = function(element){

骑猪看日落/ 2022年06月01日 23:51/ 0 赞/ 124 阅读

相关列表 Javascript描述

列表在日常生活中，人们经常使用列表：待办事项列表、购物清单、十佳榜单、最后十名榜单等。当需要保存的元素不是太多，不需要在一个很长的序列中查找元素，或者对其进行排序时，就适合

谁借莪１个温暖的怀抱￠/ 2022年05月25日 00:18/ 0 赞/ 141 阅读

相关反转链表JavaScript

反转一个单链表。题目详细描述：[https://leetcode-cn.com/problems/reverse-linked-list/description/][https

- 日理万妓/ 2022年05月19日 08:20/ 0 赞/ 110 阅读

相关【JavaScript】用JavaScript实现一个链表

append(element) ：向列表尾部添加一个新的项。 insert(position, element) ：向列表的特定位置插入一个新的项。 indexOf(e

我就是我/ 2022年05月10日 14:46/ 0 赞/ 194 阅读

相关 JavaScript -- 二叉查找树的JavaScript的描述

我首先看一下什么是树。树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构，以分层的方式存储数据。树被用来存储具有层级关系的数据，比如文件系统中的文件； ![

谁借莪１个温暖的怀抱￠/ 2022年04月17日 01:50/ 0 赞/ 112 阅读

相关 JavaScript -- 双链表的JavaScript描述

尽管从链表的头节点遍历到尾节点很简单，但反过来，从后向前遍历则没那么简单。通过给 Node 对象增加一个属性，该属性存储指向前驱节点的链接，这样就容易多了。此时向链表插入一个节

淡淡的烟草味﹌/ 2022年04月17日 00:55/ 0 赞/ 144 阅读

相关 JavaScript -- 链表的JavaScript描述

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。看下图： ![20181110192522308.png][] hea

深碍√TFBOYSˉ_/ 2022年04月17日 00:50/ 0 赞/ 165 阅读