JS数据结构与算法-链表

  1. 定义 链表是由一组节点组成的集合。每个元素由一个存储元素本身的节点和一个指向下一个元素的应用(也称之为指针或链接)组成。

一个链表的结构 现实中的举例说明就是火车。每节车厢是链表的元素,车厢间的连接就是指针:

来自《学习javascript数据结构与算法》

  1. 创建一个链表
  • 定义一个LinkedList类和一个Node类
function LinkedList() {
  //定义一个Node类,element用来保存节点上的数据,next表示指向链表中下一个项的指针
  var Node = function(element) {
    this.element = element;
    this.next = null;
  }

  //用length表示列表的数量
  var length = 0;
  //head存储第一个节点的引用
  var head = null;
}
  • 实现append方法向列表尾部添加一个新的项 有两种情况:列表为空,添加的是第一个元素,列表不为空,向其追加元素。
this.append = function(element) {
    var node = new Node(element),
        current;
    if(head === null) {
      head = node;
    }else {
      current = head;
      //循环链表,直到找到最后一项
      while(current.next) {
        current = current.next;
      }
      //找到最后一项将其next赋为node,建立连接
      current.next = node;
    }
    //更新链表长度
    length++;
  };
  • 实现removeAt方法从链表的特定位置移除一项
  this.removeAt = function(position) {
    if(position > -1 && position < length) {
      var current = head,
          previous,
          index = 0;

      //移除第一项
      if(position === 0) {
        head = current.next;
      } else {
        //循环列表,找到position位置的元素和前一个元素
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        //将previous与current的下一项链接起来:跳过current,从而移除它
        previous.next = current.next;
      }
      length--;
      return current.element;
    }else {
      return null;
    }
  };
  • 实现insert方法向列表的特定位置插入一个新的项
  //向列表的特定位置插入一个新的项
  this.insert = function(position,element) {
    if(position >= 0 && position <= length) {
      var node = new Node(element),
          current = head,
          previous,
          index = 0;

      //如果要在0的位置插入新值,那么就要将head设为新值,并将它的下一个值设为当前值
      if(position === 0) {
        node.next = current;
        head = node;
      }else {
        //循环访问列表,找到目标位置,将目标位置上的元素用previou保存;将目标位置链接的下一个元素用current保存
        while(index++ <position) {
          previous = current;
          current = current.next;
        }
        //将新元素node的next属性设置为current
        //让previous.next指向新元素node
        node.next = current;
        previous.next = node;
      }
      length++; //更新列表长度

      return true;

    }else {
      return false;
    }
  };
  • 实现indexOf方法,返回元素在列表中的索引。如果列表没有该元素则返回-1
this.indexOf = function(element) {
    var current = head,
        index = 0;

    //循环这个链表,如果找到就返回index
    while(current) {
      if(element === current.element) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  };
  • 实现remove方法,从链表中移除一项
this.remove = function(element) {
    //找到这个元素的索引值
    var index = this.indexOf(element);
    return this.removeAt(index);
  };
  • isEmpty、size、toString方法
//如果链表中不包含任何元素,返回true,如果链表长度大于0则返回false。
  this.isEmpty = function() {
    return length === 0;
  };

  //返回链表的length
  this.size = function() {
    return length;
  };
  
  //把链表中的对象转换为字符串
  this.toString = function() {
    var current = head,
        string = '';

    while(current) {
      string += current.element;
      current = current.next;
    }
    return string;
  };
  • 全部代码
//定义一个LinkedList类
function LinkedList() {
  //定义一个Node类,element用来保存节点上的数据,next表示指向链表中下一个项的指针
  var Node = function(element) {
    this.element = element;
    this.next = null;
  }

  //用length表示列表的数量
  var length = 0;
  //head存储第一个节点的引用
  var head = null;

  //向列表尾部添加一个新的项
  this.append = function(element) {
    var node = new Node(element),
        current;
    if(head === null) {
      head = node;
    }else {
      current = head;
      //循环列表,直到找到最后一项 
      while(current.next) {
        current = current.next;
      }
      //找到最后一项将其next赋为node,建立连接
      current.next = node;
    }
  };

  //从列表的特定位置移除一项
  this.removeAt = function(position) {
    if(position > -1 && position < length) {
      var current = head,
          previous,
          index = 0;

      //移除第一项
      if(position === 0) {
        head = current.next;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        //将previous与current的下一项链接起来:跳过current,从而移除它
        previous.next = current.next;
      }
      length--;
      return current.element;
    }else {
      return null;
    }
  };

  //返回元素在列表中的索引。如果列表中没有该元素则返回-1
  this.indexOf = function(element) {
    var current = head,
        index = 0;

    //循环这个链表,如果找到就返回index
    while(current) {
      if(element === current.element) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  };

  //从列表中移除一项
  this.remove = function(element) {
    //找到这个元素的索引值
    var index = this.indexOf(element);
    return this.removeAt(index);
  };

  //如果链表中不包含任何元素,返回true,如果链表长度大于0则返回false。
  this.isEmpty = function() {
    return length === 0;
  };

  this.size = function() {
    return length;
  };

  this.toString = function() {
    var current = head,
        string = '';

    while(current) {
      string += current.element;
      current = current.next;
    }
    return string;
  };
}

var test = new LinkedList();
test.append(1);
test.append(2);
test.append(4);
console.log(test.toString()); //"124"
console.log(test.indexOf(2)); // 1

参考学习

《学习javascript数据结构与算法》

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序猿DD

第二章 正则表达式位置匹配攻略

第二章 正则表达式位置匹配攻略 正则表达式是匹配模式,要么匹配字符,要么匹配位置。请记住这句话。 然而大部分人学习正则时,对于匹配位置的重视程度没有那么高。 本...

20410
来自专栏desperate633

LeetCode LintCode和大于S的最小子数组Minimum Size Subarray Sum题目分析

给定一个由 n 个整数组成的数组和一个正整数 s ,请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解,则返回 -1。

912
来自专栏程序员与猫

常见算法设计方法-分治法

分治法(Devide & Conquer) 1. 常见步骤 Devide 把一个问题的特殊实例划分成若干个子问题 Conquer 递归地解决每个子问题 Co...

2059
来自专栏Python爬虫与数据挖掘

浅谈Python内置对象类型——数字篇(附py2和py3的区别之一)

Python是一门面向对象的编程设计语言,程序中每一样东西都可以视为一个对象。Python内置对象可以分为简单类型和容器类型,简单类型主要是数值...

1012
来自专栏Java大联盟

Java面试手册:集合框架

2143
来自专栏木木玲

PriorityQueue 源码分析

3666
来自专栏向治洪

java 之容器

在Java中,我们想要保存对象可以使用很多种手段。我们之前了解过的数组就是其中之一。但是数组具有固定的尺寸,而通常来说,程序总是在运行时根据条件来创建对象,我们...

2158
来自专栏desperate633

LintCode 最小子数组 && 最大子数组题目分析代码最大子数组

判断加与不加的情况,这道题的解法很巧妙,类似于背包问题。 每个数组的元素都有两种情况,加与不加,所以我们从第一个元素开始判断,包括第一个元素时,和不包括第一个...

622
来自专栏用户2442861的专栏

Java中如何遍历Map对象的4种方法

既然java中的所有map都实现了Map接口,以下方法适用于任何map实现(HashMap, TreeMap, LinkedHashMap, Hashtabl...

901
来自专栏null的专栏

LeetCode——Two Sum

题目: Given an array of integers, find two numbers such that they add up to a spec...

3185

扫码关注云+社区