循环链表

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