专栏首页一Li小麦《javascript数据结构和算法》读书笔记(3):链表

《javascript数据结构和算法》读书笔记(3):链表

第三讲 链表

储存多个元素,数组是最常用的。无论何种语言,都实现了数组。但是大多数语言中,数组的长度是固定的。数组修改操作的成本非常高。

=> 链表分类

  • 单向链表
  • 无头链表:首个节点始终存在数据域,
  • 有头链表:只有指针域,没有数据域
  • 双向链表
  • 循环链表

限于篇幅,此处只讨论单链表中的无头链表。

链表储存有序的元素集合,但不同于数组,链表元素的内存不是连续放置的。每个元素包括:

  • 元素本身
  • 指向下个元素的引用。

相对于传统的数组,链表的好处在于添加或移动元素时,无需修改其他元素。

现实中,定向越野就是一种链表。去指定的地点寻找下一个线索(指针)。寻找终点,意味着必须遍历中间所有节点。另外还有猴子捞月。

创建链表

创建链表需要明确更多的规则。

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

        this.length=0;//链表的长度
        this.head=null;//链表的头部
    }

    // ..
}

一个单链表中,一个元素Node包括以下信息:

  • element:元素本身
  • next:地址指针,索引值
//调用时:
var Node=this.Node;
var node=new Node();

在这里声明一个内部的类 Node

创建一个链表,需要满足以下功能:

  • append:在链表尾部追加,如果链表为空(head为0,赋值node给head,否则,根据索引值next找到最后一项)

如果是空链表

非空链表

// 追加元素
    append(element){
        let Node=this.Node;
        let node=new Node(element);
        let current=null;
        if(this.head==null){
            this.head=node;
        }else{
            // 指针从头部开始,一直根据索引值遍历
            current=this.head;
            while (current.next) {
                current=current.next;
            }
            // 赋值
            current.next=node;
        }
        this.length++;
    }
  • insert:在链表指定位置添加

如果是空链表

如果是非空链表

//任意位置插入元素
    insert(position,element){
        if(position>-1&&position<this.length){
            let Node=this.Node;
            let node=new Node(element);
            let current=this.head;
            let previous=null;
            let index=0;
            // 第一个位置添加
            if(position==0){
                node.next=this.head;
                this.head=node;
            }else{
                while (index++<position) {
                    previous=current
                    current=current.next;
                }
                node.next=current;
                previous.next=node;
            }
            this.length++;
            return true
        }else{
            return false
        }
    }
  • removeAt:在指定位置删除一项。同样也要区分移除头部和头部以外位置的情况。

非空链表:

空链表

// 移除
    removeAt(position){
        // 当位置在链表索引范围内,移除方能成立
        if(position>-1&&position<this.length){
            // 需要两个节点,方能实现操作
            let current=this.head;
            let previous=null;
            let index=0;
            if(position==0){
                // 移除第一项,把头部之后的节点赋值给头部。即可!
                this.head=current.next;
            }else{
                // 定位元素位置不断递进,直至找到position时终止。
                while (index++<position) {
                    previous=current
                    current=current.next;
                }
                // 将previous和current的下一项链接起来,跳过current,从而实现移除。
                previous.next=current.next;
            }

            this.length--;
            return current.element;
        }
    }
  • indexOf:返回元素在链表中的第一个索引
// 返回元素在链表中的位置,-1为找不到
    indexOf(element){
        let current=this.head;
        let index=0;//应从0开始,原书有误。
        while (current) {
            if(element==current.element){
                return index
            }
            index++;
            current=current.next;
        }
        return -1
    }
  • remove:删除该元素。实现了indexOf这个很简单了
//根据元素删除元素
    remove(element){
        let index=this.indexOf(element);
        return this.removeAt(index);
    }
  • isEmpty:若链表不含任何元素,返回true
// 返回长度
    size(){
        return this.length==0;
    }
  • size:返回链表元素的个数。
// 返回长度
    size(){
        return this.length;
    }
  • toString:输出链表的元素值(node的element值)
//吧linkList转换为一个字符串
    toString(){
        let current=this.head;
        let string='';

        while (current) {
            string+=current.element+(current.next?'->':'');
            current=current.next;
        }

        return string;
    }
  • getHead 获取头部
// 获取头部
    getHead(){
        return this.head;
    }
  • getTail 获取尾节点
// 获取尾节点
    getTail(){
        let current=this.head;
        while (current.next) {
            current=current.next;
        }
        return current.element;
    }

那么,来测试一下吧。

// 测试用例
let a=new LinkList();
a.append('djtao')
a.append('djt')
a.append('taotao')
console.log(a.toString())
a.insert(1,'dangjingtao')
console.log(a.toString())
a.removeAt(2)
console.log(a.toString())
a.remove('dangjingtao')
console.log(a.indexOf('taotao'))
console.log(a.toString())

输出结果

基于链表实现stack和queue

之前的栈和队列,都是基于数组实现的。

stack

这个还是比较简单的:

// 用链表实现stack
class Stack{
    constructor(){
        this.linkList=new LinkList();
    }

    push(item){
        this.linkList.append(item);
    }

    pop(){
        let size=this.linkList.size();
        return this.linkList.removeAt(size-1)
    }

    top(){
        return this.linkList.getTail();
    }

    print(){
        console.log(this.linkList.toString());
    }

    size(){
        return this.linkList.size();
    }

    isEmpty(){
        return this.linkList.size()==0;
    }
}
// 测试用例
var a=new Stack();
a.push('djt')
a.push('djtao')
a.push('dangjingtao')
a.print()
a.pop();
a.print();
a.pop();
a.print()
a.pop();
a.print()
a.pop();
a.print()
console.log(a.isEmpty())

queue

// 基于链表实现queue
class Queue{
    constructor(){
        this.linkList=new LinkList();
    }

    enQueue(item){
        this.linkList.append(item)
    }

    deQueue(){
        this.linkList.removeAt(0)
    }

    // 。。。
}

链表翻转

如果一个人号称”精通数据结构“,那大概意思是能做以下这些题。

在上下文环境中,使用递归 recursion和迭代 iteration两种方式实现函数

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


var node1=new Node(1);
var node2=new Node(2);
var node3=new Node(3);
var node4=new Node(4);
var node5=new Node(5);

node1.next=node2;
node2.next=node3;
node3.next=node4;
node4.next=node5;

function print(node){
    var current=node;
    var str='';
    while (current) {
        str+=current.element.toString()+(current.next!==null?'->':'');
        current=current.next;
    }
    console.log(str)
}

递归

递归的思路是(甩锅):

  • 遇到尾部next为null,递归终止
  • 遇到头部,让它的next为空。
// 递归
var recursion=function(node,previous){  
    let next=node.next;

    // 尾部
    if(!next){
        node.next=previous;
        return node;
    }else{
        // 互换
        // 头部
        if(!previous){
            previous=node;
            node.next=null;   
        }else{
            node.next=previous;
        }
        return recursion(next,node)
    }
}

print(recursion(node1))//5->4->3->2->1

迭代

迭代的思路:

见注释

// 迭代
var iteration=function(node){
    let current=node;//当前要反转的节点
    let previous=null;//前一个节点,也用于储存返回值

    while (current) {
        let next=current.next;//获取下一个节点
        current.next=previous;//获取完之后把储存位置给previous
        previous=current;//previous叫出去之后,开始后滑
        current=next;//current后滑
    }

    return previous;
}

print(iteration(node1))

【小结】拿到前后节点,只考虑单个节点的情况。

本文分享自微信公众号 - 一Li小麦(gh_c88159ec1309),作者:一li小麦

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基于react的H5音频播放器

    项目是基于React,镶嵌在页面。为此开发了组件audio.js。不过不管什么框架。逻辑都是一样的。

    一粒小麦
  • 组件设计基础(2)

    早期的react设计了许多的生命周期钩子。它们严格定义了组件的生命周期,一般说,生命周期可能会经历如下三个过程:

    一粒小麦
  • 手撸vuex和vue-router

    把这个store返回出去,那就写完了,核心原理可以说是异常简单。 就用官方文档的案例验证下这个duex有多靠谱:

    一粒小麦
  • 重读《学习JavaScript数据结构与算法-第三版》- 第6章 链表(一)

    本章为重读《学习JavaScript数据结构与算法》的系列文章,该章节主要讲述数据结构-链表,以及实现链表的过程和原理。

    胡哥有话说
  • 数据结构知否知否系列之 — 线性表的顺序与链式存储篇(8000 多字长文)

    线性表是由 n 个数据元素组成的有限序列,也是最基本、最简单、最常用的一种数据结构。

    五月君
  • javascript探秘之从零到一实现单向 & 双向链表

    前端工程师对于算法和数据结构这块的知识的掌握程度,是进阶高级工程师的非常重要的标志之一,为了总结一下数据结构和算法方面的知识,笔者今天继续把链表这一块的知识补上...

    徐小夕
  • 《剑指offer》分解让复杂问题更简单

    输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中...

    ConardLi
  • 165. 合并两个排序链表双指针

    将两个排序链表合并为一个新的排序链表. 样例 给出 1->3->8->11->15->null,2->null, 返回 1->2->3->8->11->15...

    和蔼的zhxing
  • Leetcode:148_Sort List | O(nlogn)链表排序 | Medium

    题目:Sort List Sort a linked list in O(n log n) time using constant space complexi...

    CloudDeveloper
  • 你可能不知道的7个深度学习实用技巧

    【导读】前几天,深度学习工程师George Seif发表了一篇博文,总结了7个深度学习的技巧,主要从提高深度学习模型的准确性和速度两个角度来分析这些小技巧。在使...

    WZEARW

扫码关注云+社区

领取腾讯云代金券