单链表

一、什么是单链表 二、单链表的封装 三、单链表的常用操作 1、append(element)方法-----向列表尾部添加一个项 2、toString方法-----输出元素的值 3、insert方法-----向列表的特定位置插入一个项 4、get方法-----获取对应位置的元素 5、indexOf()方法-----返回元素在列表中的索引 6、update方法-----修改某个位置的元素 7、removeAt方法-----从列表的指定位置移除一项 8、remove方法-----从列表中移除一项 9、isEmpty方法-----判断链表是否为空 9、size方法-----返回链表包含的元素个数
要存储多个元素，数组是最常用的数据结构，但是数组也有很多缺点：

数组的创建通常要申请一段连续的内存空间，并且大小是固定的，所以当当前数组不能满足容量需求时，需要进行扩容，（一般是申请一个更大的数组，然后将原数组中的元素复制过去） 在数组元素开头或者中间位置插入数据的成本很高，需要进行大量元素的位移。

所以要存储多个元素，另一个选择就是链表，不同于数组的是，链表中的元素在内存中不必是连续的空间。链表的每个元素有一个存储元素本身的节点和指向下一个元素的引用。
相对于数组，链表有一些优点：

内存空间不必是连续的，可以充分利用计算机的内存，实现灵活的内存动态管理。 链表不必在创建时就确定大小，并且大小可以无限延伸下去。 链表在插入和删除数据的时候，事件复杂度可以达到O（1），相对数组效率高很多。

相对于数组，链表有一些缺点：

链表访问任何一个位置的元素的时候，都需要从头开始访问，无法通过下标直接访问元素。

一、什么是单链表

那么到底什么是单链表呢？
它就类似于火车，火车头规连接一个节点，节点上有乘客，并且这个节点会连接到下一个节点，依次类推，如下所示：


我们的链表结构就是：

了解了直观上的链表，我们再来对单链表进行代码的封装。

二、单链表的封装

首先，我们封装一个NodeList类，用于表示链表结构，在这个类里面在封装一个内部类Node，用于封装每一个节点上的信息（数据和指向下一个节点的引用），然后在NodeList类中保存两个属性，一个是链表的长度，一个是链表中的头结点。如下所示：

 function LinkedList(){
            this.length = 0;
            this.head = null;
            //内部的类
            function Node(data){
                this.data = data;
                this.next = null;
            }
        }

三、单链表的常用操作

然后在里面添加单链表常用的操作。主要有：

append（element:向列表尾部添加一个项 insert(position,element):向列表的特定位置插入一个项 get(position):获取对应位置的元素 indexOf(element):返回元素在列表中的索引，如果列表中没有该元素则返回-1 update(position，ele):修改某个位置的元素 removeAt(position):从列表的指定位置移除一项 remove(element):从列表中移除一项 isEmpty():如果链表中不包含任何元素，返回true,如果链表长度大于0返回false size():返回链表包含的元素个数，与数组的length属性相关 toString():由于列表项用到了Node类，需要重写继承自JavaScript对象默认的toString方法，让其输出元素的值

接下来们就来一个一个实现。

1、append(element)方法-----向列表尾部添加一个项

因为向链表尾部添加数据可能有两种情况：

链表本身为空，新添加的数据是唯一的节点 链表不为空，需要向其他节点后面追加节点

所以我们就需要进行判断，如果链表为空，直接将头结点的指针指向新节点。
如果链表不为空，则新建立一个临时节点，让它等于头结点，并对它进行判断，如果它指向的节点的指针域为空，则为尾节点，将新加的节点添加到末尾，即让尾节点的指针指向新添加的节点。如果它指向的节点的指针域不为空，则让这个临时节点的指针域指向下一个节点，一直循环操作到这个节点的指针域为空（即为尾节点）。然后每添加一个节点，让链表的长度+1。

LinkedList.prototype.append = function(data){
                var newNode = new Node(data);
                // 判断链表是否为空
                // 1.为空
                if(this.length === 0){
                    this.head = newNode;
                }else{
                    //不为空
                    var current = this.head;
                    if(current.next){
                        current = current.next;
                    }
                    current.next = newNode;
                }
                this.length += 1;
            }

2、toString方法-----输出元素的值

这个比较简单，主要是获取每一个元素，因为获取链表的任何元素都必须从第一个节点开始，所以我们可以从头结点开始，循环遍历每一个节点，并且取出其中的element，拼接成字符串，并将字符串返回。

LinkedList.prototype.toString = function(){
                var current = this.head;
                var ListStr = '';
                while(current){
                    ListStr += current.data + ' ';
                    current = current.next;
                }
                return ListStr;
            }

验证：创建几个新的节点，并打印

 var list = new LinkedList();
        list.append('a');
        list.append('b');
        list.append('c');
        list.append('d');
        list.append('e');
        alert(list);

打印结果为：

3、insert方法-----向列表的特定位置插入一个项

实现在任意位置插入数据的方法，首先判断插入的位置是否越界，然后在不越界的情况下分两种情况，如果插入到第一个位置，则表示新添加的节点是头，则需要将原来的头结点作为新节点的next,再让head指向新节点。如果插入到其他位置，则需要通过循环先找到节点位置，并在循环的过程中保存上一个节点和下一个节点，找到正确的位置后，将新节点的Next指向下一个节点，将上一个节点的next节点指向新节点。代码如下：

 LinkedList.prototype.insert = function(position,data){
                if(position<0 || position >this.length){
                   return false;
               }
                var newNode = new Node(data);
                var index = 0;
              if(position == 0){
                newNode.next = this.head;
                this.head = newNode;

              }else{
                    while(index++ < position){
                        var current = this.head;
                        var previous = null;
                        previous = current;
                        current = current.next;
                    }
                    newNode.next = current;
                    previous.next = newNode;
                }
                this.length += 1;
                return true;
                }

验证：在第1个位置插入xl,在第2个位置插入wh

list.insert(1,'xl')
       list.insert(2,'wh')
        alert(list)

4、get方法-----获取对应位置的元素

这个方法相对简单，先对positon做越界判断，然后通过临时节点遍历链表直到目标位置，获取该位置的元素。

LinkedList.prototype.get = function(position,data){

                var current = this.head;
                var index = 0;
                if(position < 0 || position >= this.length){
                    return null;
                }else{
                    while(index<position){
                        current = current.next;
                        index++;
                    }
                    return current.data;
                }
            }

验证：获取第三个位置的元素：

alert( list.get(3));

5、indexOf()方法-----返回元素在列表中的索引

首先判断查找的元素的位置是否存在，如果不存在，返回-1。如果存在的话分两种情况，如果返回的元素在第一个位置，则直接返回第一个位置的索引。如果返回元素在其他位置，则需要通过循环先找到节点位置，这个过程中，索引需要跟着遍历的次数自加，找到正确元素的位置后，打印索引即为目标位置。

LinkedList.prototype.indexOf = function(data){
                var index = 0;
                var current = this.head;
                while(current){
                    if(current.data == data){
                        return index;
                    }
                    else{
                        current = current.next;
                    index++;
                    }
                }
                return -1;
            }
        }

验证：获取c的索引：

alert(list.indexOf('c'));

6、update方法-----修改某个位置的元素

这个方法和get方法很像，向后遍历，当index的值等于position时，表示找到目标位置，将date改为目标值：

LinkedList.prototype.update = function(position,ele){
                if(position<0 || position>=this.length){
                    return false;
                }else{
                    var index = 0;
                    var current = this.head;
                    while(index++ <position){
                        current = current.next;
                    }
                    current.data = ele;
                    return true;
                }
            }

验证：修该第0个位置的元素为：bear

 list.update(0,'bear')
      alert(list)

7、removeAt方法-----从列表的指定位置移除一项

首先判断删除项的位置是否越界，然后在不越界的情况下，给定两个临时节点previous和current，previous用来保存前一个current的值，从头节点开始遍历，直到索引位置等于目标位置，让临时节点current遍历到目标位置，让临时节点的前一个next指向下一个next。

LinkedList.prototype.removeAt = function(position,data){
                var current = this.head;
                var previous = null;
                var index = 0;
                if(position<0 || position>=this.length){
                    return false;
                }else{
                    while(index++ <position){
                        previous = currrent;
                        current = current.next;
                    }
                    previous.next = current.next;
                    this.length -= 1;
                    return true;
                }
            }
        }

验证：移除第三个位置的元素：

list.removeAt(3)
      alert(list)

8、remove方法-----从列表中移除一项

先判断所要删除的元素是否在链表中，如果不在，返回false，否则，构建一个临时节点，用于遍历链表，如果临时节点的data值和要删除的元素相等，则停止遍历，让临时节点的前一个next指向下一个next。这里可以在构建一个临时节点用于存储前一个current的值。

LinkedList.prototype.remove = function(ele){
                var current = this.head;
                var previous = null;
                var index = 0;
                while(current.data !== ele){
                    previous = current;
                    current = current.next;
                    index++;
                }
                previous.next = current.next;
            }

验证：删除值为xl的元素：

 list.remove('xl')
      alert(list)

9、isEmpty方法-----判断链表是否为空

根据length判断，如果链表中不包含任何元素，返回true,如果链表长度大于0返回false

LinkedList.prototype.isEmpty = function(){
                    return this.length == 0;
                }

验证：

 alert(list.isEmpty())

9、size方法-----返回链表包含的元素个数

直接返回元素的length就是其个数。

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

验证：

   alert(list.size())