-
單向循環(huán)鏈表
什么叫單向循環(huán)鏈表呢？相對于我們之前所了解的鏈表，多了一個循環(huán)润讥，那我們來看看什么是單向循環(huán)鏈表。
普通的 單向鏈表
單向循環(huán)鏈表是這樣的常潮，最后一個節(jié)點(diǎn)的next指向了鏈表中的第一個節(jié)點(diǎn)喊式，與我們之前學(xué)習(xí)的環(huán)形鏈表比較相似
通過前面的知識孵户，我們已經(jīng)能自己實(shí)現(xiàn)一個單向循環(huán)鏈表了，所以岔留，我們先自己來實(shí)現(xiàn)一個單向循環(huán)鏈表吧夏哭，實(shí)現(xiàn)完成以后，再看看單向循環(huán)鏈表到底有什么用献联。
其實(shí)單向循環(huán)鏈表非常的簡單竖配，只需要在我們之前的單向鏈表當(dāng)中何址，稍微做一點(diǎn)改進(jìn)就可以了
添加方法的修改add(int index, E element)
public void add(int index, E element) {
rangeCheckForAdd(index);
System.out.println("index == " + index);
if (index == 0) {
Node<E> newFirst = new Node<E>(element,first);
//拿到最后一個節(jié)點(diǎn)
Node<E> last = (size == 0) ? newFirst : node(size - 1);
last.next = newFirst;
first = newFirst;
} else {
Node<E> prev = node(index - 1);
prev.next = new Node<>(element,prev.next);
}
size++;
}
我們在添加元素的時候，只需要在index == 0 時进胯，去維護(hù)循環(huán)的那一根線就可以了用爪，不過，需要注意一種特俗的情況胁镐，即當(dāng)一開始偎血，鏈表為空的時候這種情況，添加完元素以后盯漂，為下圖的所示颇玷，所以需要做特俗的判斷
刪除節(jié)點(diǎn) E remove(int index)
同樣的，在刪除節(jié)點(diǎn)時宠能，需要注意當(dāng)刪除的是頭節(jié)點(diǎn)的情況亚隙，需要做特俗處理，并且需要注意的是违崇，當(dāng)size為1的時候阿弃，也需要特殊處理，否則會出現(xiàn)無法刪除的情況羞延，最終刪除的代碼如下所示
public E remove(int index) {
rangeCheck(index);
Node<E> node = first;
if (index == 0) {
if (size == 1) {
first = null;
} else {
//拿到最后一個節(jié)點(diǎn)
Node<E> last = node(size - 1);
first = first.next;
last.next = first;
}
} else {
Node<E> prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
size--;
return node.element;
}
通過以上修改以后渣淳，單向循環(huán)鏈表通過了我們LinkedListDemo類的測試。接下來伴箩，我們看看雙向循環(huán)鏈表入愧。
-
雙向循環(huán)鏈表
首先我們來回顧以下前面所介紹的雙向鏈表
在以前，雙向循環(huán)鏈表嗤谚，如果是頭節(jié)點(diǎn)棺蛛，它的prev指向的是null，如果是尾節(jié)點(diǎn)巩步，它的next指向的是null
如果是雙向循環(huán)鏈表旁赊，則是這樣的
如果是頭節(jié)點(diǎn)，頭節(jié)點(diǎn)的prev指向的是鏈表的尾節(jié)點(diǎn)椅野，如果是尾節(jié)點(diǎn)终畅，則尾節(jié)點(diǎn)的next指向的是頭節(jié)點(diǎn)，那么在這種情況下竟闪，應(yīng)該如何做鏈表的添加和刪除呢离福？同樣的，我們在原來雙向鏈表的基礎(chǔ)上進(jìn)行修改炼蛤，參照CircleLinkedList.java類
添加過程分析
假設(shè)有如下所示的鏈表對象妖爷，添加66的元素
如果我們是往最后的位置添加該節(jié)點(diǎn)，則添加完成后的引用應(yīng)該是這樣的
不過需要注意的是理朋，當(dāng)往鏈表最前面的節(jié)點(diǎn)添加元素時赠涮，也需要特殊的處理子寓。
通過以上分析，將代碼調(diào)整后如下所示add(int index, E element)
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == size) {
Node<E> oldLast = last;
last = new Node<>(oldLast,element,first);
if (oldLast == null) {
first = last;
first.next = first;
first.prev = first;
} else {
oldLast.next = last;
first.prev = last;
}
} else {
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev,element,next);
next.prev = node;
prev.next = node;
if (index == 0) {
first = node;
}
}
size++;
}
刪除過程代碼調(diào)整E remove(int index)
public E remove(int index) {
rangeCheck(index);
Node<E> node = first;
if (size == 1) {
first = null;
last = null;
} else {
Node<E> node = node(index);
Node<E> prev = node.prev;
Node<E> next = node.next;
prev.next = next;
next.prev = prev;
if (node == first) {//等價于index == 0
first = next;
}
if (node == last) {//等價于index == size - 1
last = prev;
}
}
size--;
return node.element;
}
通過以上修改以后笋除，同樣通過了我們LinkedListDemo類的測試斜友。說明以上修改沒有問題
接下來，做一個小練習(xí)吧垃它！
練習(xí) - 約瑟夫問題
假設(shè)圈里面是8個人鲜屏，8個人排成一個圈，每個人都又自己的序號国拇，從序號為1的人開始數(shù)數(shù)洛史，數(shù)到3的時候槍斃，然后下一位又從1開始數(shù)數(shù)酱吝，重復(fù)如此也殖，最終看看誰能活下來。
這個問題务热，通過借助本文的循環(huán)鏈表就非常好解決忆嗜，不過為了把循環(huán)鏈表的威力發(fā)揮到最大，我們可以做下面一些事情
如何發(fā)揮循環(huán)鏈表的最大威力崎岂？
增設(shè)一個成員變量和三個方法
成員變量：current：用于指向某個節(jié)點(diǎn)
三個方法：
- void reset()：讓current指向頭節(jié)點(diǎn)first
- E next()：讓current往后走一步捆毫，也就是current= current.next
- E remove()：刪除current指向的節(jié)點(diǎn)，刪除成功后冲甘，讓current指向下一個節(jié)點(diǎn)
current如下所示
以下是方法的實(shí)現(xiàn)
void reset()
public void reset() {
current = first;
}
E next()
public E next() {
if (current == null) return null;
current = current.next;
return current.element;
}
E remove()
public E remove() {
if (current == null) return null;
Node<E> next = current.next;
E element = remove(current);
current = next;
return element;
}
通過封裝的方法與成員變量绩卤，即可輕松的解決上面的約瑟夫問題。代碼如下<建議直接下載源碼進(jìn)行閱讀>
static void josephus(){
CirleLinkedList<Integer> list = new CirleLinkedList<>();
for (int i = 1; i <= 8 ; i++) {
list.add(i);
}
list.reset();//指向頭節(jié)點(diǎn)
while (!list.isEmpty()) {
list.next();
list.next();
System.out.println( list.remove());
}
}
-
靜態(tài)鏈表
前面說介紹的鏈表江醇，都是依賴于指針（引用）實(shí)現(xiàn)的濒憋，有些編程語言是沒有指針的，比如早期的BASIC,FORTRAN語言陶夜，沒有指針的情況下跋炕，如何實(shí)現(xiàn)鏈表？
- 可以通過數(shù)組來模擬鏈表律适，稱為靜態(tài)鏈表
- 數(shù)組的每個元素存放2個數(shù)據(jù)：值，下一個元素的索引
- 數(shù)組0位置存放的是頭節(jié)點(diǎn)信息
將鏈表訪問軌跡則為這樣的遏插、
串起來后捂贿，是這樣的
??如果數(shù)組的每個元素只能存放一個數(shù)據(jù)呢？
那就使用兩個數(shù)組胳嘲，一個數(shù)組存放索引關(guān)系厂僧，一個數(shù)組存放值
練習(xí)：ArrayList進(jìn)一步優(yōu)化
在之前，我們的ArrayList是存在性能問題的了牛，例如上圖的一個數(shù)組對象颜屠，如果我們是頭部進(jìn)行新增元素或則刪除元素辰妙，會對所有的元素進(jìn)行移動操作
刪除前面的元素
我們可以再增加一個成員變量，用來保存首元素的位置甫窟，并且永遠(yuǎn)記錄首元素的位置密浑，這樣在刪除元素時，就不用再對數(shù)組中的每個元素進(jìn)行移動操作了
往最前面添加元素
如果我們要再數(shù)組的首節(jié)點(diǎn)添加元素的話粗井，也是對首元素進(jìn)行操作尔破，比如現(xiàn)在有以下數(shù)組
假設(shè)我們還要繼續(xù)往數(shù)組的最前面插入元素，我們則可以通過在數(shù)組尾部添加浇衬，下圖所示
這種情況懒构，如果我們要對數(shù)組進(jìn)行遍歷的話，就可以從8的位置遍歷耘擂，然后索引增加胆剧，下一個訪問索引為0的元素，我們可以對索引進(jìn)行取余操作醉冤，就可以了
往中間添加元素
如果我們想要在數(shù)組中間插入元素
以前的話秩霍，我們是將后面的所有元素，往后移動冤灾，但是引入了記錄首元素位置后前域，我們可以選擇移動元素較少的一邊，如將上圖中的22韵吨，33往前移動
然后就可以在空出來的地方匿垄，插入新的元素
刪除中間的元素
與往中間添加元素相似，如果我們要刪除中間的元素归粉，也是選擇元素較少的一方來進(jìn)行元素移動
刪除完成后
通過這種操作椿疗，可以極大的減少數(shù)組中元素的挪動，進(jìn)而達(dá)到性能優(yōu)化的目的糠悼。
本節(jié)完届榄！
