海同科技，欢迎您！
就业
学习
资料
职坐标
IT知识库

WEB前端

站
热门城市 全国站>
    其他省市
      搜索
      快速购买 快速购买  >
      icon 15692118659

      热门课程

      IT学院

      职坐标首页 IT知识库 WEB前端 JavaScript
      选择在海同提升： 30 天 1735 名， 今日申请 25 人 IT技术咨询 >>
      JavaScript数据结构教程(2)：链表
      沉沙 2018-07-23 来源 ： 阅读 1574 评论 0

      摘要：本篇JavaScript教程探讨了链表的相关内容，希望阅读本篇文章以后大家有所收获，帮助大家对JavaScript的理解更加深入。

      相比数组我们今天主角——链表就要来的随性多，简单的理解可以是这样：在内存中，栈和队列（数组）的存在就是一个整体，如果想要对她内部某一个元素进行移除或是添加一个新元素，就要动她内部所有的元素，所谓牵一发而动全身；而链表则不一样，每一个元素都是由元素本身数据和指向下一个元素的指针构成，所以添加或是移除某一个元素不需要对链表整体进行操作，只需要改变相关元素的指针指向就可以了。

      链表在实际生活中的例子也有很多，比如自行车的链条，环环相扣，但添加或是移除某一个环节只需要对症下药，对相关环节进行操作就OK。再比如：火车，火车就是一个链表，每一节车厢就是元素，想要移除或是添加某一节车厢，只需要把连接车厢的链条改变一下就好了。那么，在 JS 中又该怎么去实现链表结构呢？

      链表的创建

      首先我们要创建一个链表类：

      function LinkedList(){

          //各种属性和方法的声明

      }

         

      然后我们需要一种数据结构来保存链表里面的数据：

      var Node=function(element){

          this.element=element;

          this.next=null;

      }

      //Node类表示要添加的元素，他有两个属性，一个是element，表示添加到链表中的具体的值；另一个是next,表示要指向链表中下一个元素的指针。

         

      接下来，我们需要给链表声明一些方法：

      · append(element):向链表尾部添加一个新的元素；

      · insert(position,element):向链表特定位置插入元素；

      · remove(element):从链表移除一项；

      · indexOf(element):返回链表中某元素的索引，如果没有返回-1；

      · removeAt(position):从特定位置移除一项；

      · isEmpty():判断链表是否为空，如果为空返回true,否则返回false;

      · size():返回链表包含的元素个数；

      · toString():重写继承自Object类的toString()方法，因为我们使用了Node类；

      链表的完整代码：

      function LinkedList() {
    //Node类声明
    let Node = function(element){
        this.element = element;
        this.next = null;
    };
    //初始化链表长度
    let length = 0;
    //初始化第一个元素
    let head = null;
    this.append = function(element){
        //初始化添加的Node实例
        let node = new Node(element),
            current;
        if (head === null){
            //第一个Node实例进入链表，之后在这个LinkedList实例中head就不再是null了
            head = node;
        } else {
            current = head;
            //循环链表知道找到最后一项，循环结束current指向链表最后一项元素
            while(current.next){
                current = current.next;
            }
            //找到最后一项元素后，将他的next属性指向新元素node,j建立链接
            current.next = node;
        }
        //更新链表长度
        length++;
    };
    this.insert = function(position, element){
        //检查是否越界，超过链表长度或是小于0肯定不符合逻辑的
        if (position >= 0 && position <= length){
            let node = new Node(element),
                current = head,
                previous,
                index = 0;
            if (position === 0){
                //在第一个位置添加
                node.next = current;
                head = node;
            } else {
                //循环链表，找到正确位置，循环完毕，previous，current分别是被添加元素的前一个和后一个元素
                while (index++ < position){
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
            }
            //更新链表长度
            length++;
            return true;
        } else {
            return false;
        }
    };
    this.removeAt = function(position){
        //检查是否越界，超过链表长度或是小于0肯定不符合逻辑的
        if (position > -1 && position < length){
            let current = head,
                previous,
                index = 0;
            //移除第一个元素
            if (position === 0){
                //移除第一项，相当于head=null;
                head = current.next;
            } else {
                //循环链表，找到正确位置，循环完毕，previous，current分别是被添加元素的前一个和后一个元素
                while (index++ < position){
                    previous = current;
                    current = current.next;
                }
                //链接previous和current的下一个元素，也就是把current移除了
                previous.next = current.next;
            }
            length--;
            return current.element;
        } else {
            return null;
        }
    };
    this.indexOf = function(element){
        let current = head,
            index = 0;
        //循环链表找到元素位置
        while (current) {
            if (element === current.element) {
                return index;
            }
            index++;
            current = current.next;
        }
        return -1;
    };
    this.remove = function(element){
        //调用已经声明过的indexOf和removeAt方法
        let index = this.indexOf(element);
        return this.removeAt(index);
    };
    this.isEmpty = function() {
        return length === 0;
    };
    this.size = function() {
        return length;
    };
    this.getHead = function(){
        return head;
    };
    this.toString = function(){
        let current = head,
            string = '';
        while (current) {
            string += current.element + (current.next ? ', ' : '');
            current = current.next;
        }
        return string;
    };
    this.print = function(){
        console.log(this.toString());
    };
}
//一个实例化后的链表，里面是添加的数个Node类的实例

         

      ES6版本:

      let LinkedList2 = (function () {
    class Node {
        constructor(element){
            this.element = element;
            this.next = null;
        }
    }
    //这里我们使用WeakMap对象来记录长度状态
    const length = new WeakMap();
    const head = new WeakMap();
    class LinkedList2 {
        constructor () {
            length.set(this, 0);
            head.set(this, null);
        }
        append(element) {
            let node = new Node(element),
                current;
            if (this.getHead() === null) {
                head.set(this, node);
            } else {
                current = this.getHead();
                while (current.next) {
                    current = current.next;
                }
                current.next = node;
            }
            let l = this.size();
            l++;
            length.set(this, l);
        }
        insert(position, element) {
            if (position >= 0 && position <= this.size()) {
 
                let node = new Node(element),
                    current = this.getHead(),
                    previous,
                    index = 0;
                if (position === 0) {
                    node.next = current;
                    head.set(this, node);
                } else {
                    while (index++ < position) {
                        previous = current;
                        current = current.next;
                    }
                    node.next = current;
                    previous.next = node;
                }
                let l = this.size();
                l++;
                length.set(this, l);
                return true;
            } else {
                return false;
            }
        }
        removeAt(position) {
            if (position > -1 && position < this.size()) {
                let current = this.getHead(),
                    previous,
                    index = 0;
                if (position === 0) {
                    head.set(this, current.next);
                } else {
                    while (index++ < position) {
                        previous = current;
                        current = current.next;
                    }
                    previous.next = current.next;
                }
                let l = this.size();
                l--;
                length.set(this, l);
                return current.element;
            } else {
                return null;
            }
        }
        remove(element) {
            let index = this.indexOf(element);
            return this.removeAt(index);
        }
        indexOf(element) {
            let current = this.getHead(),
                index = 0;
            while (current) {
                if (element === current.element) {
                    return index;
                }
                index++;
                current = current.next;
            }
            return -1;
        }
        isEmpty() {
            return this.size() === 0;
        }
        size() {
            return length.get(this);
        }
        getHead() {
            return head.get(this);
        }
        toString() {
            let current = this.getHead(),
                string = '';
            while (current) {
                string += current.element + (current.next ? ', ' : '');
                current = current.next;
            }
            return string;
 
        }
        print() {
            console.log(this.toString());
        }
    }
    return LinkedList2;
})();

         

      双向链表

      function DoublyLinkedList() {
    let Node = function(element){
        this.element = element;
        this.next = null;
        this.prev = null; //NEW
    };
    let length = 0;
    let head = null;
    let tail = null; //NEW
    this.append = function(element){
        let node = new Node(element),
            current;
        if (head === null){
            head = node;
            tail = node; //NEW
        } else {
            //NEW
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
        length++;
    };
    this.insert = function(position, element){
        if (position >= 0 && position <= length){
            let node = new Node(element),
                current = head,
                previous,
                index = 0;
            if (position === 0){
                if (!head){       //NEW
                    head = node;
                    tail = node;
                } else {
                    node.next = current;
                    current.prev = node; //NEW
                    head = node;
                }
            } else  if (position === length) { ////NEW
                current = tail;  
                current.next = node;
                node.prev = current;
                tail = node;
            } else {
                while (index++ < position){
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
                current.prev = node; //NEW
                node.prev = previous; //NEW
            }
            length++;
            return true;
        } else {
            return false;
        }
    };
    this.removeAt = function(position){
        if (position > -1 && position < length){
            let current = head,
                previous,
                index = 0;
            if (position === 0){ //NEW
                if (length === 1){ //
                    tail = null;
                } else {
                    head.prev = null;
                }
            } else if (position === length-1){  //NEW
                current = tail;
                tail = current.prev;
                tail.next = null;
            } else {
                while (index++ < position){
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
                current.next.prev = previous; //NEW
            }
            length--;
            return current.element;
        } else {
            return null;
        }
    };
    this.remove = function(element){
        let index = this.indexOf(element);
        return this.removeAt(index);
    };
    this.indexOf = function(element){
        let current = head,
            index = -1;
        if (element == current.element){
            return 0;
        }
        index++;
        while(current.next){
            if (element == current.element){
                return index;
            }
            current = current.next;
            index++;
        }
        //check last item
        if (element == current.element){
            return index;
        }
        return -1;
    };
    this.isEmpty = function() {
        return length === 0;
    };
    this. size = function() {
        return length;
    };
    this.toString = function(){
        let current = head,
            s = current ? current.element : '';
        while(current && current.next){
            current = current.next;
            s += ', ' + current.element;
        }
        return s;
    };
    this.inverseToString = function() {
        let current = tail,
            s = current ? current.element : '';
        while(current && current.prev){
            current = current.prev;
            s += ', ' + current.element;
        }
        return s;
    };
    this.print = function(){
        console.log(this.toString());
    };
    this.printInverse = function(){
        console.log(this.inverseToString());
    };
    this.getHead = function(){
        return head;
    };
    this.getTail = function(){
        return tail;
    }
}

         

      双向链表和单项比起来就是Node类多了一个prev属性，也就是每一个node不仅仅有一个指向它后面元素的指针也有一个指向它前面的指针。

      循环链表

      明白了前面的基础链表和双向链表之后这个肯定不在话下了，循环，其实就是整个链表实例变成了一个圈，在单项链表中最后一个元素的next属性为null,现在让它指向第一个元素也就是head，那么他就成了单向循环链表。在双向链表中最后一个元素的next属性为null,现在让它指向第一个元素也就是head，那么他就成了双向循环链表。就那么回事…


      本文由职坐标整理发布，学习更多的JavaScript相关知识，请关注职坐标WEB前端JavaScript频道！

      javascript视频教程 javascript代码 javascript编程艺术
      本文由 @沉沙 发布于职坐标。未经许可，禁止转载。
      喜欢 | 0 不喜欢 | 0
      看完这篇文章有何感觉？已经有0人表态，0%的人喜欢 快给朋友分享吧~
      评论（0）
      后参与评论
      加入IT交流圈
      JAVA工程师交流群 +加入
      大数据架构师交流群 +加入
      人工智能Python交流群 +加入
      WEB/H5前端交流群 +加入
      职坐标公众号
      WEB前端 直通车
      • 资料领取 资料领取 资料领取
      • 答疑解惑 答疑解惑 答疑解惑
      • 技术交流 技术交流 技术交流
      • 职业测评 职业测评 职业测评
      • 面试技巧 面试技巧 面试技巧
      • 高薪秘笈 高薪秘笈 高薪秘笈
      海同专业团队 更多>>
      黄骈 联系TA
      认证System Analyst，System Architect
      张浩 联系TA
      15年全栈技术研发经验，中南大学、湖南师大等10+所高校特聘讲师
      热门就业技能 更多>>
      【零基础】人工智能+Python全栈开发技术
      【零基础】人工智能+Python全栈开发技术
      人工智能+Python技术风口浪潮
      【零基础】JavaEE高级开发技术
      【零基础】JavaEE高级开发技术
      起薪高，轻松进名企
      【零基础】大数据与分布式架构技术
      【零基础】大数据与分布式架构技术
      培训大数据分布式架构
      JavaScript30天热搜词 更多>>
      javascript怎么解决 javascript案例下载 javascript基础知识 javascript基础 javascript教程网 javascript代码 javascript基础代码 javascript视频教程 javascript基础教程第9版 javascript基础教程第8版代码 javascript编程艺术 javaweb前端技术 JavaScript知乎 javascript小案例 怎么开启javascript javascript高级程序 javascript函数大全 javascript异步编程 第一个javascript程序 手机javascript开启

      您输入的评论内容中包含违禁敏感词

      我知道了

      助您圆梦职场 匹配合适岗位
      验证码手机号，获得海同独家IT培训资料
      选择就业方向：
      人工智能物联网
      大数据开发/分析
      人工智能Python
      Java全栈开发
      WEB前端+H5

      请输入正确的手机号码

      请输入正确的验证码

      获取验证码

      您今天的短信下发次数太多了，明天再试试吧！

      提交

      我们会在第一时间安排职业规划师联系您！

      您也可以联系我们的职业规划师咨询：

      小职老师的微信号：z_zhizuobiao
      小职老师的微信号：z_zhizuobiao

      版权所有 职坐标-一站式AI+学习就业服务平台 沪ICP备13042190号-4
      上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com，All Rights Reserved.
       沪公网安备 31011502005948号    

      关于我们 │ 法律声明 │ 联系我们

      ©2015 www.zhizuobiao.com All Rights Reserved