Обръщане на свързан списък в Java

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

1. Въведение

В този урок ще внедрим два свързани алгоритма за обръщане на списъци в Java.

2. Структура на данните от свързания списък

Свързаният списък е линейна структура от данни, при която указател във всеки елемент определя реда. Всеки елемент от свързан списък съдържа поле за данни за съхраняване на данните от списъка и поле за указател, което да сочи към следващия елемент в последователността. Също така можем да използваме указател за глава, за да сочим към началния елемент на свързан списък:

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

В Java имаме клас LinkedList, за да осигурим двойно свързано изпълнение на списъка на интерфейсите List и Deque . В този урок обаче ще използваме обща структура на данните от списъка с единични връзки.

Нека първо започнем с клас ListNode, за да представим елемент от свързан списък:

public class ListNode { private int data; private ListNode next; ListNode(int data) { this.data = data; this.next = null; } // standard getters and setters }

Класът ListNode има две полета:

  • Целочислена стойност за представяне на данните на елемента
  • Указател / препратка към следващия елемент

Свързаният списък може да съдържа множество обекти на ListNode . Например можем да изградим горния примерен свързан списък с цикъл:

ListNode constructLinkedList() { ListNode head = null; ListNode tail = null; for (int i = 1; i <= 5; i++) { ListNode node = new ListNode(i); if (head == null) { head = node; } else { tail.setNext(node); } tail = node; } return head; }

3. Прилагане на итеративен алгоритъм

Нека внедрим итеративния алгоритъм в Java:

ListNode reverseList(ListNode head) { ListNode previous = null; ListNode current = head; while (current != null) { ListNode nextElement = current.getNext(); current.setNext(previous); previous = current; current = nextElement; } return previous; }

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

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

Можем да проверим това итеративно изпълнение с обикновен единичен тест:

@Test public void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult() { ListNode head = constructLinkedList(); ListNode node = head; for (int i = 1; i <= 5; i++) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } LinkedListReversal reversal = new LinkedListReversal(); node = reversal.reverseList(head); for (int i = 5; i>= 1; i--) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } }

В този единичен тест първо изграждаме примерен свързан списък с пет възли. Също така проверяваме дали всеки възел в свързания списък съдържа правилната стойност на данните. След това извикваме итерационната функция за обръщане на свързания списък. Накрая проверяваме обратния свързан списък, за да се уверим, че данните са обърнати, както се очаква.

4. Прилагане на рекурсивен алгоритъм

Сега, нека внедрим рекурсивния алгоритъм в Java:

ListNode reverseListRecursive(ListNode head) { if (head == null) { return null; } if (head.getNext() == null) { return head; } ListNode node = reverseListRecursive(head.getNext()); head.getNext().setNext(head); head.setNext(null); return node; }

Във функцията reverseListRecursive ние рекурсивно посещаваме всеки елемент от свързания списък, докато достигнем последния. Този последен елемент ще стане новата глава на обърнатия свързан списък. Също така добавяме посетения елемент в края на частично обърнатия свързан списък.

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

@Test public void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult() { ListNode head = constructLinkedList(); ListNode node = head; for (int i = 1; i <= 5; i++) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } LinkedListReversal reversal = new LinkedListReversal(); node = reversal.reverseListRecursive(head); for (int i = 5; i>= 1; i--) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } }

5. Заключение

В този урок внедрихме два алгоритма за обръщане на свързан списък. Както винаги, изходният код на статията е достъпен в GitHub.