單向循環(huán)鏈表
單向循環(huán)鏈表只需要在之前的單向鏈表基礎(chǔ)之上進(jìn)行修改所意，這里只需要修改添加和刪除就可以了轨域。
單向循環(huán)鏈表 – add(int index, E element)
添加需要考慮往第0位置上添加結(jié)點(diǎn)的特殊情況
單向循環(huán)鏈表 – remove(int index)
單向循環(huán)鏈表不僅需要考慮刪除第0位置的結(jié)點(diǎn)伤为，還需要考慮如果只有一個(gè)結(jié)點(diǎn)的特殊情況咒循。
單向循環(huán)鏈表 – 只有1個(gè)節(jié)點(diǎn)
雙向循環(huán)鏈表
雙向循環(huán)鏈表 – add(int index, E element)
雙向循環(huán)鏈表 – remove(int index)
雙向循環(huán)鏈表在刪除時(shí)還需要考慮如果只有一個(gè)結(jié)點(diǎn)的情況。
雙向循環(huán)鏈表 – 只有1個(gè)節(jié)點(diǎn)
約瑟夫問(wèn)題（Josephus Problem）
約瑟夫問(wèn)題（Josephus Problem）：例如有八個(gè)人绞愚，這八個(gè)人排成一個(gè)圈叙甸，每個(gè)人都有一個(gè)序號(hào)，從第1個(gè)開始數(shù)位衩，數(shù)到第三個(gè)裆蒸，那么第三個(gè)就拿出去槍斃，循環(huán)下去糖驴，最后誰(shuí)能活下來(lái)僚祷。
這個(gè)問(wèn)題可以使用之前介紹的循環(huán)鏈表就可以很好的解決哪痰，但是我們還可以把之前介紹的循環(huán)鏈表發(fā)揮最大威力
如何發(fā)揮循環(huán)鏈表的最大威力？
可以考慮增設(shè)1個(gè)成員變量久妆、3個(gè)方法
- current:用于只想某一個(gè)結(jié)點(diǎn)
- void reset():讓 current 指向結(jié)點(diǎn)first
- E next():讓 current 往后走一步晌杰，也就是 current = current.next
- E remove():刪除 current 指向的結(jié)點(diǎn)，刪除成功后讓 current 指向下一個(gè)結(jié)點(diǎn)筷弦。
我們這里直接采用之前的雙向循環(huán)鏈表來(lái)實(shí)現(xiàn)肋演，單向循環(huán)鏈表暫時(shí)不實(shí)現(xiàn)(雙向的實(shí)現(xiàn)了，那么單向的也就會(huì)實(shí)現(xiàn)了)烂琴。
在雙向循環(huán)鏈表中新增current成員屬性
實(shí)現(xiàn)reset()
public void reset() {
current = first;
}
實(shí)現(xiàn)next()
public E next() {
if(current == null) return null;
current = current.next;
return current.element;
}
實(shí)現(xiàn)remove()
我們可以使用indexOf(E element)和remove(int index)方法來(lái)實(shí)現(xiàn)本本方法
public E remove() {
if(current == null) return null;
return remove(indexOf(current.element));
}
但是這個(gè)做法覺(jué)得太笨了爹殊，那么我們是否可以新增一個(gè)remove(Node<E> node)方法該多好。
private E remove(Node<E> node) {
if(size == 1) {
first = null;
last = null;
}else {
Node<E> prev = node.prev;
Node<E> next = node.next;
prev.next = next;
next.prev = prev;
if(node == first) {//index == 0 刪除0位置的結(jié)點(diǎn)
first = next;
}
if(node == last) {//index == size - 1 刪除最后一個(gè)結(jié)點(diǎn)
last = prev;
}
}
size--;
return node.element;
}
實(shí)現(xiàn)了remove(Node<E> node)方法奸绷，那么之前的remove(int index)方法就可以簡(jiǎn)單實(shí)現(xiàn)
public E remove(int index) {
rangeCheck(index);//如果鏈表中沒(méi)有數(shù)據(jù)
return remove(findNode(index));
}
最后實(shí)現(xiàn)remove()方法：
public E remove() {
if(current == null) return null;
Node<E> next = current.next;
E element = remove(current);
if(size == 0) {
current = null;
}else {
current = next;// current 指向下一個(gè)結(jié)點(diǎn)
}
return element;
}
這里還要考慮鏈表中只有一個(gè)結(jié)點(diǎn)的特殊情況梗夸。
現(xiàn)在實(shí)現(xiàn)上面的約瑟夫問(wèn)題（Josephus Problem）
輸出結(jié)果：
靜態(tài)鏈表(了解)
- 前面所學(xué)的鏈表，是依賴于指針(引用)實(shí)現(xiàn)的号醉，有的編程語(yǔ)言是沒(méi)有指針的反症，比如早期的BASIC、FORTRAN語(yǔ)言
- 沒(méi)有指針的情況下畔派，如何實(shí)現(xiàn)鏈表铅碍？
- 可以通過(guò)數(shù)組來(lái)模擬鏈表，成為靜態(tài)鏈表
- 數(shù)組的每個(gè)元素存放2個(gè)數(shù)據(jù)：值线椰、下個(gè)元素的索引
- 數(shù)組0位置存放的是頭結(jié)點(diǎn)信息
思考：如果數(shù)組的每個(gè)元素只能存放1個(gè)數(shù)據(jù)呢胞谈？
那就使用2個(gè)數(shù)組，1個(gè)數(shù)組存放索引關(guān)系憨愉，1個(gè)數(shù)組存放值
