你的位置:首页 > Java教程

[Java教程]用JavaScript来实现链表LinkedList


写在前面

好多做web开发的朋友,在学习数据结构和算法时可能比较讨厌C和C++,上学的时候写过的也忘得差不多了,更别提没写过的了。但幸运的是,你会JavaScript啊。我想说学好数据结构和基本算法并非是要我们必须要去书写,算法的工作有专业的职位专业的人来做,但是如果你希望走的更高,这些是必不可少的,比如你学习Redis,如果hashmap等相关结构的话,也只能停留在使用的层次上,永远和优化不能挂钩。我也是个一瓶子不满半瓶子晃悠,和希望快速成长的伙伴们共同加深印象,共同提高吧。

如果你对JavaScript OOP还不太了解的话,请移步这两篇分享:http://www.cnblogs.com/tdws/p/5947693.html    http://www.cnblogs.com/tdws/p/5944254.html

如果你希望学习redis的话,可以看下这个链接 http://www.cnblogs.com/tdws/tag/NoSql/

 

进入正题

链表是一种动态的数据结构,不同于数组的是,链表分配内存空间的灵活性,它不会像数组一样被分配一块连续的内存。当你想在数组的任意位置,插入一个新值的时候,必须对数组中的各个元素进行相应的位置移动才能达到目标,开销显然是很大的。然而链表的灵活性在于它的每个元素节点分为两部分,一部分是存储元素本身,另一部分是指向下一个节点元素的引用,也可以称为指针,当你要插入数据时,把上一个节点的向下指针指向新数据节点,新数据节点的向下指针指向原有数据。但是链表不像数组那样可以直接通过索引立刻定位,只能通过遍历。

图画的可能是乱了点,就是想突出一下,链表分配内存的动态性,你随时随地,都可以增加和删除,并且内存的不连续性和无索引性。我暂时给链表类定义如下几个方法

一个append追加元素,一个removeAt移除指定位置元素,一个insert在指定位置插入元素,toString输出元素,一个indexOf寻找指定元素的索引。先上代码吧:

  function LinkedList() {    var Node = function (element) {        //新元素构造      this.element = element;      this.next = null;    };    var length = 0;    var head = null;    this.append = function (element) {      var node = new Node(element);        //构造新的元素节点      var current;      if (head === null) {             //头节点为空时 当前结点作为头节点        head = node;      } else {        current = head;                      while (current.next) {          //遍历,直到节点的next为null时停止循环,当前节点为尾节点          current = current.next;        }        current.next = node;            //将尾节点指向新的元素,新元素作为尾节点      }            length++;                    //更新链表长度    };    this.removeAt = function (position) {      if (position > -1 && position < length) {        var current = head;        var index = 0;        var previous;        if (position == 0) {          head = current.next;        } else {          while (index++ < position) {            previous = current;            current = current.next;          }          previous.next = current.next;        }        length--;        return current.element;      } else {        return null;      }    };    this.insert = function (position, element) {      if (position > -1 && position <= length) {        //校验边界        var node = new Node(element);                current = head;        var index = 0;        var previous;        if (position == 0) {                    //作为头节点,将新节点的next指向原有的头节点。          node.next = current;          head = node;                        //新节点赋值给头节点        } else {          while (index++ < position) {            previous = current;            current = current.next;          }                                //遍历结束得到当前position所在的current节点,和上一个节点          previous.next = node;                    //上一个节点的next指向新节点 新节点指向当前结点,可以参照上图来看          node.next = current;        }        length++;        return true;      } else {        return false;      }    };    this.toString = function () {      var current = head;      var string = '';      while (current) {        string += ',' + current.element;        current = current.next;      }      return string;    };    this.indexOf = function (element) {      var current = head;      var index = -1;      while (current) {        if (element === current.element) {            //从头节点开始遍历          return index;        }        index++;        current = current.next;      }      return -1;    };    this.getLength = function () {      return length;    }  }

写在最后

接下来将将分享双向LinkedList和hashMap以便谈及redis数据类型以及一些基本算法。

如果我的点滴分享对您有点滴帮助。欢迎你为自己点赞,也为我点赞。也欢迎点击红色按钮长期关注,我将持续分享。