Gli elenchi collegati sono una delle strutture di dati più comuni utilizzate per l’allocazione dinamica della memoria. Qui viene creato un elenco di un set finito di elementi, che contiene almeno due posizioni di memoria: una per l’elemento di dati e un altro per il puntatore che collega il prossimo set di elementi. Questo tutorial spiega come è possibile implementare diversi elenchi collegati utilizzando puntatori e tipi di struttura in GO.
Strutture di dati in Go
La memoria di accesso casuale (RAM) può essere visualizzata come una tabella, una matrice o una griglia di posizioni indirizzabili. Per archiviare i valori nella tabella, i programmatori devono designarli Strutture localizzabili. A queste strutture locabili viene dato un nome comodo chiamato Nome variabile. Comprendi che un nome dato a una variabile è solo per comodità del programmatore; Una volta compilato il programma, il nome variabile viene sostituito con a riferimento (o indirizzo di memoria, come advert esempio 0x78bac).
Nella forma più semplice, un nome variabile può riferirsi a una singola cella, ma in situazioni complicate, può essere una posizione di memoria contigua o una matrice con una riga e una colonna chiamata vettore. Un array può essere a livello di programmazione dal suo indiceadvert esempio Array_name (2) (4)che può significare elementi nella seconda colonna e nella quarta riga.
Tuttavia, in un’altra situazione complicata, la relazione strutturale tra gli elementi di dati potrebbe non essere archiviata in modo contiguo. Piuttosto, possono essere conservati in modo casuale, are available in una struttura advert albero che rappresenta le relazioni gerarchiche, le relazioni di ramificazione o una struttura multilink complessa con molte interconnessioni.
Pertanto, al nice di archiviare relazioni strutturali presenti nei dati, gli sviluppatori GO devono definire il format della memoria e l’accesso alle strategie in base alla loro esigenza specifica.
Allocazione di memoria statica e dinamica in GO
Un fatto importante sull’allocazione della memoria sono le proprietà chiamate dinamico E statico natura. Le dimensioni e la posizione di una struttura di dati statica sono predefinite, mentre in una struttura di dati dinamica, le dimensioni e la posizione non sono particular o sono decise in fase di esecuzione.
Advert esempio, poiché gli sviluppatori GO definiscono un array, forniscono un valore statico delle sue dimensioni in modo che il compilatore sappia esattamente a quale posizione si riferiscono quando forniscono valori dell’indice. Nelle strutture di dati dinamici, come gli elenchi collegati, viene decisa la posizione dell’elemento di dati successivo soltanto quando viene creato durante la fase di esecuzione. Le dimensioni della struttura dei dati dinamiche possono crescere o ridursi in fase di esecuzione. Poiché le strutture di dati statiche sono archiviate in posizioni di memoria contigue, funzionano in modo lineare, in cui gli elementi di dati sono archiviati in sequenza.
La base di strutture di dati dinamiche è chiamata a Elenco collegato (Sebbene si noti che l’allocazione della memoria dinamica non è limitata agli elenchi collegati). Qui, gli elementi di dati sono archiviati in una posizione casuale nella memoria con un collegamento per accedere a ciascuno degli elementi. Pertanto, un elenco collegato contiene almeno due elementi: uno che rappresenta un elemento di dati e un altro collegamento alla struttura successiva.
Confrontare l’allocazione sequenziale e collegata in GO
A differenza delle strutture sequenziali (advert esempio, array), l’allocazione collegata richiede una memoria aggiuntiva per archiviare non solo l’elemento di dati ma anche un elemento per archiviare un collegamento all’elemento successivo. Questo può essere un fattore dominante in alcune situazioni, ma l’efficienza acquisita attraverso l’allocazione collegata supera di gran lunga i suoi svantaggi. Advert esempio, la dimensione allocata di memoria è fissata in array; Pertanto, molto può rimanere inutilizzato. Nell’allocazione collegata, il problema dell’allocazione non utilizzata non si presenta perché un nodo viene creato solo quando necessario.
È facile eliminare gli elementi in un elenco collegato, ma nell’allocazione sequenziale, la cancellazione implica in genere lo spostamento di gran parte degli elementi di dati in numerous posizioni. Inoltre, l’inserimento dei dati è rapido nell’allocazione collegata. Tuttavia, fare riferimento a una parte casuale dell’elenco è molto più veloce nei casi di allocazione sequenziale.
Ogni metodo di archiviazione ha i suoi professional e contro. Scegliere la struttura giusta è a discrezione del programmatore GO.
Tipi di elenchi collegati
Esistono tre modi di base che un elenco collegato può rappresentare la memoria: lineare, circolare, doppiamenteE doppiamente circolare.
In a lineare O Elenco singolarmente collegatoesiste un singolo elemento di collegamento che indica il nodo successivo nell’elenco. L’elemento successivo dell’ultimo nodo di collegamento a nilcosì poiché l’elenco viene attraversato dall’inizio alla nice, l’elenco è rappresentato non appena nil si incontra.
IL Elenco collegato circolare è lo stesso di un elenco lineare, tranne per il fatto che l’ultimo nodo punta al primo nodo. L’arrestamento può verificarsi fino a quando l’elemento successivo non contiene l’indirizzo del primo nodo. Poiché l’ultimo nodo indica il primo, è possibile attraversare circolare.
In a Elenco doppiamente collegatoVengono forniti due indirizzi collegati: uno che si collega al nodo precedente e un altro che si collega al nodo successivo. A differenza degli elenchi lineari, questo è chiaramente un vantaggio perché la attraversamento può verificarsi in entrambe le direzioni. Trovare elementi di dati può essere rapido.
UN Elenco collegato doppiamente circolare è lo stesso di un elenco doppiamente collegato, tranne per il fatto che l’elemento successivo dell’ultimo nodo si collega al primo nodo e l’elemento precedente si collega all’ultimo nodo. Ciò rende possibile l’attraversamento circolare in entrambe le direzioni.
Si noti che la flessibilità aumenta mentre passiamo da un elenco singolarmente a doppiamente collegato e circolare a doppiamente-circolare. Implementamo ciascuno di questi tipi di elenchi collegati GO advert alcuni degli esempi di seguito. Per semplificare le cose, limiteremo principalmente alla creazione e all’attraversamento dell’elenco.
Esempio di elenco singolarmente collegato in GO
Di seguito è riportato un esempio di come creare un elenco singolarmente collegato in GO:
bundle most important
import (
"fmt"
"math/rand"
)
kind Node struct {
information interface{}
subsequent *Node
}
kind Checklist struct {
head *Node
}
func (l *Checklist) Insert(d interface{}) {
record := &Node{information: d, subsequent: nil}
if l.head == nil {
l.head = record
} else {
p := l.head
for p.subsequent != nil {
p = p.subsequent
}
p.subsequent = record
}
}
func Present(l *Checklist) {
p := l.head
for p != nil {
fmt.Printf("-> %v ", p.information)
p = p.subsequent
}
}
func most important() {
sl := Checklist{}
for i := 0; i L’output previsto per l’esecuzione di questo codice Golang nel tuo ambiente di sviluppo integrato è:
-> 81 -> 87 -> 47 -> 59 -> 81Esempio di codice dell’elenco collegato circolare in GO
Possiamo facilmente convertire un singolo elenco collegato in circolare. Quindi, senza modificare il codice sopra, aggiungi queste due funzioni: ConvertSinglyToCircular E ShowCircular. Invocare queste due funzioni da most importantquesto è tutto.
Ecco le due funzioni:
func ShowCircular(l *Checklist) {
p := l.head
for {
if p.subsequent == l.head {
fmt.Printf("-> %v ", p.information)
break
}
fmt.Printf("-> %v ", p.information)
p = p.subsequent
}
}
func ConvertSinglyToCircular(l *Checklist) {
p := l.head
for p.subsequent != nil {
p = p.subsequent
}
p.subsequent = l.head
}Nota: mentre si presume che questo elenco sia già circolare (cioè, p.subsequent Alla nice punta indietro a l.head), Se l.head È nil (Elenco vuoto), questa funzione si bloccherà con un errore di dereferenza del puntatore NIL.
Ora, invoca le funzioni da most important Come segue:
func most important() {
sl := Checklist{}
for i := 0; i Esempio di codice dell’elenco doppiamente collegato in GO
Ecco un esempio di codice che mostra come creare elenchi doppiamente collegati in Golang:
bundle most important
import (
"fmt"
"math/rand"
"time"
)
kind Node struct {
information interface{}
prev *Node
subsequent *Node
}
kind Checklist struct {
head *Node
tail *Node
}
func (l *Checklist) Insert(d interface{}) {
record := &Node{information: d, prev: nil, subsequent: nil}
if l.head == nil {
l.head = record
l.tail = record
} else {
p := l.head
for p.subsequent != nil {
p = p.subsequent
}
record.prev = p
p.subsequent = record
l.tail = record
}
}
func Present(l *Checklist) {
p := l.head
for p != nil {
fmt.Printf("-> %v ", p.information)
p = p.subsequent
}
}
func ReverseShow(l *Checklist) {
r := l.tail
for r != nil {
fmt.Printf("-> %v ", r.information)
r = r.prev
}
}
func most important() {
sl := Checklist{}
seed := rand.NewSource(time.Now().UnixNano())
rnd := rand.New(seed)
for i := 0; i L’output previsto per l’esecuzione di questo esempio di codice GO nell’editor di codice sarebbe:
-> 11 -> 17 -> 56 -> 71 -> 39 -> 44 -> 18 -> 78 -> 25 -> 19
----------------------------
-> 19 -> 25 -> 78 -> 18 -> 44 -> 39 -> 71 -> 56 -> 17 -> 11Esempio di elenco collegato doppiamente circolare in GO
Proprio come l’elenco collegato circolare, un elenco collegato doppiamente circolare può essere facilmente convertito dall’elenco doppiamente collegato. Aggiungeremo solo due funzioni al codice sopra. Il resto del codice rimane lo stesso, tranne una leggera modifica in most important Funzione, come abbiamo visto nel caso del nostro esempio di elenco collegato circolare:
func ConvertDoublyToDoublyCircular(l *Checklist) {
l.head.prev = l.tail
l.tail.subsequent = l.head
}
func ShowDoublyCircular(l *Checklist) {
p := l.head
for {
if p.subsequent == l.head {
fmt.Printf("-> %v ", p.information)
break
}
fmt.Printf("-> %v ", p.information)
p = p.subsequent
}
}
func ReverseShowDoublyCircular(l *Checklist) {
r := l.tail
for {
if r.prev == l.tail {
fmt.Printf("-> %v ", r.information)
break
}
fmt.Printf("-> %v ", r.information)
r = r.prev
}
}
func most important() {
sl := Checklist{}
seed := rand.NewSource(time.Now().UnixNano())
rnd := rand.New(seed)
for i := 0; i I pensieri finali sulla programmazione vanno elenchi collegati
Come possiamo vedere, un elenco collegato è abbastanza facile da implementare in Go. Le allocazioni collegate vengono utilizzate per modellare diversi tipi di dati, che si tratti di valori singoli o strutture di dati complesse con molti campi. L’accesso è davvero veloce nella ricerca sequenziale se usato con i puntatori. Esistono numerous tecniche di ottimizzazione affiliate a elenchi collegati. Gli elenchi doppiamente collegati hanno una maggiore efficacia rispetto all’allocazione collegata singolare e il traversario può essere rapido in entrambe le direzioni.
Nota dell’editore: l’immagine in primo piano di questo articolo (Gopher) è stata creata da Renee Frenchautorizzato sotto il Attribuzione Inventive Commons 4.0 licenza, e si trova anche su Go’s GitHub.
