Javascript-算法-linked list

2017-03-16

链表：任意添加或移除项，它会按需进行扩容。

要存储多个元素，数组(或列表)可能是最常用的数据结构。
这种数据结构非常方便，提供了一个便利的[]语法来访问它的元素。
然而，这种数据结构有一个缺点:数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。
每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成。

方法	描述
append(element)	向列表尾部添加一个新项。
insert(position, element)	向列表的特定位置插入一个新项。
remove(element)	从列表中移除一项。
removeAt(position)	从列表的特定位置移除一项。
indexOf(element)	返回元素在列表中的索引。如果列表中没有该元素则返回-1。
isEmpty()	如果链表中不包含任何元素，返回true，否则返回false。
size()	返回链表包含的元素个数。
toString()	由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。

const Node = function(element){ 
  this.element = element;
  this.next = null;
};
function LinkedList() {
  let length = 0; 
  let head = null; 
  this.append = function(element){
    const node = new Node(element);
    let current;
    if(length == 0){
      head = node;
    }else{
      current = head;
      while(current.next){
        current = current.next;
      }
      current.next = node;
    }
    length ++;
  };
  this.insert = function(position, element){
    if(position >=0 && position <= length){
      const node = new Node(element);
      let current = head, index = 0;
      if(position == 0){
        node.next = head;
        head = node;
      }else{
        while(index != position - 1){
          current = current.next;
          index ++;
        }
        node.next = current.next;
        current.next = node;
      }
      length ++;
      return true;
    }else{
      return false;
    }
  };
  this.removeAt = function(position){
    if(position > -1 && position < length){
      let removeEle = head;
      if(position == 0){
        head = head.next;
      }else{
        let current = head, index = 0;
        while(index != position - 1){
          current = current.next;
          index ++;
        }
        removeEle = current.next;
        current.next = current.next.next;
      }
      length --;
      return removeEle.element;
    }else{
      return null;
    }
  };
  this.remove = function(element){};
  this.indexOf = function(element){
    let current = head, index = 0;
    while(current){
      if(current.element == element){
        return index;
      }else{
        current = current.next;
        index ++;
      }
    }
    return -1;
  };
  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 = string + current.element;
      current = current.next;
    }
    return string;
  };
  this.print = function(){};
}
const list = new LinkedList();
list.append(1);
list.append(7);
list.append(4);