一.链表的概念
链表是一个在物理存储单元中不连续，没有顺序的的存储结构，关于它的顺序是由链表中的指针链接实现的，是一种递归的数据结构，链表有一系列节点组成，而这些节点会在运行时动态生成。
节点包括两个部分：一部分存储数据元素的数据域（存储对象），另一部分是存储下一个节点地址的指针域（引用下一个节点）。
优点：和线性表顺序结构相比，链表结构插入，删除操作不需要移动所有节点，不需要初始化容量。
缺点：搜索时必须遍历节点，含有大量引用，占空间大。
链表分为三类：单向链表，双向链表，循环链表。
二.单向链表
单链表是有序的列表
虽然单链表是有序列表，但是其元素并不是连续存储的。
特点：
- 单链表是以节点的方式来存储的
- 每个节点包含data域(存储数据)，next域(指向下一个节点)
- 单链表的各个节点不一定是连续存储的
三.双向链表
双向链表可以向前或向后查找，与单向链表的区别就是它不仅有后继节点，还有前驱节点。
这样就既存储了下一个节点的地址，也存储了前一个节点的地址。而单向链表只能从一个方向查询。
双向链表可以自我删除，单向链表不可以，需要靠辅助节点来删除。
四.循环链表
将单链表中终点指针指向头结点，是整个链表形成环，这叫做单向循环链表。
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('------------------------------------------------');
}
