單項循環連結清單
圖解
實作
步驟分析
由于之前已經寫過了單連結清單單向連結清單，而單向循環鍊多數操作和單連結清單操作一緻，是以我們隻需基于之前的代碼進行修改添加結點和删除結點的操作即可。
代碼範例
添加操作
有元素的情況下，向0索引位置插入元素
如下圖所示：
1. 新結點的next指向0索引位置的元素
2. 尾元素的next指針指向新結點
3. first指針指向新結點
連結清單沒有元素的情況下向0索引位置插入元素
如下圖所示，操作步驟為：
1. 新結點的next指向自己
2. first的next指針指向新結點
正常插入(包括插傳入連結表尾部)
如下圖所示，操作步驟為:
1. 新結點next指向指定索引位置的原元素
2. 原元素的前驅結點指向新結點
代碼實作
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == 0) {
Node<E> newNode = new Node<E>(element, first);
Node<E> lastNode = (size == 0) ? newNode : findNode(index - 1);
lastNode.next = newNode;
first = newNode;
} else {
Node<E> preNode = findNode(index - 1);
Node<E> newNode = new Node<E>(element, preNode.next);
preNode.next = newNode;
}
size++;
}
删除操作
過程圖解
連結清單元素大于1的情況下删除0索引位置元素
如下圖所示，操作步驟為：
1. 尾結點指向首結點的下一節點
2. first指向首結點的下一節點
連結清單元素隻有1的情況下删除0索引元素
如下圖所示，将first指針置空即可
正常删除
如下圖所示，将待删結點的前驅結點指向待删結點的後繼節點即可
代碼實作
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> delNode = first;
if (index == 0) {
if (size == 1) {
first = null;
} else {
Node<E> lastNode = findNode(size - 1);
lastNode.next = first.next;
first = first.next;
}
} else {
Node<E> prevNode = findNode(index - 1);
delNode = prevNode.next;
prevNode.next = delNode.next;
}
size--;
return delNode.element;
}
完整代碼
package com.study.Circle;
import com.study.singlelinkDemo.AbstractList;
/**
* Created by Zsy on 2020/8/4.
*/
public class SingleCirecleLinkList<E> extends AbstractList<E> {
private Node<E> first;
private static class Node<E> {
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(element).append("_").append(next.element);
return sb.toString();
}
}
@Override
public void clear() {
this.first = null;
size = 0;
}
@Override
public E get(int index) {
return findNode(index).element;
}
public Node<E> findNode(int index) {
rangeCheck(index);
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
@Override
public E set(int index, E element) {
rangeCheck(index);
Node<E> node = findNode(index);
E oldNode = node.element;
node.element = element;
return oldNode;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == 0) {
Node<E> newNode = new Node<E>(element, first);
Node<E> lastNode = (size == 0) ? newNode : findNode(index - 1);
lastNode.next = newNode;
first = newNode;
} else {
Node<E> preNode = findNode(index - 1);
Node<E> newNode = new Node<E>(element, preNode.next);
preNode.next = newNode;
}
size++;
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> delNode = first;
if (index == 0) {
if (size == 1) {
first = null;
} else {
Node<E> lastNode = findNode(size - 1);
lastNode.next = first.next;
first = first.next;
}
} else {
Node<E> prevNode = findNode(index - 1);
delNode = prevNode.next;
prevNode.next = delNode.next;
}
size--;
return delNode.element;
}
@Override
public int indexOf(E element) {
Node<E> node = first;
if (element == null) {
for (int i = 0; i < size; i++) {
if (node == null) return i;
node = node.next;
}
} else {
for (int i = 0; i < size; i++) {
if (element.equals(node.element))//防止空指針異常
return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
@Override
public String toString() {
Node<E> node = this.first;
String statrStr = String.format("size: %d [", size);
StringBuilder result = new StringBuilder();
result.append(statrStr);
for (int i = 0; i < size; i++) {
if (i != 0) result.append(",");
result.append(node.element);
node = node.next;
}
result.append("]");
return result.toString();
}
}
雙向循環連結清單
圖解
實作
添加操作
正常添加
0索引位置添加
如下圖所示，操作步驟為：
1. 新結點指向首結點所指向的元素
2. 尾結點的next指針指向新結點
3. first指針指向新結點
正常添加
如下圖所示，操作步驟為：
1. 新結點指向指定索引的原結點及其前驅結點
2. 原結點的prev指針指向新結點
3. 原結點的前驅結點的next指針指向新結點
尾部添加
與首部添加同理，隻是将first指向新結點改為last指向新結點
因為是否是尾部添加的判定條件為:
index == size
尾部添加還需要考慮一個情況是目前連結清單為空的情況。具體情況如下圖所示，操作步驟為：
1. first和last都指向新結點
2. 新結點兩個指針都指向自己
實作代碼
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == size) {
Node<E> oldLastNode = last;
last = new Node<E>(oldLastNode, element, first);
if (oldLastNode == null) {
first = last;
first.next = first;
first.prev = first;
} else {
oldLastNode.next = last;
first.prev = last;
}
} else {
Node<E> node = findNode(index);
Node<E> prev = node.prev;
Node<E> newNode = new Node<E>(prev, element, node);
prev.next = newNode;
node.prev = newNode;
if (index == 0) {
first = newNode;
}
}
size++;
}
删除操作
删除操作的情況
1. 尾部删除：正常删除操作後，修改last指針指向即可
2. 首部删除：正常删除操作後，修改first指針指向即可
3. 正常删除
4. 隻剩下一個元素的删除：first、last指針都置空
實作代碼
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> delNode = findNode(index);
E removeNode = remove(delNode);
return removeNode;
}
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) {
first = next;
}
if (node == last) {
last = node;
}
}
size--;
return node.element;
}
練習案例
約瑟夫問題
如下圖所示，用雙向連結清單實作，每次指針挪動三步，并移除該元素的操作
實作步驟
1. 加入current指針
2. 添加删除方法
3. 添加初始化current方法
4. 添加重置current指針方法
實作核心代碼塊
private Node<E> current;
public void reset() {
current = first;
}
public E CurrentMoveToNext() {
if (CurrentIsNullPoint()) return null;
current = current.next;
System.out.println(" move to"+current.element);
return current.element;
}
public boolean CurrentIsNullPoint() {
return current == null;
}
public E removeCurrentNode() {
if (CurrentIsNullPoint()) return null;
Node<E> currentNext = current.next;
E removeValue = remove(current);
if (size == 0)
current=null;
else
current =currentNext;
return removeValue;
}