数据结构-javascript实现【链表】

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

1. 链表的职责

  append(element):  向链表尾部添加一个新的元素

  insert(element): 向链表的特定位置插入一个新的元素

  remove(element): 从链表中移除一个元素

  indexOf(element): 返回元素在链表中的索引，如果找不到该元素则返回-1

  removeAt(position): 从链表的特定位置移除一项

  isEmpty()：检测链表是否为空

  size(): 返回链表包含的元素个数

2. 链表的实现

class LinkedList {
  constructor(){
    this.length = 0;
    this.head = null;
  }

  append(element) {
    const node = new Node(element);
    let current = null;
    if(this.head === null)
    {
      this.head = node;
    } 
    else 
    {
      current = this.head;
      while(current.next)
      {
        current = current.next;
      }
      current.next = node;
    }
    this.length++;
  }

  insert(position, element) {
    if(position < 0 || position > this.length) return false;
    const node = new Node(element);
    let current = this.head;
    let previous = null;
    let index = 0;
    if(position === 0){
      node.next = current;
      head = node;
    }
    else
    {
      while(index++ < position){
        previous = current;
        current = current.next;
      }
      node.next = current;
      previous.next = node;
    }
    this.length++;
    return true;
  }

  removeAt(position) {
    if(position < 0 || position >= this.length) return null;
    let current = this.head;
    let previous = null;
    let 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;
  }
 
  remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  }

  indexOf(element) {
    let current = this.head;
    let index = 0;
    while(current) {
      if(element === current.element)
      {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  }

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

  size() {
    return this.length;
  }

  getHead() {
    return this.head;
  }

  toString() {
    let current = this.head;
    let strings = [];
    while(current){
      strings.push(current.element);
      current = current.next;
    }
    return strings.join(',');
  }

  print() {
    console.log(this.toString());
  }
}

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

const list = new LinkedList();
console.log(list.isEmpty());
list.append(15);
list.append(10);
list.append(23);
list.insert(1,11);
list.print(); // 15, 11, 10, 23
const p = list.indexOf(10); 
console.log(p); //2
const size = list.size();
console.log(size); // 4
const head = list.getHead();
console.log(head.element);
list.remove(10);
list.print(); // 15, 11, 23
list.removeAt(0);
list.print(); // 11, 23