Структури на данни и алгоритми в Java, Част 4: Единично свързани списъци

Подобно на масивите, които бяха въведени в Част 3 от тази поредица от уроци, свързаните списъци са основна категория на структурата на данни, върху която могат да се основават по-сложни структури от данни. За разлика от поредицата от елементи обаче, свързаният списък е поредица от възли, където всеки възел е свързан с предходния и следващия възел в последователността. Спомнете си, че възел е обект, създаден от самореферентен клас, а самореферентният клас има поне едно поле, чийто референтен тип е името на класа. Възлите в свързан списък са свързани чрез препратка към възел. Ето пример:

 class Employee { private int empno; private String name; private double salary; public Employee next; // Other members. }

В този пример Employeeе самореферентен клас, защото неговото nextполе има тип Employee. Това поле е пример за поле за връзка, защото може да съхранява препратка към друг обект от своя клас - в този случай друг Employeeобект.

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

изтегляне Вземете кода Изтеглете трите примерни приложения за тази статия. Създадено от Jeff Friesen за JavaWorld.

Какво представлява единично свързан списък?

А единично свързан списък е свързан списък на възли, където всеки възел има едно поле връзка. В тази структура от данни референтната променлива съдържа препратка към първия (или най-горния) възел; всеки възел (с изключение на последния или долния възел) се свързва със следващия; и полето за връзка на последния възел съдържа нулевата препратка, за да обозначи края на списъка. Въпреки че референтната променлива е често именувана top, можете да изберете всяко име, което искате.

Фигура 1 представя единично свързан списък с три възли.

По-долу е псевдокодът за единично свързан списък.

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next END DECLARE DECLARE Node top = NULL 

Nodeе самореферентен клас с nameполе за данни и поле за nextвръзка. topе референтна променлива от тип, Nodeкоято съдържа препратка към първия Nodeобект в единично свързан списък. Тъй като списъкът все още не съществува, topпървоначалната стойност на NULL.

Създаване на единично свързан списък в Java

Създавате единично свързан списък, като прикачите един Nodeобект. Следният псевдокод създава Nodeобект, присвоява препратката към него top, инициализира неговото поле за данни и присвоява NULLна неговото поле за връзка:

 top = NEW Node top.name = "A" top.next = NULL 

Фигура 2 показва първоначалния единично свързан списък, който излиза от този псевдокод.

Тази операция има времева сложност на O (1) - постоянна. Спомнете си, че O (1) се произнася „Big Oh of 1.“ (Вижте Част 1 за напомняне за това как измерванията на сложността на времето и пространството се използват за оценка на структурите на данните.)

Вмъкване на възли в единично свързан списък

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

  • Вмъкване преди първия възел.
  • Вмъкване след последния възел.
  • Вмъкване между два възела.

Вмъкване преди първия възел

Нов възел се вмъква преди първия възел чрез присвояване на препратка към горния възел към полето за връзка на новия възел и присвояване на препратка към новия възел на topпроменливата. Тази операция се демонстрира от следния псевдокод:

 DECLARE Node temp temp = NEW Node temp.name = "B" temp.next = top top = temp 

Полученият двусписък се Nodeпоявява на фигура 3.

Тази операция има времева сложност на O (1).

Вмъкване след последния възел

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

 temp = NEW Node temp.name = "C" temp.next = NULL DECLARE Node temp2 temp2 = top // We assume top (and temp2) are not NULL // because of the previous pseudocode. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 now references the last node. temp2.next = temp 

Фигура 4 разкрива списъка след вмъкването на NodeC след NodeA.

Тази операция има времева сложност на O ( n ) - линейна. Сложността му във времето може да бъде подобрена до O (1) чрез поддържане на препратка към последния възел. В този случай не би било необходимо да се търси последният възел.

Вмъкване между два възела

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

 temp = NEW Node temp.name = "D" temp2 = top // We assume that the newly created Node inserts after Node // A and that Node A exists. In the real world, there is no // guarantee that any Node exists, so we would need to check // for temp2 containing NULL in both the WHILE loop's header // and after the WHILE loop completes. WHILE temp2.name NE "A" temp2 = temp2.next END WHILE // temp2 now references Node A. temp.next = temp2.next temp2.next = temp 

Фигура 5 представя списъка след вмъкването на NodeD между Nodes A и C.

Тази операция има времева сложност на O ( n ).

Изтриване на възли от единично свързан списък

Изтриването на възел от единично свързан списък също е малко по-сложно от създаването на единично свързан списък. Съществуват обаче само два случая:

  • Изтриване на първия възел.
  • Изтриване на всеки възел, но на първия възел.

Deletion of the first node

Deleting the first node involves assigning the link in the first node's link field to the variable that references the first node, but only when there is a first node:

 IF top NE NULL THEN top = top.next; // Reference the second Node (or NULL when there's only one Node). END IF 

Figure 6 presents before and after views of a list where the first Node has been deleted. Node B disappears and Node A becomes the first Node.

This operation has a time complexity of O(1).

Deletion of any node but the first node

Deleting any node but the first node involves locating the node that precedes the node to be deleted and assigning the reference in the node-to-be-deleted's link field to the preceding node's link field. Consider the following pseudocode:

 IF top NE NULL THEN temp = top WHILE temp.name NE "A" temp = temp.next END WHILE // We assume that temp references Node A. temp.next = temp.next.next // Node D no longer exists. END IF 

Figure 7 presents before and after views of a list where an intermediate Node is deleted. Node D disappears.

This operation has a time complexity of O(n).

Example #1: Create, insert, and delete in a singly linked list

I've created a Java application named SLLDemo that demonstrates how to create, insert, and delete nodes in a singly linked list. Listing 1 presents this application's source code.

Listing 1. Java application demo for singly linked lists (SSLDemo.java, version 1)

 public final class SLLDemo { private static class Node { String name; Node next; } public static void main(String[] args) { Node top = null; // 1. The singly linked list does not exist. top = new Node(); top.name = "A"; top.next = null; dump("Case 1", top); // 2. The singly linked list exists and the node must be inserted // before the first node. Node temp; temp = new Node(); temp.name = "B"; temp.next = top; top = temp; dump("Case 2", top); // 3. The singly linked list exists and the node must be inserted // after the last node. temp = new Node(); temp.name = "C"; temp.next = null; Node temp2; temp2 = top; while (temp2.next != null) temp2 = temp2.next; temp2.next = temp; dump("Case 3", top); // 4. The singly linked list exists and the node must be inserted // between two nodes. temp = new Node(); temp.name = "D"; temp2 = top; while (temp2.name.equals("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; dump("Case 4", top); // 5. Delete the first node. top = top.next; dump("After first node deletion", top); // 5.1 Restore node B. temp = new Node(); temp.name = "B"; temp.next = top; top = temp; // 6. Delete any node but the first node. temp = top; while (temp.name.equals("A") == false) temp = temp.next; temp.next = temp.next.next; dump("After D node deletion", top); } private static void dump(String msg, Node topNode) { System.out.print(msg + " "); while (topNode != null) { System.out.print(topNode.name + " "); topNode = topNode.next; } System.out.println(); } } 

Compile Listing 1 as follows:

 javac SLLDemo.java 

Run the resulting application as follows:

 java SLLDemo 

You should observe the following output:

 Case 1 A Case 2 B A Case 3 B A C Case 4 B A D C After first node deletion A D C After D node deletion B A C 

Concatenating singly linked lists

You might occasionally need to concatenate a singly linked list to another singly linked list. For example, suppose you have a list of words that start with letters A through M and another list of words starting with letters N through Z, and you want to combine these lists into a single list. The following pseudocode describes an algorithm for concatenating one singly linked list to another:

 DECLARE Node top1 = NULL DECLARE Node top2 = NULL // Assume code that creates top1-referenced singly linked list. // Assume code that creates top2-referenced singly linked list. // Concatenate top2-referenced list to top1-referenced list. IF top1 EQ NULL top1 = top2 END END IF // Locate final Node in top1-referenced list. DECLARE Node temp = top1 WHILE temp.next NE NULL temp = temp.next END WHILE // Concatenate top2 to top1. temp.next = top2 END 

In the trivial case, there is no top1-referenced list, and so top1 is assigned top2's value, which would be NULL if there was no top2-referenced list.

This operation has a time complexity of O(1) in the trivial case and a time complexity of O(n) otherwise. However, if you maintain a reference to the last node, there's no need to search the list for this node; the time complexity changes to O(1).

Inverting a singly linked list

Another useful operation on a singly linked list is inversion, which reverses the list's links to let you traverse its nodes in the opposite direction. The following pseudocode reverses the top1-referenced list's links:

 DECLARE Node p = top1 // Top of original singly linked list. DECLARE Node q = NULL // Top of reversed singly linked list. DECLARE Node r // Temporary Node reference variable. WHILE p NE NULL // For each Node in original singly linked list ... r = q // Save future successor Node's reference. q = p // Reference future predecessor Node. p = p.next // Reference next Node in original singly linked list. q.next = r // Link future predecessor Node to future successor Node. END WHILE top1 = q // Make top1 reference first Node in reversed singly linked list. END 

This operation has a time complexity of O(n).

Example #2: Concatenating and inverting a singly linked list

Създадох втора версия на приложението SLLDemoJava, която демонстрира конкатенация и инверсия. Листинг 2 представя изходния код на това приложение.