Version: Next

双向循环链表

定义

在双向链表的基础上

  • first的prev指向last
  • last的next指向first

image-20200917161552971

节点toString方法

@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
if (prev == null) {
stringBuilder.append("[null]");
} else {
stringBuilder.append("[").append(prev.element).append("]");
}
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 result = new StringBuilder("BiLinkedList{" +
"size=" + size + " | ");
if (first == null) { // 如果链表为空，不遍历直接打印空
result.append("null }");
return result.toString();
}
BiLinkedListNode<E> node = first;
for (int i = 0; i < size - 1; i++) {
result.append(node).append(" <-> ");
node = node.next;
}
result.append(node).append("}");
return result.toString();
}

add(int index, E element)方法

边界情况
  • 在末尾添加
    • 在末尾新建节点，prev为之前的last，next为first
    • first的prev更新为新的last
  • 在末尾添加且只有一个元素
    • first就是last
    • 循环链表，first的next是first，first的prev也是first
    • 让first的prev指向新的last
  • 不在末尾插入，且在最开头插入
    • 要插入节点的前驱节点就是last节点 || 后一个节点为first || index==0 三选一即可
    • first指向新插入的节点
// 向index位置插入一个元素
public void add(int index, E element) {
rangeCheckForAdd(index);
// 在最后面插入
if (index == size) {
// 在最后面插入新节点，新节点的next为first，prev为上一个last
// 最终插进去的节点变为了新的last
last = new BiLinkedListNode<>(element, last, first);
if (size == 0) { // 链表为空
first = last; // 唯一一个节点，头 尾都是它
first.next = last;
} else {
// 先前last的next指向新插入节点，也就是新的last节点
last.prev.next = last;
}
first.prev = last; // first的prev更新为新的last
} else { // 不是在最后面插入
// 找到index对应的节点
BiLinkedListNode<E> node = node(index);
BiLinkedListNode<E> preNode = node.prev; // 前一个节点
// 创建要插入的节点
BiLinkedListNode<E> insertNode = new BiLinkedListNode<>(element, preNode, node);
// 在最开头插入 || 后一个节点为first || index==0 三选一即可前一个节点
if (preNode == last) {
first = insertNode;
}
preNode.next = insertNode;
// 后一个节点的prev指向要插入的节点
node.prev = insertNode;
}
size++;
}

remove(int index) 方法

边界情况
  • 删除的是头节点
    • 原先first的next变为新的first
    • 新的first的prev为last
    • last的next变为新first
  • 删除的是尾节点
    • 原last的prev变为新last
    • 新last的next为first
    • first的prev设置为新的last
// 移除index位置的元素并返回
public E remove(int index) {
BiLinkedListNode<E> node = node(index);
E removedElement = node.element;
if (size == 1) { // 删除唯一节点
first = null;
last = null;
} else if (node == first) { // 删除的是头结点
first = node.next;
} else if (node == last) { // 删除的是尾结点
last = node.prev;
}
node.prev.next = node.next;
node.next.prev = node.prev;
size--;
return removedElement;
}