«1. Введение
В этом руководстве мы рассмотрим реализацию кругового связанного списка в Java.
2. Циклический связанный список
Циклический связанный список — это вариант связанного списка, в котором последний узел указывает на первый узел, завершая полный круг узлов. Другими словами, этот вариант связанного списка не имеет пустого элемента в конце.
С этим простым изменением мы получаем некоторые преимущества:
-
Любой узел в циклическом связанном списке может быть отправной точкой Следовательно, весь список можно пройти, начиная с любого узла Поскольку последний узел циклического связанного списка имеет указатель на первый узел, легко выполнять операции постановки в очередь и удаления из очереди
В общем, это очень полезно при реализации структуры данных очереди.
С точки зрения производительности это то же самое, что и другие реализации связанных списков, за исключением одного: переход от последнего узла к головному узлу может выполняться за постоянное время. С обычными связанными списками это линейная операция.
3. Реализация на Java
Начнем с создания вспомогательного класса Node, в котором будут храниться значения int и указатель на следующий узел:
class Node {
int value;
Node nextNode;
public Node(int value) {
this.value = value;
}
}Теперь давайте создадим первый и последний узлы в циклическом соединении список, обычно называемый головой и хвостом:
public class CircularLinkedList {
private Node head = null;
private Node tail = null;
// ....
}В следующих подразделах мы рассмотрим наиболее распространенные операции, которые мы можем выполнять над круговым связанным списком.
3.1. Вставка элементов
Первая операция, которую мы рассмотрим, — это вставка новых узлов. При вставке нового элемента нам нужно будет обработать два случая:
-
Головной узел имеет значение null, то есть уже нет добавленных элементов. В этом случае мы сделаем новый узел, который мы добавляем, как головной, так и хвостовой части списка, поскольку есть только один узел. Головной узел не является нулевым, то есть один или несколько элементов уже добавлены в список. список. В этом случае существующий хвост должен указывать на новый узел, а вновь добавленный узел станет хвостом
В обоих вышеприведенных случаях nextNode для хвоста будет указывать на голову
Давайте создадим метод addNode, который принимает значение, которое будет вставлено в качестве параметра:
public void addNode(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
} else {
tail.nextNode = newNode;
}
tail = newNode;
tail.nextNode = head;
}Теперь мы можем добавить несколько чисел в наш круговой связанный список:
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. Поиск элемента
Следующей операцией, которую мы рассмотрим, является поиск, чтобы определить, присутствует ли элемент в списке.
Для этого зафиксируем узел в списке (обычно головной) как currentNode и пройдемся по всему списку, используя nextNode этого узла, пока не найдем нужный элемент.
Давайте добавим новый метод 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;
}
}Теперь добавим пару тестов, чтобы убедиться, что созданный выше список содержит добавленные нами элементы и не содержит новых: ~ ~~
@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. Удаление элемента
Далее мы рассмотрим операцию удаления.
Вообще говоря, после удаления элемента нам нужно обновить ссылку nextNode предыдущего узла, чтобы она указывала на ссылку nextNode удаленного узла.
Однако есть некоторые особые случаи, о которых нам нужно подумать:
-
Циклический связанный список имеет только один элемент, и мы хотим удалить этот элемент — в этом случае нам просто нужно установить головной узел и хвостовой узел в ноль Элемент, который нужно удалить, — это головной узел — мы должны сделать head.nextNode новым головным элементом. Удаляемый элемент — это хвостовой узел — нам нужно сделать предыдущий узел узла, который мы хотим удалить как новый конец
Давайте посмотрим на реализацию удаления элемента:
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);
}Давайте теперь создадим несколько тестов, чтобы убедиться, что удаление работает должным образом во всех случаях:
@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 . Обход списка
В этом заключительном разделе мы рассмотрим обход нашего кругового связанного списка. Подобно операциям поиска и удаления, для обхода мы фиксируем currentNode как головной и проходим по всему списку, используя nextNode этого узла.
Давайте добавим новый метод traverseList, который выводит элементы, добавленные в список:
public void traverseList() {
Node currentNode = head;
if (head != null) {
do {
logger.info(currentNode.value + " ");
currentNode = currentNode.nextNode;
} while (currentNode != head);
}
}
«
«Как мы видим, в приведенном выше примере при обходе мы просто печатаем значение каждого из узлов, пока не вернемся к головному узлу.
4. Заключение
В этом руководстве мы увидели, как реализовать круговой связанный список в Java, и рассмотрели некоторые из наиболее распространенных операций.
Во-первых, мы узнали, что такое круговой связанный список, включая некоторые из наиболее общих функций и отличий от обычного связанного списка. Затем мы увидели, как вставлять, искать, удалять и перемещаться элементы в нашей реализации кругового связанного списка.