Структури на данни и алгоритми в Java, Част 5: Двойно свързани списъци

Макар че едносвързаните списъци имат много приложения, те също представляват някои ограничения. Първо, единично свързаните списъци ограничават обхождането на възела до една посока: не можете да прехвърлите еднопосочно свързан списък назад, освен ако първо не обърнете връзките му към възли, което отнема време. Ако направите обратно обхождане и трябва да възстановите обхождането на възела в първоначалната посока, ще трябва да повторите обръщането, което отнема повече време. Единично свързани списъци също ограничават изтриването на възли. В този тип списък не можете да изтриете произволен възел без достъп до предшественика на възела.

За щастие, Java предлага няколко вида списък, който можете да използвате за търсене и сортиране на съхранени данни във вашите Java програми. Този последен урок от поредицата Структури на данни и алгоритми въвежда търсене и сортиране с двойно свързани списъци и списъци с кръгова връзка. Както ще видите, тези две категории на структурата на данни се основават на единично свързани списъци, за да предложат по-широк спектър от поведение при търсене и сортиране във вашите Java програми.

Двойно свързани списъци

А двойно свързан списък е свързан списък на възли, където всеки възел има двойка полета връзка. Едното поле за връзка ви позволява да прекосите списъка в посока напред, докато другият възел ви позволява да прегледате списъка в обратна посока. За посоката напред референтната променлива съдържа препратка към първия възел. Всеки възел се свързва със следващия възел чрез полето за връзка „next”, с изключение на последния възел, чието поле „next” link съдържа нулевата препратка, за да обозначи края на списъка (в посока напред). Посоката назад се работи по подобен начин. Референтната променлива съдържа препратка към последния възел на посоката напред, който вие интерпретирате като първия възел. Всеки възел се свързва с предишния възел чрез полето за връзката "предишен". "Предишният" на първия възелполето link съдържа null, за да означава края на списъка.

Опитайте се да мислите за двойно свързан списък като за двойка единично свързани списъци, като всеки свързва едни и същи възли. Диаграмата на фигура 1 показва topForward-реферирани и topBackward-реферирани единично свързани списъци.

CRUD операции в двойно свързани списъци

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

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next DECLARE Node prev END DECLARE DECLARE Node topForward DECLARE Node temp DECLARE Node topBackward topForward = NEW Node topForward.name = "A" temp = NEW Node temp.name = "B" topBackward = NEW Node topBackward.name = "C" // Create forward singly-linked list topForward.next = temp temp.next = topBackward topBackward.next = NULL // Create backward singly-linked list topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Delete Node B. temp.prev.next = temp.next; // Bypass Node B in the forward singly-linked list. temp.next.prev = temp.prev; // Bypass Node B in the backward singly-linked list. END 

Примерно приложение: CRUD в двойно свързан списък

Примерното приложение Java DLLDemoдемонстрира как да създавате, вмъквате и изтривате възли в двойно свързан списък. Изходният код на приложението е показан в Листинг 1.

Листинг 1. Java приложение, демонстриращо CRUD в двойно свързан списък

 public final class DLLDemo { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Reference node B. temp = topForward.next; // Delete node B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Dump forward singly-linked list. System.out.print("Forward singly-linked list (after deletion): "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list (after deletion): "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } } 

Компилирайте списък 4, както следва:

 javac DLLDemo.java 

Стартирайте полученото приложение, както следва:

 java DLLDemo 

Трябва да наблюдавате следния изход:

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list (after deletion): AC Backward singly-linked list (after deletion): CA 

Разбъркване в двойно свързани списъци

Java Collections Framework включва Collectionsклас полезни методи, който е част от java.utilпакета. Този клас включва void shuffle(List list)метод, който „ произволно пермутира посочения списък, използвайки източник на произволност по подразбиране “. Например, можете да използвате този метод, за да разбъркате тесте карти, изразени като двойно свързан списък ( java.util.LinkedListкласът е пример). В псевдокода по-долу можете да видите как алгоритъмът за разбъркване може да разбърка двойно свързан списък:

 DECLARE RANDOM rnd = new RANDOM DECLARE INTEGER i FOR i = 3 DOWNTO 2 swap(topForward, i - 1, rnd.nextInt(i)) END FOR FUNCTION swap(Node top, int i, int j) DECLARE Node nodei, nodej DECLARE INTEGER k // Locate ith node. Node nodei = top FOR k = 0 TO i - 1 nodei = nodei.next END FOR // Locate jth node. Node nodej = top FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Perform the swap. DECLARE STRING namei = nodei.name DECLARE STRING namej = nodej.name nodej.name = namei nodei.name = namej END FUNCTION END 

Алгоритъмът за разбъркване получава източник на случайност и след това обхожда списъка назад, от последния възел до втория. Той многократно сменя произволно избран възел (който всъщност е само полето с името) в „текущата позиция“. Възлите се избират на случаен принцип от частта от списъка, която тече от първия възел до текущата позиция, включително. Имайте предвид, че този алгоритъм е грубо извлечен от void shuffle(List list)изходния код на.

Псевдокодът на алгоритъма за разбъркване е мързелив, тъй като се фокусира само върху еднопосочно свързан списък. Това е разумно решение за проектиране, но ние плащаме цена за това в сложност във времето. Сложността във времето е O ( n 2). Първо, имаме цикъл O ( n ), който извиква swap(). Второ, вътре swap()имаме двата последователни O ( n ) цикъла. Припомнете си следното правило от Част 1:

 If f1(n) = O(g(n)) and f2(n) = O(h(n)) then (a) f1(n)+f2(n) = max(O(g(n)), O(h(n))) (b) f1(n)*f2(n) = O(g(n)*h(n)). 

Част (а) се занимава с последователни алгоритми. Тук имаме два O ( n ) контура. Съгласно правилото, получената сложност във времето ще бъде O ( n ). Част (б) се занимава с вложени алгоритми. В този случай имаме O ( n ), умножено по O ( n ), което води до O ( n 2).

Имайте предвид, че пространствената сложност на Shuffle е O (1), в резултат на помощните променливи, които са декларирани.

Примерно приложение: Разбъркване в двойно свързан списък

В Shuffleзаявлението на Обява 2 е демонстрация на алгоритъма Shuffle.

Листинг 2. Алгоритъмът за разбъркване в Java

 import java.util.Random; public final class Shuffle { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Shuffle list. Random rnd = new Random(); for (int i = 3; i > 1; i--) swap(topForward, i - 1, rnd.nextInt(i)); // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } public static void swap(Node top, int i, int j) { // Locate ith node. Node nodei = top; for (int k = 0; k < i; k++) nodei = nodei.next; // Locate jth node. Node nodej = top; for (int k = 0; k < j; k++) nodej = nodej.next; String namei = nodei.name; String namej = nodej.name; nodej.name = namei; nodei.name = namej; } } 

Съставете списък 5, както следва:

 javac Shuffle.java 

Стартирайте полученото приложение, както следва:

 java Shuffle 

Трябва да наблюдавате следния изход от едно изпълнение:

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list: BAC Backward singly-linked list: CAB 

Циркулярно свързани списъци

Полето за връзка в последния възел на единично свързан списък съдържа нулева връзка. Това важи и за двойно свързан списък, който съдържа полетата за връзки в последните възли на еднопосочно свързаните списъци напред и назад. Да предположим вместо това, че последните възли са съдържали връзки към първите възли. В тази ситуация бихте получили кръгово свързан списък , който е показан на фигура 2.

Circular-linked lists, also known as circular buffers or circular queues, have many uses. For example, they're used by operating system interrupt handlers to buffer keystrokes. Multimedia applications use circular-linked lists to buffer data (for example, buffering data being written to a sound card). This technique is also used by the LZ77 family of lossless data compression algorithms.

Linked lists versus arrays

Throughout this series on data structures and algorithms, we've considered the strengths and weaknesses of different data structures. Since we've focused on arrays and linked lists, you might have questions about these types specifically. What advantages and disadvantages do linked lists and arrays offer? When do you use a linked list and when do you use an array? Can data structures from both categories be integrated into a useful hybrid data structure? I'll try to answer these questions below.

Linked lists offer the following advantages over arrays:

  • They don't require extra memory to support expansion. In contrast, arrays require extra memory when expansion is necessary. (Once all elements contain data items, no new data items can be appended to an array.)
  • Те предлагат по-бързо въвеждане / изтриване на възел, отколкото еквивалентни операции, базирани на масив. Само връзките трябва да се актуализират след идентифициране на позицията за вмъкване / изтриване. От гледна точка на масива, вмъкването на елемент от данни изисква движението на всички други елементи на данни, за да се създаде празен елемент. По същия начин изтриването на съществуващ елемент от данни изисква движението на всички други елементи от данни, за да се премахне празен елемент. Преместването на всички елементи от данни отнема време.

За разлика от тях масивите предлагат следните предимства пред свързаните списъци:

  • Елементите на масива заемат по-малко памет от възлите, тъй като елементите не изискват полета за връзка.
  • Масивите предлагат по-бърз достъп до елементи от данни чрез индекси, базирани на цели числа.