数据结构与算法（第一季）：循环链表

一、单向循环链表

• 尾节点的next，指向头节点。

image

二、单向循环链表接口设计

• 相较于单项链表，单向循环链表需要重写插入节点、删除节点两个方法。

三、单向循环链表的实现

1、插入节点

• 插入节点，需要特别关注插入头节点的情况。此时需要拿到尾节点，然后将其next指向新节点。

public void add(int index, E element) {
    rangeCheckForAdd(index);

    if (index == 0) {
        Node<E> newFirst = new Node<>(element, first);
        // 拿到最后一个节点
        Node<E> last = (size == 0) ? newFirst : node(size - 1);
        last.next = newFirst;
        first = newFirst;
    } else {
        Node<E> prev = node(index - 1);
        prev.next = new Node<>(element, prev.next);
    }
    size++;
}
复制代码

2、删除节点

• 如果删除的是头节点，删除后需让last指向新的头节点。
• 当只有一个节点并删除时, first指向null。

public E remove(int index) {
    rangeCheck(index);

    Node<E> node = first;
        //删除头节点
        if (index == 0) {
            // 只有一个节点
            if (size == 1) {
                first = null;
            } else {
                Node<E> last = node(size - 1);
                first = first.next;
                last.next = first;
            }
        } else {
            Node<E> prev = node(index - 1);
            node = prev.next;
            prev.next = node.next;
        }
        size--;
        return node.element;
    }
复制代码

四、双向循环链表

• 头节点的prev指向尾节点。
• 尾节点的next指向头节点。

image

五、双向循环链表接口设计

• 相较于双向链表，双向循环链表需要重写插入节点、删除节点两个方法。

六、双向循环链表接的实现

1、插入节点

• 需特殊处理添加第一个元素和添加到尾节点两种特殊情况。

public void add(int index, E element) {
    rangeCheckForAdd(index);
    // 如果 index == size, 说明添加的索引是最后位置
    if (index == size) {
        // 创建新节点, prev指向原链表的尾节点, next指向首节点
        Node<E> node = new Node<>(last, element, first);
        // 当原链表没有任何节点
        if (size == 0) {
            first = node;
            last = node;
            node.prev = node;
            node.next = node;
        }else {
            // 原链表尾节点next指向node
            last.next = node;
            // 原链表头结点prev指向node
            first.prev = node;
            // last指向新的尾节点
            last = node;
        }
    }else {
        // 添加新节点后的下一个节点
        Node<E> next = node(index);
        // 添加新节点后的上一个节点
        Node<E> prev = next.prev;
        // 创建新节点, 新节点的上一个节点时prev, 新节点的下一个节点是next
        Node<E> node = new Node<>(prev, element, next);
        // next的上一个节点是新节点
        next.prev = node;
        // prev的下一个节点是新节点
        prev.next = node;
        // 当next == first时, 说明新添加节点的索引是0
        if (next == first) { 
            first = node;
        }
    }
    size++;
}
复制代码

2、删除节点

• 删除节点，就是在环上去掉某一个节点，然后根据删除的节点是首节点或者尾节点来处理first和last。
• 需要特殊处理只有一个节点的删除操作。

public E remove(int index) {
    // 需要删除的节点
    Node<E> node = node(index); 
    if (size == 1) {
        first = null;
        last = null;
    }else {
        // 删除节点的前一个节点
        Node<E> prev = node.prev;
        // 删除节点的后一个节点
        Node<E> next = node.next;
        next.prev = prev;
        prev.next = next;
        // 如果node == first, 说明删除的是第一个节点
        if (node == first) {
            first = next;
        }
        // 如果next == last, 说明删除的是最后一个节点
        if (next == last) {
            last = prev;
        }   
    }
    size--;
    return node.element;
}
复制代码