JavaScript 链表

Question

一种简单的存储数据序列动态的数据结构，链表存储有序的元素集合，每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。

添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。

1、创建链表

function LinkedList() {

  let Node = function(element){ // {1}
    this.element = element;
    this.next = null;
  };

  let length = 0; // {2}
  let head = null; // {3}

  this.append = function(element){};
  this.insert = function(position, element){};
  this.removeAt = function(position){};
  this.remove = function(element){};
  this.indexOf = function(element){};
  this.isEmpty = function() {};
  this.size = function() {};
  this.getHead = function(){};
  this.toString = function(){};
  this.print = function(){};
}

2、在链表末尾追加元素

append(element)：向列表尾部添加一个新的项。

this.append = function(element){

  let node = new Node(element), //{1}
    current; //{2}

  if (head === null){ //列表中第一个节点 //{3}
    head = node;

  } else {
    current = head; //{4}

    //循环列表，直到找到最后一项
    while(current.next){
      current = current.next;
    }

    //找到最后一项，将其 next 赋为 node，建立链接
    current.next = node; //{5}
  }

  length++; //更新列表的长度 //{6}
};

3、从链表中移除元素

remove(element)：从列表中移除一项

this.removeAt = function(position){

  //检查越界值
  if (position > -1 && position < length){ // {1}

    let current = head, // {2}
    previous, // {3}
    index = 0; // {4}

    //移除第一项
    if (position === 0){ // {5}
      head = current.next;
    } else {

      while (index++ < position){ // {6}

        previous = current;     // {7}
        current = current.next; // {8}
      }

      //将 previous 与 current 的下一项链接起来：跳过 current，从而移除它
      previous.next = current.next; // {9}
    }

    length--; // {10}

    return current.element;

  } else {
    return null; // {11}
  }
};

4、在任意位置插入元素

insert(position, element)：向列表的特定位置插入一个新的项。

this.insert = function(position, element){

  //检查越界值
  if (position >= 0 && position <= length){ //{1}

    let node = new Node(element),
    current = head,
    previous,
    index = 0;

    if (position === 0){ //在第一个位置添加

      node.next = current; //{2}
      head = node;

    } else {
      while (index++ < position){ //{3}
        previous = current;
        current = current.next;
      }
      node.next = current; //{4}
      previous.next = node; //{5}
    }

    length++; //更新列表的长度

    return true;

  } else {
    return false; //{6}
  }
};

5、toString 方法

toString 方法会把 LinkedList 对象转换成一个字符串。

this.toString = function(){
　
  let current = head, //{1}
  string = '';    //{2}
　
  while (current) {   //{3}
    string +=current.element +(current.next ? 'n' : '');//{4}
    current = current.next;          //{5}
  }
  return string;              //{6}
};

6、indexOf 方法

indexOf 方法接收一个元素的值，如果在列表中找到它，就返回元素的位置，否则返回-1。

this.indexOf = function(element){
　
  let current = head, //{1}
  index = -1;
　
  while (current) { //{2}
    if (element === current.element) {
      return index;       //{3}
    }
    index++;                //{4}
    current = current.next; //{5}
  }
　
  return -1;
};

7、isEmpty 方法

如果列表中没有元素，isEmpty 方法就返回 true，否则返回 false。

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

8、size 方法

size 方法返回列表的 length。和我们之前几章实现的类有所不同，列表的 length 是内部控制的，因为 LinkedList 是从头构建的。

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

9、getHead 方法

head 变量是 LinkedList 类的私有变量（这意味着它不能在 LinkedList 实例外部被访问和更改，只有通过 LinkedList 实例才可以）。

this.getHead = function(){
  return head;
};