数据结构 - 链表

一.链表的概念

链表是一个在物理存储单元中不连续，没有顺序的的存储结构，关于它的顺序是由链表中的指针链接实现的，是一种递归的数据结构，链表有一系列节点组成，而这些节点会在运行时动态生成。

节点包括两个部分：一部分存储数据元素的数据域（存储对象），另一部分是存储下一个节点地址的指针域（引用下一个节点）。

优点：和线性表顺序结构相比，链表结构插入，删除操作不需要移动所有节点，不需要初始化容量。
缺点：搜索时必须遍历节点，含有大量引用，占空间大。

链表分为三类：单向链表，双向链表，循环链表。

二.单向链表

单链表是有序的列表

虽然单链表是有序列表，但是其元素并不是连续存储的。

特点：

1. 单链表是以节点的方式来存储的
2. 每个节点包含data域(存储数据)，next域(指向下一个节点)
3. 单链表的各个节点不一定是连续存储的

三.双向链表

双向链表可以向前或向后查找，与单向链表的区别就是它不仅有后继节点，还有前驱节点。

这样就既存储了下一个节点的地址，也存储了前一个节点的地址。而单向链表只能从一个方向查询。
双向链表可以自我删除，单向链表不可以，需要靠辅助节点来删除。

四.循环链表

将单链表中终点指针指向头结点，是整个链表形成环，这叫做单向循环链表。

4.1 约瑟夫（Josephu）环问题

约瑟夫问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。

如何解决？
使用单向环形链表解决Josephu问题，用不带头结点的单向循环链表先构成一个有n个节点的链表，然后由k节点起从1开始计数，直到第m时，对应节点删除，然后从被删除的下一个节点开始从1开始计数，直到最后一个节点被删除结束算法。

class Node {
  constructor(ele) {
    this.element = ele
    this.next = null
  }
}

class LList {
  constructor() {
    this.head = new Node('head')
    this.head.next = this.head;
    this.currentNode = this.head;
  }
  find(item) {
    let currNode = this.head;
    while (currNode.element != item) {
      currNode = currNode.next;
    }
    return currNode;
  }
  insert(newElement, item) {
    let newNode = new Node(newElement);
    let current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
  }
  findPrevious(item) {
    let currNode = this.head;
    while (!(currNode.next == null) && (currNode.next.element != item)) {
      currNode = currNode.next;
    }
    return currNode;
  }
  remove(item) {
    let prevNode = this.findPrevious(item);
    if (!(prevNode.next == null)) {
      prevNode.next = prevNode.next.next;
    }
  }
  advance(n) {
    while (n > 0) {
      if (this.currentNode.next.element == "head") {
        this.currentNode = this.currentNode.next.next;
      } else {
        this.currentNode = this.currentNode.next;
      }
      n--;
    }
  }
  count() {
    let node = this.head;
    let i = 0;
    while (!(node.next.element == "head")) {
      node = node.next;
      i++;
    }
    return i;
  }
  display() {
    let currNode = this.head;
    while (!(currNode.next == null) && !(currNode.next.element == "head")) {
      console.log(currNode.next.element + ",");
      currNode = currNode.next;
    }
  }
}




let person = new LList();
person.insert('1', 'head');
for (let index = 1; index < 41; index++) {
  person.insert(`${index+1}`, `${index}`);
}


let n = 3;
while (person.count() > 2) {
  person.advance(n);
  person.remove(person.currentNode.element);
  person.display();
  console.log('------------------------------------------------');
}