单项循环链表
图解
实现
步骤分析
由于之前已经写过了单链表单向链表，而单向循环链多数操作和单链表操作一致，所以我们只需基于之前的代码进行修改添加结点和删除结点的操作即可。
代码范例
添加操作
有元素的情况下，向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;
}