Version: Next

单向循环链表

定义
  • 单向链表
  • 最后一个节点的next指向头节点first

image-20200917124546364

与单项链表对比

需要修改：

  • 添加方法
  • 删除方法

节点toString方法

@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[").append(element).append("]");
if (next == null) {
stringBuilder.append("[null]");
} else {
stringBuilder.append("[").append(next.element).append("]");
}
return stringBuilder.toString();
}

单向循环链表toString方法

@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("SingleCycleLinkedList{" + "size=")
.append(size)
.append(" | { ");
if (size == 0) {
stringBuilder.append("null}");
return stringBuilder.toString();
} else {
LinkedListNode<E> node = this.first;
for (int i = 0; i < size - 1; i++) {
stringBuilder.append(node).append(" -> ");
node = node.next;
}
stringBuilder.append(node).append(" }");
}
return stringBuilder.toString();
}

add(int index, E element方法)

在头部插入的情况

  • 记录当前first节点的element值
  • 用要插入的节点的element值，替换当前first节点的element值
  • 建立新节点，值为原先first的值，next为原先first的next
  • first的next指向新节点

整个单向循环链表只有一个节点

  • 这个节点的next指向自己
// 向index位置插入一个元素
public void add(int index, E element) {
rangeCheckForAdd(index);
LinkedListNode<E> insertNode;
if (index == 0) { // 在头部插入
if (size == 0) { // 空链表，插进去唯一节点，自己指向自己
insertNode = new LinkedListNode<>(element, null);
insertNode.next = insertNode;
first = insertNode;
} else {
E firstElement = first.element; // 记录当前first的值
first.element = element; // 用要插入的节点的element值，替换当前first的element值
// 建立新节点，值为原先first的值，next为原先first的next
insertNode = new LinkedListNode<>(firstElement, first.next);
first.next = insertNode;
}
} else {
LinkedListNode<E> preNode = node(index - 1);
preNode.next = new LinkedListNode<>(element, preNode.next);
}
size++;
}

remove(int index)方法

边界情况，在头部删除

采用移形换位的思想，直接用下一个的值把要删除的节点的值换了

  • 把first的next的值复制到first来
  • 让first的next指向first.next的next
// 移除index位置的元素并返回
public E remove(int index) {
E removedElement = null;
if (index == 0) { // 头部删除
removedElement = first.element; // 记录被删除的值
first.element = first.next.element; // 把first的next的值复制到first上
first.next = first.next.next; // 让first的next指向first的next的next
} else {
LinkedListNode<E> preNode = node(index - 1);
removedElement = preNode.next.element;
preNode.next = preNode.next.next;
}
size--;
return removedElement;
}