单向循环链表

单向循环链表的尾节点的 next 指针不再是 null,而是指向链表的头节点,以形成环

单向循环链表

实现单向循环链表

相比单向链表,单向循环链表需要重写插入节点、删除节点两个方法

插入节点

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public void add(int index,E ele) {
    checkRangeForAdd(index);
    // 如果是向头节点插入,需要维护尾节点的 next,其他情况保持和单向链表的插入操作相同
    if(index == 0) {
        Node<E> newFirst = new Node<>(ele,first);
        // 如果插入新头节点时链表非空,正常调用 getNode()
        // 如果是空链表,不可调用 getNode,此时的尾节点就是要插入的新节点
        Node<E> last = size==0 ? newFirst : getNode(size-1);
        // 尾节点的 next 指向新的头节点
        last.next = newFirst;
        first = newFirst;
    }else {
        // 对于尾节点的插入自动维护了 next
        Node<E> prev = getNode(index-1);
        prev.next = new Node<>(ele,prev.next);
    }
    size++;
}

删除节点

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public E remove(int index) {
    checkRange(index);
    Node<E> node;
    if(index == 0) {
        // 取出头节点
        node = first;
        if(size==1) {
            // 如果链表只有一个元素,直接置空first指针即可
            first = null;
        }else {
            // 如果链表不知一个元素,要拿到尾节点
            // 注意:因为getNode()方法是从first位置开始向后遍历的,所以不能先修改first的值
            getNode(size-1).next = first.next;
            first = first.next;
        }
    }else {
        Node<E> prev = getNode(index-1);
        node = prev.next;
        prev.next = node.next;
    }
    size--;
    return node.element;
}

双向循环链表

双向循环链表的头节点的 prev 不再是 null,而是指向尾节点 双向循环链表的尾节点的 next 不再是 null,而是指向头节点

双向循环链表

实现双向循环链表

相比双向链表,双向循环链表需要重写插入节点、删除节点两个方法

插入节点

插入节点需要对添加第一个节点和添加尾节点进行特殊处理

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 添加元素
public void add(int index,E ele) {
    checkRangeForAdd(index);
    // 向链表尾部添加元素
    if(index==size) {
        // 取出原最后一个节点
        Node<E> oldLast = last;
        // 新的last的next不再是null,而是指向first
        last = new Node<>(oldLast,ele,first);
        // 如果原链表是空的,即要添加的元素是第一个元素
        if(oldLast==null) {
            last.next = last;
            last.prev = last;
            first = last;
        }else {
            oldLast.next = last;
            first.prev = last;
        }
    // 向链表其他位置添加元素
    }else {
        // 原来位置的节点作为后继
        Node<E> next = getNode(index);
        // 原来位置的节点的前驱作为新节点的前驱
        Node<E> prev = next.prev;
        // 创建新节点
        Node<E> node = new Node<>(prev,ele,next);
        // 非空循环链表,节点的next一定不为空
        next.prev = node;
        // 非空循环链表,节点的prev一定不为空
        prev.next = node;
        // 如果插入到第一个位置,也就是说 index==0
        // 即要插入节点next是之前的first,插入后要修改新的first
        if(next==first) {
            first = node;
        }
    }
    size ++;
}

删除节点

  • 删除节点,就是在环上去掉某一个节点,然后根据删除的节点是头节点或者尾节点来处理first 和 last
  • 链表只有一个节点时同样需要特殊处理
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 删除元素
public E remove(int index) {
    checkRange(index);
    // 获取要删除的节点
    Node<E> node = getNode(index);
    // 如果链表只有一个节点,其前驱和后继都是自己本身,重新设置不会断掉引用
    if(size==1) {
        first = null;
        last = null;
    // 链表不只一个节点
    }else {
        Node<E> prev = node.prev;
        Node<E> next = node.next;
        prev.next = next;
        next.prev = prev;
        // 如果删除的是头尾节点,还需要维护first或者last
        if(node == first) {
            first = next;
        }
        if(node == last) {
            last = prev;
        }
    }
    size --;
    return node.element;
}

参考