双向链表 - Githubissues

与单向链表的区别：

单向链表查找的方面只能是一个方向，而双向链表可以向前或者向后查找。
单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以 自我删除 ，所以前面我们单链表删除节点，总是找到temp，temp是待删除节点的前一个节点。

添加

找到链表最后一个节点（遍历）
```
//遍历 ..... 略
```

temp.next = newNode; newNode.pre = temp;


## 插入
- 找到链表插入位置，AC 插入 B
```java
//遍历 ..... 略

temp = A.next; //temp = C
A.next = B;
B.pre = A;
B.next = temp;
temp.pre = B;

//或者是这样
A.next.pre = B:
B.next = A.next;
A.next = B;
B.pre = A;

删除

因为是双向链表，可以实现自我删除某个节点
找到链表插入位置，ABC 删除 B
//遍历 ..... 略

//找到B B.pre.next = B.next; B.next.pre = B.pre;


## 应用
### 单项环形链表

构建一个单项环形链表
1. 先构建第一个节点，让first指向该节点。
1. 后面每创建一个新的节点，就把该节点，加入到已有的环形链表中。
1. 创建辅助指针temp，来代表最新的节点
```java
public Node(){}

// 伪代码
Node first = new Node();
first.next = first;

Node temp = first;

for(int i=0;i<10;i++){
    Node newNode = new Node();

    newNode.next = first;
    temp.next = newNode;
    temp = newNode;
}

遍历环形链表

先让弄一个辅助指针（变量）temp，指向first节点
然后通过一个while循环遍历该环形链表，temp.next == first 结束

Node temp = node;

while(true){
    if(temp.next == node)
        return ;
    sout(temp.next);
}

约瑟夫问题、丢手帕

约瑟夫问题（或称丢手帕问题）是指n个人围成一圈，从第一个人开始数1，数到第m个人数m则将m位置删除，继续接着从 1数,数到 m则将 m位置删除。如此循环，每次删除一个。这个问题的来源据说是 39个传教士和 2个朋友困在一个山洞中，传教士宁愿死也不愿被敌人抓到，故而决定大家一个一个自杀，这样可以避免同时自杀可能某些传教士后悔。但 2朋友是不想死的，

于是其中一个人将他俩的位置安排在16和31，这样最终避免了两个人的死亡。

这个问题从以下方向突破：

n个人围成1圈。

每次循环数m个数。

这样可以通过循环链表来实现遍历圈内的元素进行数数，可以通不过从1不断累加至m......2m......3m......每当数至m的整数倍时即可进行删除操作。程序的框架也就是初始化链表---->循环遍历链表---->每每遍历至m的整数倍时执行删除操作和输出删除的序号.

这里简化：5个小孩丢手帕，每次数1，2，3……，数到 2的时候，该小孩就出局。最后算出小孩出局的顺序

思路

根据用户的输入，生成一个出圈的顺序

n=5，即一共5个人
k=1，从第一个人开始报数
m=2，数 2下

创建一个辅助指针（变量）temp，事先应该指向环形链表的最后这个节点。
当小孩报数时，让first和temp指针同时移动 m-1次
这时就可以将first指向的小孩节点出圈。
```
first = first.next
temp.next = first
```
原来first指向的节点就没有任何引用，就会被回收

Zakariyya / blog

双向链表 #123

添加

删除

约瑟夫问题、丢手帕

思路