Strutture dati e algoritmi in Java, Parte 4: elenchi collegati singolarmente

Come gli array, che sono stati introdotti nella Parte 3 di questa serie di esercitazioni, gli elenchi collegati sono una categoria di strutture dati fondamentali su cui è possibile basare strutture dati più complesse. A differenza di una sequenza di elementi, tuttavia, un elenco collegato è una sequenza di nodi, in cui ogni nodo è collegato al nodo precedente e successivo nella sequenza. Ricorda che un nodo è un oggetto creato da una classe autoreferenziale e una classe autoreferenziale ha almeno un campo il cui tipo di riferimento è il nome della classe. I nodi in un elenco collegato sono collegati tramite un riferimento nodo. Ecco un esempio:

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

In questo esempio, Employeeè una classe autoreferenziale perché il suo nextcampo ha tipo Employee. Questo campo è un esempio di campo di collegamento perché può memorizzare un riferimento a un altro oggetto della sua classe, in questo caso un altro Employeeoggetto.

Questo tutorial introduce i dettagli degli elenchi collegati singolarmente nella programmazione Java. Imparerai le operazioni per creare un elenco collegato singolarmente, inserire nodi in un elenco collegato singolarmente, eliminare nodi da un elenco collegato singolarmente, concatenare un elenco collegato singolarmente a un altro elenco collegato singolarmente e invertire un elenco collegato singolarmente. Esploreremo anche gli algoritmi più comunemente usati per ordinare elenchi collegati singolarmente e concluderemo con un esempio che mostra l'algoritmo di ordinamento per inserzione.

download Ottieni il codice Scarica le tre applicazioni di esempio per questo articolo. Creato da Jeff Friesen per JavaWorld.

Cos'è una lista collegata singolarmente?

Un elenco collegato singolarmente è un elenco collegato di nodi in cui ogni nodo ha un singolo campo di collegamento. In questa struttura dati, una variabile di riferimento contiene un riferimento al primo (o al primo) nodo; ogni nodo (eccetto l'ultimo o l'ultimo nodo) si collega a quello successivo; e il campo di collegamento dell'ultimo nodo contiene il riferimento nullo per indicare la fine dell'elenco. Sebbene la variabile di riferimento abbia un nome comune top, puoi scegliere qualsiasi nome desideri.

La Figura 1 presenta un elenco collegato singolarmente con tre nodi.

Di seguito è riportato lo pseudocodice per un elenco collegato singolarmente.

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

Nodeè una classe autoreferenziale con un namecampo dati e un nextcampo collegamento. topè una variabile di riferimento di tipo Nodeche contiene un riferimento al primo Nodeoggetto in un elenco collegato singolarmente. Poiché l'elenco non esiste ancora, topil valore iniziale di è NULL.

Creazione di un elenco collegato singolarmente in Java

Si crea un elenco collegato singolarmente allegando un singolo Nodeoggetto. Il seguente pseudocodice crea un Nodeoggetto, assegna il suo riferimento a top, inizializza il suo campo dati e lo assegna NULLal suo campo di collegamento:

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

La Figura 2 mostra l'elenco iniziale collegato singolarmente che emerge da questo pseudocodice.

Questa operazione ha una complessità temporale di O (1) - costante. Ricorda che O (1) si pronuncia "Big Oh of 1." (Vedere la Parte 1 per un promemoria su come le misurazioni della complessità temporale e spaziale vengono utilizzate per valutare le strutture dei dati.)

Inserimento di nodi in un elenco collegato singolarmente

L'inserimento di un nodo in un elenco collegato singolarmente è un po 'più complicato rispetto alla creazione di un elenco collegato singolarmente perché ci sono tre casi da considerare:

Inserimento prima del primo nodo.
Inserimento dopo l'ultimo nodo.
Inserimento tra due nodi.

Inserimento prima del primo nodo

Un nuovo nodo viene inserito prima del primo nodo assegnando il riferimento del nodo superiore al campo di collegamento del nuovo nodo e assegnando il riferimento del nuovo nodo alla topvariabile. Questa operazione è dimostrata dal seguente pseudocodice:

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

Il risultante Nodeelenco a due viene visualizzato nella Figura 3.

Questa operazione ha una complessità temporale di O (1).

Inserimento dopo l'ultimo nodo

Un nuovo nodo viene inserito dopo l'ultimo nodo assegnando null al campo di collegamento del nuovo nodo, attraversando l'elenco collegato singolarmente per trovare l'ultimo nodo e assegnando il riferimento del nuovo nodo al campo di collegamento dell'ultimo nodo, come dimostra il seguente pseudocodice:

 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

La figura 4 mostra l'elenco dopo l'inserimento di NodeC dopo NodeA.

Questa operazione ha una complessità temporale di O ( n ) - lineare. La sua complessità temporale potrebbe essere migliorata a O (1) mantenendo un riferimento all'ultimo nodo. In tal caso non sarebbe necessario cercare l'ultimo nodo.

Inserimento tra due nodi

L'inserimento di un nodo tra due nodi è il caso più complesso. Si inserisce un nuovo nodo tra due nodi attraversando l'elenco per trovare il nodo che precede il nuovo nodo, assegnando il riferimento nel campo di collegamento del nodo trovato al campo di collegamento del nuovo nodo e assegnando il riferimento del nuovo nodo al collegamento del nodo trovato campo. Il seguente pseudocodice dimostra queste attività:

 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

La figura 5 presenta l'elenco successivo all'inserimento di NodeD tra Nodes A e C.

Questa operazione ha una complessità temporale di O ( n ).

Eliminazione di nodi da un elenco collegato singolarmente

Anche l'eliminazione di un nodo da un elenco collegato singolarmente è un po 'più complicato rispetto alla creazione di un elenco collegato singolarmente. Tuttavia, ci sono solo due casi da considerare:

Cancellazione del primo nodo.
Cancellazione di qualsiasi nodo tranne il primo nodo.

Cancellazione del primo nodo

L'eliminazione del primo nodo implica l'assegnazione del collegamento nel campo di collegamento del primo nodo alla variabile che fa riferimento al primo nodo, ma solo quando è presente un primo nodo:

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

La Figura 6 presenta le visualizzazioni prima e dopo di un elenco in cui la prima Nodeè stata eliminata. Il nodo Bscompare e NodeA diventa il primo Node.

Questa operazione ha una complessità temporale di O (1).

Cancellazione di qualsiasi nodo tranne il primo nodo

L'eliminazione di qualsiasi nodo tranne il primo implica l'individuazione del nodo che precede il nodo da eliminare e l'assegnazione del riferimento nel campo di collegamento del nodo da eliminare al campo di collegamento del nodo precedente. Considera il seguente pseudocodice:

 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

La Figura 7 presenta le visualizzazioni prima e dopo di un elenco in cui Nodeviene eliminato un intermedio . NodeD scompare.

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