Внедряване на Java с циркулярно свързан списък

Програмиране

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. Вмъкване на елементи

Първата операция, която ще покрием, е вмъкването на нови възли. Докато вмъкваме нов елемент, ще трябва да се справим с два случая:

  • В главата възел е нула , че е не съществуват елементи вече добавено. В този случай ще направим новия възел, който добавяме като главата и опашката на списъка, тъй като има само един възел
  • В главата възел не е нула , тоест, има един или повече елементи, които вече добавени към списъка. В този случай съществуващата опашка трябва да сочи към новия възел и новодобавеният възел ще стане опашката

И в двата случая по-горе, 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. Изтриване на елемент

След това ще разгледаме операцията за изтриване. Подобно на вмъкването, имаме няколко случая (с изключение на случая, когато самият списък е празен), които трябва да разгледаме.

  • Елемент за изтриване е главата си . В този случай, ние трябва да се актуализира главата като на следващия възел на текущата глава , а на следващия възел на опашката за нов ръководител
  • Елемент за изтриване е всеки елемент, различен от главата . В този случай просто трябва да актуализираме следващия възел на предишния възел като следващия възел на възела, който трябва да бъде изтрит

Сега ще добавим нов метод deleteNode, който приема valueToDelete като параметър:

public void deleteNode(int valueToDelete) { Node currentNode = head; if (head != null) { if (currentNode.value == valueToDelete) { head = head.nextNode; tail.nextNode = head; } else { do { Node nextNode = currentNode.nextNode; if (nextNode.value == valueToDelete) { currentNode.nextNode = nextNode.nextNode; break; } currentNode = currentNode.nextNode; } while (currentNode != head); } } }

Нека сега добавим прост тест, за да проверим дали изтриването работи както се очаква за всички случаи:

@Test public void givenACircularLinkedList_WhenDeletingElements_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)); }

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.