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