Структуры данных и алгоритмы в Java, Часть 4: Односвязные списки

Подобно массивам, которые были представлены в части 3 этой серии руководств, связанные списки представляют собой фундаментальную категорию структур данных, на которой могут быть основаны более сложные структуры данных. Однако в отличие от последовательности элементов связанный список представляет собой последовательность узлов, где каждый узел связан с предыдущим и следующим узлами в последовательности. Напомним, что узел - это объект, созданный из класса, ссылающегося на себя, а класс, ссылающийся на себя, имеет по крайней мере одно поле, ссылочным типом которого является имя класса. Узлы в связанном списке связаны через ссылку на узел. Вот пример:

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

В этом примере Employeeэто класс, ссылающийся на себя, потому что его nextполе имеет тип Employee. Это поле является примером поля ссылки, потому что оно может хранить ссылку на другой объект своего класса - в данном случае другой Employeeобъект.

Это руководство знакомит с тонкостями односвязных списков в программировании на Java. Вы изучите операции для создания односвязного списка, вставки узлов в односвязный список, удаления узлов из односвязного списка, конкатенации односвязного списка в другой односвязный список и инвертирования односвязного списка. Мы также рассмотрим алгоритмы, наиболее часто используемые для сортировки односвязных списков, и в заключение приведем пример, демонстрирующий алгоритм сортировки вставкой.

загрузить Получить код Загрузите три примера приложений для этой статьи. Создано Джеффом Фризеном для 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) произносится как «Большое О из 1». (См. Часть 1 для напоминания о том, как измерения сложности времени и пространства используются для оценки структур данных.)

Вставка узлов в односвязный список

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

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

Вставка перед первым узлом

Новый узел вставляется перед первым узлом путем присвоения ссылки верхнего узла полю ссылки нового узла и присвоения ссылки нового узла topпеременной. Эта операция демонстрируется следующим псевдокодом:

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

Результирующий Nodeсписок из двух элементов показан на рисунке 3.

Эта операция имеет временную сложность O (1).

Вставка после последнего узла

Новый узел вставляется после последнего узла путем присвоения null полю ссылки нового узла, обхода односвязного списка для поиска последнего узла и присвоения ссылки нового узла полю ссылки последнего узла, как демонстрирует следующий псевдокод:

 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

Я создал вторую версию SLLDemoприложения Java, демонстрирующую конкатенацию и инверсию. В листинге 2 представлен исходный код этого приложения.