《javascript数据结构和算法》读书笔记（3）：链表

一粒小麦

发布于 2019-07-18 17:48:13

4330

发布于 2019-07-18 17:48:13

文章被收录于专栏：一Li小麦

第三讲链表

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

=> 链表分类

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

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

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

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

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

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

创建链表

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

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))

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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-04-10，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

node.js

本文分享自一Li小麦微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

node.js

登录后参与评论

0 条评论

热度