1、单向循环链表
image.png
当单向循环链表只有一个元素的情况时，链表的结构如下
image.png
从单向循环链表的结构看来，只要不是在链表的头或尾进行增加和删除操作，单向循环链表的添加和删除和单向链表是相同的，需要处理的就是头尾的特殊情况。
1.1、单向循环链表的add
public void add(int index, E element) {
checkIndexForAdd(index);
if (index == 0) {
if (size == 0) {
first = new Node<>(element, null);
first.next = first;
} else {
Node<E> lastNode = nodeIndex(size - 1);
first = new Node<E>(element, first);
lastNode.next = first;
}
} else {
Node<E> preNode = nodeIndex(index - 1);
preNode.next = new Node<>(element, preNode.next);
}
size++;
}
1.2、单向循环链表的remove
public E remove(int index) {
checkIndex(index);
Node<E> oldNode = first;
if (index == 0) {
if (size == 1) {
first = null;
} else {
first = first.next;
Node<E> lastNode = nodeIndex(size - 1);
lastNode.next = first;
}
} else {
Node<E> preNode = nodeIndex(index - 1);
oldNode = preNode.next;
preNode.next = preNode.next.next;
}
size--;
return oldNode.element;
}
至此单向循环链表中接口方法已处理完毕，完整代码如下：
public class SingleCircleLinkedList<E> extends AbstractList<E> {
private Node<E> first;
private static class Node<E> {
private E element;
private Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
@Override
public void add(int index, E element) {
checkIndexForAdd(index);
if (index == 0) {
if (size == 0) {
first = new Node<>(element, null);
first.next = first;
} else {
Node<E> lastNode = nodeIndex(size - 1);
first = new Node<E>(element, first);
lastNode.next = first;
}
} else {
Node<E> preNode = nodeIndex(index - 1);
preNode.next = new Node<>(element, preNode.next);
}
size++;
}
/**
* 查找位置为index的元素
*/
private Node<E> nodeIndex(int index) {
checkIndex(index);
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
@Override
public E get(int index) {
Node<E> node = nodeIndex(index);
return node.element;
}
@Override
public E set(int index, E element) {
Node<E> node = nodeIndex(index);
E old = node.element;
node.element = element;
return old;
}
@Override
public E remove(int index) {
checkIndex(index);
Node<E> oldNode = first;
if (index == 0) {
if (size == 1) {
first = null;
} else {
first = first.next;
Node<E> lastNode = nodeIndex(size - 1);
lastNode.next = first;
}
} else {
Node<E> preNode = nodeIndex(index - 1);
oldNode = preNode.next;
preNode.next = preNode.next.next;
}
size--;
return oldNode.element;
}
@Override
public int indexOf(E element) {
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == null)
return i;
node = node.next;
}
} else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (element.equals(node.element))
return i;
node = node.next;
}
}
return -1;
}
@Override
public void clear() {
first = null;
size = 0;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("size=" + size + " [");
Node<E> node = first;
for (int i = 0; i < size; i++) {
sb.append(node.element).append("_");
sb.append(node.next.element);
if (i != size - 1)
sb.append(" , ");
node = node.next;
}
sb.append("]");
return sb.toString();
}
}
2、双向循环链表
image.png
双向循环链表只有一个节点时，链表的结构如下：
image.png
2.1、双向循环链表的add
public void add(int index, E element) {
checkIndexForAdd(index);
if (index == size) {
Node<E> newNode = new Node<>(last, element, first);
if (size == 0) {
first = newNode;
last = newNode;
newNode.prev = newNode;
newNode.next = newNode;
} else {
last.next = newNode;
last = newNode;
first.prev = last;
}
} else {
Node<E> nextNode = nodeIndex(index);
Node<E> preNode = nextNode.prev;
Node<E> newNode = new Node<>(preNode, element, nextNode);
preNode.next = newNode;
nextNode.prev = newNode;
if (index == 0) // 在向头部添加元素
first = newNode;
}
size++;
}
2.2、双向循环链表的remove
public E remove(int index) {
checkIndex(index);
Node<E> oldNode = first;
if (size == 1) {
first = null;
last = null;
} else {
oldNode = nodeIndex(index);
Node<E> preNode = oldNode.prev;
Node<E> nexNode = oldNode.next;
preNode.next = nexNode;
nexNode.prev = preNode;
if (index == 0) {
first = nexNode;
} else if (index == size - 1) {
last = preNode;
}
}
size--;
return oldNode.element;
}
2.3、完整代码
public class CircleLinkedList<E> extends AbstractList<E> {
private Node<E> first;
private Node<E> last;
private static class Node<E> {
private E element;
private Node<E> next;
private Node<E> prev;
public Node(Node<E> prev, E element, Node<E> next) {
this.element = element;
this.next = next;
this.prev = prev;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(prev == null ? null : prev.element).append("_");
sb.append(element).append("_");
sb.append(next == null ? null : next.element);
return sb.toString();
}
}
@Override
public void add(int index, E element) {
checkIndexForAdd(index);
if (index == size) {
Node<E> newNode = new Node<>(last, element, first);
if (size == 0) {
first = newNode;
last = newNode;
newNode.prev = newNode;
newNode.next = newNode;
} else {
last.next = newNode;
last = newNode;
first.prev = last;
}
} else {
Node<E> nextNode = nodeIndex(index);
Node<E> preNode = nextNode.prev;
Node<E> newNode = new Node<>(preNode, element, nextNode);
preNode.next = newNode;
nextNode.prev = newNode;
if (index == 0) // 在向头部添加元素
first = newNode;
}
size++;
}
/**
* 查找位置为index的元素
*/
private Node<E> nodeIndex(int index) {
checkIndex(index);
Node<E> node = first;
if (index <= size >> 1) {
for (int i = 0; i < index; i++) {
node = node.next;
}
} else {
node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
}
return node;
}
@Override
public E get(int index) {
Node<E> node = nodeIndex(index);
return node.element;
}
@Override
public E set(int index, E element) {
Node<E> node = nodeIndex(index);
E old = node.element;
node.element = element;
return old;
}
@Override
public E remove(int index) {
checkIndex(index);
Node<E> oldNode = first;
if (size == 1) {
first = null;
last = null;
} else {
oldNode = nodeIndex(index);
Node<E> preNode = oldNode.prev;
Node<E> nexNode = oldNode.next;
preNode.next = nexNode;
nexNode.prev = preNode;
if (index == 0) {
first = nexNode;
} else if (index == size - 1) {
last = preNode;
}
}
size--;
return oldNode.element;
}
@Override
public int indexOf(E element) {
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == null)
return i;
node = node.next;
}
} else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (element.equals(node.element))
return i;
node = node.next;
}
}
return -1;
}
@Override
public void clear() {
first = null;
last = null;
size = 0;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("size=" + size + " ，first=" + (first == null ? null : first.element) + " ,last="
+ (last == null ? null : last.element) + " [");
Node<E> node = first;
for (int i = 0; i < size; i++) {
sb.append(node);
if (i != size - 1)
sb.append(" , ");
node = node.next;
}
sb.append("]");
return sb.toString();
}
}
3、练习
3.1、解决约瑟夫问题。
约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。比如N=8，M=3，则被杀的顺序如下：3->6->1->5->2->8->4->7
image.png
下面看下如何使用循环双向链表来解决约瑟夫问题，要解决这个问题，我们需要给双向循环链表增加如下几个方法：
- 1、current用于指向某个节点
- 2、void reset()：让current指向头结点
- 3、E next()：让current向后走一步
- 4、remove()：删除current指向的节点，并让current向后移动一步
在双向链表中加入上面接口的实现
public void reset() {
current = first;
}
public E next() {
if (current == null)
return null;
current = current.next;
return current.element;
}
public E remove() {
if (current == null)
return null;
Node<E> nexNode = current.next;
E element = remove(current.element);
if (size == 0)
current = null;
else
current = nexNode;
return element;
}
测试代码如下：
CircleLinkedList2<Integer> list = new CircleLinkedList2<Integer>();
for (int i = 1; i < 9; i++) {
list.add(i);
}
list.reset();
while(!list.isEmpty()) {
list.next();
list.next();
System.out.println(list.remove());
}
输出结果如下
3->6->1->5->2->8->4->7
网友评论