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 next
campo 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 Employee
oggetto.
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 name
campo dati e un next
campo collegamento. top
è una variabile di riferimento di tipo Node
che contiene un riferimento al primo Node
oggetto in un elenco collegato singolarmente. Poiché l'elenco non esiste ancora, top
il valore iniziale di è NULL
.
Creazione di un elenco collegato singolarmente in Java
Si crea un elenco collegato singolarmente allegando un singolo Node
oggetto. Il seguente pseudocodice crea un Node
oggetto, assegna il suo riferimento a top
, inizializza il suo campo dati e lo assegna NULL
al 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 top
variabile. Questa operazione è dimostrata dal seguente pseudocodice:
DECLARE Node temp temp = NEW Node temp.name = "B" temp.next = top top = temp
Il risultante Node
elenco 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 Node
C dopo Node
A.

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 Node
D tra Node
s 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 B
scompare e Node
A 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 Node
viene eliminato un intermedio . Node
D 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
This operation has a time complexity of O(n).
Example #2: Concatenating and inverting a singly linked list
Ho creato una seconda versione SLLDemo
dell'applicazione Java che mostra la concatenazione e l'inversione. Il listato 2 presenta il codice sorgente di questa applicazione.