首先要明确，我们为什么要创建链表呢？数组的大小是固定的，从数组的起点或中间插入或移除的成本很高，因为需要移动元素。尽管JS的Array类方法可以做这些，但是情况也是这样。链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身和指向下一个元素的指针组成。

相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，需要从起点（表头）开始迭代到列表直到找到所需元素。

好了，闲话少叙，正式创建链表！
我们使用动态原型模式来创建一个链表。列表最后一个节点的下一个元素始终是null。

function LinkedList() {

    //先创建一个节点

    function Node(element) {

        this.element = element;

        this.next = null;

    }

    this.head = null;

    this.length = 0;

    //通过对一个方法append判断就可以知道是否设置了prototype

    if ((typeof this.append !== 'function') && (typeof this.append !== 'string')) {

        //添加元素

        LinkedList.prototype.append = function(element) {

            var node = new Node(element);

            var current;

            if (this.head == null) {

                this.head = node;

            } else {

                current = this.head;

                while (current.next != null) {

                    current = current.next;

                }

                current.next = node;

            }

            this.length++;

        };

        //插入元素，成功true，失败false

        LinkedList.prototype.insert = function(position, element) {

            if (position > -1 && position < this.length) {

                var current = this.head;

                var node = new Node(element);

                var previous;

                var index = 0;

                if (position == 0) {

                    node.next = current;

                    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;

            }

        };

        //根据位置删除指定元素，成功 返回元素， 失败 返回null

        LinkedList.prototype.removeAt = function(position) {

            if (position > -1 && position < this.length) {

                var current = this.head;

                var previous = null;

                var index = 0;

                if (position == 0) {

                    this.head = current.next;

                } else {

                    while (index++ < position) {

                        previous = current;

                        current = current.next;

                    }

                    previous.next = current.next;

                }

                this.length--;

                return current.element;

            } else {

                return null;

            }

        };

        //根据元素删除指定元素，成功 返回元素， 失败 返回null

        LinkedList.prototype.remove = function(element) {

            var index = this.indexOf(element);

            return this.removeAt(index);

        };

        //返回给定元素的索引，如果没有则返回-1

        LinkedList.prototype.indexOf = function(element) {

            var current = this.head;

            var index = 0;

            while (current) {

                if (current.element === element) {

                    return index;

                }

                current = current.next;

                index++;

            }

            return -1;

        };

        LinkedList.prototype.isEmpty = function() {

            return this.length === 0;

        };

        LinkedList.prototype.size = function() {

            return this.length;

        };

        LinkedList.prototype.toString = function() {

            var string = '';

            var current = this.head;

            while (current) {

                string += current.element;

                current = current.next;

            }

            return string;

        };

        LinkedList.prototype.getHead = function() {

            return this.head;

        };

    }

}

链表的基本使用

var linkedList = new LinkedList();

    console.log(linkedList.isEmpty());//true;

    linkedList.append('huang');

    linkedList.append('du')

    linkedList.insert(1,'cheng');

    console.log(linkedList.toString());//huangchengdu

    console.log(linkedList.indexOf('du'));//

    console.log(linkedList.size());//

    console.log(linkedList.removeAt(2));//du

    console.log(linkedList.toString());//huangcheng

创建双向链表

在双向链表中,链接是双向的:一个链向下一个元素, 另一个链向前一个元素。

双向链表和链表的区别就是有一个tail属性，所以必须重写insert、append、removeAt方法。每个节点对应的Node也多了一个prev属性。

//寄生组合式继承实现，详见javascript高级程序设计第七章

   function inheritPrototype(subType, superType) {

       function object(o) {

           function F() {}

           F.prototype = o;

           return new F();

       }

       var prototype = object(superType.prototype);

       prototype.constructor = subType;

       subType.prototype = prototype;

   }

   function DoublyLinkedList() {

       function Node(element) {

           this.element = element;

           this.next = null;

           this.prev = null;

       }

       this.tail = null;

       LinkedList.call(this);

       //与LinkedList不同的方法自己实现。

       this.insert = function(position, element) {

           if (position > -1 && position <= this.length) {

               var node = new Node(element);

               var current = this.head;

               var previous;

               var index = 0;

               if (position === 0) {

                   if (!this.head) {

                       this.head = node;

                       this.tail = node;

                   } else {

                       node.next = current;

                       current.prev = node;

                       this.head = node;

                   }

               } else if (position == this.length) {

                   current = this.tail;

                   current.next = node;

                   node.prev = current;

                   this.tail = node;

               } else {

                   while (index++ < position) {

                       previous = current;

                       current = current.next;

                   }

                   previous.next = node;

                   node.next = current;

                   current.prev = node;

                   node.prev = previous;

               }

               this.length++;

               return true;

           } else {

               return false;

           }

       };

       this.append = function(element) {

           var node = new Node(element);

           var current;

           if (this.head === null) {

               this.head = node;

               this.tail = node;

           } else {

               current = this.head;

               while (current.next !== null) {

                   current = current.next;

               }

               current.next = node;

               node.prev = current;

               this.tail = node;

           }

           this.length++;

       };

       this.removeAt = function(position) {

           if (position > -1 && position < this.length) {

               var current = this.head;

               var previous;

               var index = 0;

               if (position === 0) {

                   this.head = current.next;

                   if (this.length === 1) {

                       this.tail = null;

                   } else {

                       this.head.prev = null;

                   }

               } else if (position === (this.length - 1)) {

                   current = this.tail;

                   this.tail = current.prev;

                   this.tail.next = null;

               } else {

                   while (index++ < position) {

                       previous = current;

                       current = current.next;

                   }

                   previous.next = current.next;

                   current.next.prev = previous;

               }

               this.length--;

               return current.element;

           } else {

               return false;

           }

       };

   }

   inheritPrototype(DoublyLinkedList, LinkedList);

双向链表的基本使用

var doublyList = new DoublyLinkedList();

    console.log(doublyList.isEmpty()); //true;

    doublyList.append('huang');

    doublyList.append('du')

    doublyList.insert(1, 'cheng');

    console.log(doublyList.toString()); //huangchengdu

    console.log(doublyList.indexOf('du')); //

    console.log(doublyList.size()); //

    console.log(doublyList.removeAt(2)); //du

    console.log(doublyList.toString()); //huangcheng

最新文章

  1. MySQL SQL Mode及相关问题
  2. 【Java EE 学习 35 下】【struts2】【struts2文件上传】【struts2自定义拦截器】【struts2手动验证】
  3. 基于eBox旋转编码器
  4. html_博客博主
  5. MySQL函数汇总
  6. android-support-xxxx.jar NoClassDefFoundError
  7. 弹出框页面中使用jquery.validate验证控件
  8. u-boot向linux内核传递启动参数(详细)
  9. [Locked] Binary Tree Upside Down
  10. 博客SEO-搜索引擎工作原理简介
  11. 异步编程的两种模型，闭包回调，和Lua的coroutine，到底哪一种消耗更大
  12. HttpURLConnection 411错误解决
  13. MySQL/MariaDB 在插入数据的时候提示 Incorrect string value
  14. Django--CRM--modelformset的用法
  15. 解决IE11 Array没有find的方法
  16. 一月分四周的JAVA实现方法
  17. 【CTF WEB】服务端请求伪造
  18. C#使用ICSharpCode.SharpZipLib压缩后进行web批量下载文件
  19. Float浮点数的使用和条件
  20. SQL语句（十六）实现集合运算、对数据修改、数据表复制

热门文章

  1. Java基础第一天--继承、修饰符
  2. 从零开始使用mocha测试
  3. SpringCloud之Hystrix容错保护原理及配置
  4. VUE【二、选项和生命周期】
  5. 【6】Zookeeper脚本及API
  6. cbv装饰器 中间件 跨站请求伪造
  7. 002.MVC开发方法和步骤--用一个简单的加法程序来演示
  8. linux常用的操作命令
  9. LoadRunner（5）
  10. 关于C++编译时内链接和外链接