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 , то есть уже добавленных элементов нет. В этом случае мы сделаем новый узел, который мы добавляем, иголовой, ихвостомсписка, поскольку есть только один узел. - Головной
узелне равен 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. Поиск элемента
Следующая операция, которую мы рассмотрим, — это поиск, чтобы определить, присутствует ли элемент в списке.
Для этого мы зафиксируем узел в списке (обычно head ) как 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, и рассмотрели некоторые из наиболее распространенных операций.
Во-первых, мы узнали, что такое круговой связанный список, включая некоторые из наиболее общих функций и отличий от обычного связанного списка. Затем мы увидели, как вставлять, искать, удалять и перемещаться элементы в нашей реализации кругового связанного списка.
Как обычно, все примеры, использованные в этой статье, доступны на GitHub.