【js4agls】数据结构JavaScript描述-链表篇

Xufc 发布于2019-08-19 18:14 / 1114人阅读

摘要：我们可以使用链表这种数据结构，来删除元素的时候而不必让后面的元素向前移动。一个节点的上一个节点称为它的前驱，下一个节点即指向的节点称为它的后继节点，在简单的单向链表中，第一个节点称为头节点它没有前驱节点，最后一个节点没有后继节点为。

之前我们用数组的方式来实现了队列，是否还记得在出队列后有这样一段代码：

for (i = 0; i < this.length - 1; i++) {
    this.dataStore[i] = this.dataStore[i + 1];
}

我们为了删除一个元素，导致了整个数组元素的前移，显然这是非常低效的！尤其是当元素很多时。我们可以使用链表这种数据结构，来删除元素的时候而不必让后面的元素向前移动。

一个节点的上一个节点称为它的前驱，下一个节点即next指向的节点称为它的后继节点，在简单的单向链表中，第一个节点称为头节点它没有前驱节点，最后一个节点没有后继节点(为NULL)。关于头节点head其实是可有可无的，但是一般都会加上这个数据为空的节点，保存当前链表信息，如果一个链表的头节点找不到了，那么将会导致整个链表的丢失。

ADT

我们来看抽象数据类型的结构：

Node，单个节点
- element，节点数据
- next，下一个节点的指针

LinkList，链表的信息与方法
- insert，插入节点
- find，查找一个节点
- remove，删除一个节点
- findPrevious，查找节点的前驱节点
- print，打印链表

JavaScript完整描述

function Node (element) {
    this.element = element;
    this.next = null;
}
function LinkList () {
    this.head = new Node("head");
}
LinkList.prototype = {
    constructor: LinkList,
    insert: function (target, element) {
        var newNode = new Node(target);
        var current = this.find(element);
        newNode.next = current.next;
        current.next = newNode;
        return this;
    },
    find: function (target) {
        var currentNode = this.head;
        while (currentNode.element !== target) {
            currentNode = currentNode.next;
        }
        return currentNode;
    },
    remove: function (element) {
        var preNode = this.findPrevious(element);
        if (preNode.next !== null) {
            preNode.next = preNode.next.next;
            return true;
        }
        return false;
    },
    findPrevious: function (element) {
        var current = this.head;
        while (current.next !== null && current.next.element !== element) {
            current = current.next;
        }
        return current;
    },
    print: function () {
        var current = this.head.next;
        var str = "";
        while (current) {
            str += current.element + "->";
            current = current.next;
        }
        console.log(str.substr(0, str.length-2));
    }
}

分析 插入节点

通过find方法找到要插入的节点位置target

创建新的节点

当前节点的next指向target的next

target.next指向新节点

在插入的最后我们返回了this是为了方便进行链式插入。

算了直接看图：

删除节点

找到要删除元素的前驱preNode

将preNode的下一个节点指向preNode的下一个节点(要删除的节点)的下一个节点

如果遍历整个链表都没找到要删除的节点将会返回最后一个节点，而最后一个节点的下一个节点是NULL，所以，这样的删除操作会失败，返回false

测试

var list = new LinkList();
list.insert("jiavan1", "head").insert("jiavan2", "jiavan1").insert("jiavan3", "jiavan2").insert("jiavan4", "jiavan3");
list.print(); // jiavan1->jiavan2->jiavan3->jiavan4
list.remove("jiavan2"); // true
list.print(); // jiavan1->jiavan3->jiavan4
list.remove("none"); // false

这只是最简单的一种链表，复杂点的还有双向链表，循环链表，我们将用另外的文章实现。

原文出处 https://github.com/Jiavan/jia... 觉得对你有帮助就给个star吧

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/79354.html

数据结构大总结（链表篇）

摘要：实际中更多是作为其他数据结构的子结构，如哈希桶图的邻接表等等。实际中使用的链表数据结构，都是带头双向循环链表。文章目录一.算法的时间复杂度和空间复杂度1.算法...

不知名网友 2021-11-29 10:50 评论0 收藏0
【js4agls】数据结构JavaScript描述-栈篇

摘要：列表项目栈是一种后进先出的数据结构，我们所能操作的都是栈顶元素，删除一个栈顶元素叫做出栈或者弹栈，添加一个元素叫做入栈或者压栈首先构建我们的抽象数据类型栈顶元素位置保存数据的数组压栈出栈查看栈顶元素清空栈栈的长度输出栈元素描述模拟输出列表项目栈是一种后进先出(LIFO)的数据结构，我们所能操作的都是栈顶元素，删除一个栈顶元素叫做出栈或者弹栈，添加一个元素叫做入栈或者压栈. show...

psychola 2019-08-19 18:13 评论0 收藏0
【js4agls】数据结构JavaScript描述-队列篇

摘要：队列是一种先进先出的数据结构，与栈不同的是，它操作的元素是在两端，而且进行的是不一样的操作。队列(Queue)是一种先进先出(First-In-First-Out, FIFO)的数据结构，与栈不同的是，它操作的元素是在两端，而且进行的是不一样的操作。向队列的队尾加入一个元素叫做入队列(enQueue)，向队列的队首删除一个元素叫做出队列(delQueue). showImg(http...

Anonymous1 2019-08-19 18:13 评论0 收藏0
数据结构与算法（链表） --javascript语言描述

从尾到头打印链表输入一个链表，从尾到头打印链表每个节点的值。思路：先将链表每个结点的值存入数组中，然后通过数组的reverse方法，即可从尾到头打印。 function ListNode(x){ this.val = x; this.next = null; } function printListFromTailToHead(head){ if(!head...

617035918 2019-08-26 11:44 评论0 收藏0
数据结构JavaScript描述（二）

摘要：在上一篇文章中，我们了解了队列和栈的描述，现在让我们来了解一下单链表和双向链表的实现。单链表和双向链表具有以下特点可动态分配空间，但不能随机访问。在上一篇文章中，我们了解了队列和栈的JavaScript描述，现在让我们来了解一下单链表和双向链表的实现。本文的代码并非所有都由本人所写，只是出于学习目的，在此分享出来，并加上一定的解释，便于大家学习。本系列文章的代码可在ht...

OldPanda 2019-08-21 18:20 评论0 收藏0