Circular Linked List Java Implementation – 循环链接列表的Java实现

1. Introduction

1.绪论

In this tutorial, we’ll look at the implementation of a circular linked list in Java.

在本教程中，我们将看一下Java中循环链表的实现。

2. Circular Linked List

2.循环链接列表

A circular linked list is a variation of a linked list in which the last node points to the first node, completing a full circle of nodes. In other words, this variation of the linked list doesn’t have a null element at the end.

循环链接列表是链接列表的一种变体，其中最后一个节点指向第一个节点，完成了一个完整的节点循环。换句话说，这个变体的链接列表在最后没有null元素。

With this simple change, we gain some benefits:

通过这一简单的改变，我们获得了一些好处。

• Any node in the circular linked list can be a starting point
• Consequently, the whole list can be traversed starting from any node
• Since the last node of the circular linked list has the pointer to the first node, it’s easy to perform enqueue and dequeue operations

All in all, this is very useful in the implementation of the queue data structure.

总而言之，这在队列数据结构的实现中非常有用。

Performance-wise, it is the same as other linked list implementations except for one thing: Traversing from the last node to the head node can be done in constant time. With conventional linked lists, this is a linear operation.

从性能上讲，它与其他链接列表的实现是一样的，除了一点：从最后一个节点到头部节点的遍历可以在恒定时间内完成。对于传统的链表，这是一个线性操作。

3. Implementation in Java

3.用Java实现

Let’s start by creating an auxiliary Node class that will store int values and a pointer to the next node:

让我们先创建一个辅助的Node类，它将存储int值和一个指向下一个节点的指针：。

class Node {

    int value;
    Node nextNode;

    public Node(int value) {
        this.value = value;
    }
}

Now let’s create the first and last nodes in the circular linked list, usually called the head and tail:

现在让我们创建循环链接列表中的第一个和最后一个节点，通常称为head和tail：。

public class CircularLinkedList {
    private Node head = null;
    private Node tail = null;

    // ....
}

In the next subsections we’ll take a look at the most common operations we can perform on a circular linked list.

在接下来的几个小节中，我们将看看我们可以在循环链表上执行的最常见的操作。

3.1. Inserting Elements

3.1.插入元素

The first operation we’re going to cover is the insertion of new nodes. While inserting a new element we’ll need to handle two cases :

我们要讨论的第一个操作是插入新节点。在插入一个新元素时，我们需要处理两种情况。

• The head node is null, that is there are no elements already added. In this case, we’ll make the new node we add as both the head and tail of the list since there is only one node
• The head node isn’t null, that is to say, there are one or more elements already added to the list. In this case, the existing tail should point to the new node and the newly added node will become the tail

In both of the above cases, the nextNode for tail will point to head

在上述两种情况下，nextNode的tail将指向head。

Let’s create an addNode method that takes the value to be inserted as a parameter:

让我们创建一个addNode方法，把要插入的value作为一个参数。

public void addNode(int value) {
    Node newNode = new Node(value);

    if (head == null) {
        head = newNode;
    } else {
        tail.nextNode = newNode;
    }

    tail = newNode;
    tail.nextNode = head;
}

Now we can add a few numbers to our circular linked list:

现在我们可以向我们的循环链接列表添加一些数字。

private CircularLinkedList createCircularLinkedList() {
    CircularLinkedList cll = new CircularLinkedList();

    cll.addNode(13);
    cll.addNode(7);
    cll.addNode(24);
    cll.addNode(1);
    cll.addNode(8);
    cll.addNode(37);
    cll.addNode(46);

    return cll;
}

3.2. Finding an Element

3.2.寻找一个元素

The next operation we’ll look at is searching to determine if an element is present in the list.

我们要看的下一个操作是搜索，以确定一个元素是否存在于列表中。

For this, we’ll fix a node in the list (usually the head) as the currentNode and traverse through the entire list using the nextNode of this node, until we find the required element.

为此，我们将固定列表中的一个节点（通常是head）作为currentNode，并使用这个节点的nextNode遍历整个列表，直到我们找到所需的元素。

Let’s add a new method containsNode that takes the searchValue as a parameter:

让我们添加一个新的方法containsNode，它以searchValue为参数。

public boolean containsNode(int searchValue) {
    Node currentNode = head;

    if (head == null) {
        return false;
    } else {
        do {
            if (currentNode.value == searchValue) {
                return true;
            }
            currentNode = currentNode.nextNode;
        } while (currentNode != head);
        return false;
    }
}

Now, let’s add a couple of tests to verify that the above-created list contains the elements we added and no new ones:

现在，让我们添加几个测试来验证上述创建的列表是否包含我们添加的元素，而没有新的元素。

@Test
 public void givenACircularLinkedList_WhenAddingElements_ThenListContainsThoseElements() {
    CircularLinkedList cll = createCircularLinkedList();

    assertTrue(cll.containsNode(8));
    assertTrue(cll.containsNode(37));
}

@Test
public void givenACircularLinkedList_WhenLookingForNonExistingElement_ThenReturnsFalse() {
    CircularLinkedList cll = createCircularLinkedList();

    assertFalse(cll.containsNode(11));
}

3.3. Deleting an Element

3.3.删除一个元素

Next, we’ll look at the delete operation.

接下来，我们来看看删除操作。

Generally speaking, after we delete an element, we need to update the nextNode reference of the previous node to point to the nextNode reference of the node that has been deleted.

一般来说，在我们删除一个元素后，我们需要更新前一个节点的nextNode引用，以指向被删除的节点的nextNode引用。

However, there are some special cases we need to think about:

然而，有一些特殊情况我们需要考虑。

• The circular linked list has only one element, and we want to remove the element – In this case, we just need to set the head node and tail node to null
• The element to delete is the head node – We must make head.nextNode as the new head
• The element to delete is the tail node – We need to make the previous node of the node we want to delete as the new tail

Let’s take a look at the implementation of deleting an element:

让我们来看看删除一个元素的实现。

public void deleteNode(int valueToDelete) {
    Node currentNode = head;
    if (head == null) { // the list is empty
        return;
    }
    do {
        Node nextNode = currentNode.nextNode;
        if (nextNode.value == valueToDelete) {
            if (tail == head) { // the list has only one single element
                head = null;
                tail = null;
            } else {
                currentNode.nextNode = nextNode.nextNode;
                if (head == nextNode) { //we're deleting the head
                    head = head.nextNode;
                }
                if (tail == nextNode) { //we're deleting the tail
                    tail = currentNode;
                }
            }
            break;
        }
        currentNode = nextNode;
    } while (currentNode != head);
}

Let’s now create some tests to verify that deletion works as expected for all the cases:

现在，让我们创建一些测试，以验证在所有情况下，删除工作都是预期的。

@Test
public void givenACircularLinkedList_WhenDeletingInOrderHeadMiddleTail_ThenListDoesNotContainThoseElements() {
    CircularLinkedList cll = createCircularLinkedList();

    assertTrue(cll.containsNode(13));
    cll.deleteNode(13);
    assertFalse(cll.containsNode(13));

    assertTrue(cll.containsNode(1));
    cll.deleteNode(1);
    assertFalse(cll.containsNode(1));

    assertTrue(cll.containsNode(46));
    cll.deleteNode(46);
    assertFalse(cll.containsNode(46));
}

@Test
public void givenACircularLinkedList_WhenDeletingInOrderTailMiddleHead_ThenListDoesNotContainThoseElements() {
    CircularLinkedList cll = createCircularLinkedList();

    assertTrue(cll.containsNode(46));
    cll.deleteNode(46);
    assertFalse(cll.containsNode(46));

    assertTrue(cll.containsNode(1));
    cll.deleteNode(1);
    assertFalse(cll.containsNode(1));

    assertTrue(cll.containsNode(13));
    cll.deleteNode(13);
    assertFalse(cll.containsNode(13));
}

@Test
public void givenACircularLinkedListWithOneNode_WhenDeletingElement_ThenListDoesNotContainTheElement() {
    CircularLinkedList cll = new CircularLinkedList();
    cll.addNode(1);
    cll.deleteNode(1);
    assertFalse(cll.containsNode(1));
}

3.4. Traversing the List

3.4.遍历列表

We’re going to take a look at the traversal of our circular linked list in this final section. Similar to the search and delete operations, for traversal we fix the currentNode as head and traverse through the entire list using the nextNode of this node.

在这最后一节中，我们要看一下循环链接列表的遍历。与搜索和删除操作类似，对于遍历，我们将currentNode固定为head，并使用该节点的nextNode遍历整个列表。

Let’s add a new method traverseList that prints the elements that are added to the list:

让我们添加一个新的方法traverseList，打印出被添加到列表中的元素。

public void traverseList() {
    Node currentNode = head;

    if (head != null) {
        do {
            logger.info(currentNode.value + " ");
            currentNode = currentNode.nextNode;
        } while (currentNode != head);
    }
}

As we can see, in the above example, during the traversal, we simply print the value of each of the nodes, until we get back to the head node.

我们可以看到，在上面的例子中，在遍历过程中，我们只是简单地打印每个节点的值，直到我们回到头部节点。

4. Conclusion

4.总结

In this tutorial, we’ve seen how to implement a circular linked list in Java and explored some of the most common operations.

在本教程中，我们已经看到了如何在Java中实现循环链表，并探索了一些最常见的操作。

First, we learned what exactly a circular linked list is including some of the most common features and differences with a conventional linked list. Then, we saw how to insert, search, delete and traverse items in our circular linked list implementation.

首先，我们了解了什么是循环链表，包括一些最常见的特征以及与传统链表的区别。然后，我们看到如何在我们的循环链表实现中插入、搜索、删除和遍历项目。

As usual, all the examples used in this article are available over on GitHub.

像往常一样，本文使用的所有例子都可以在GitHub上找到。。