Un elenco collegato considera una raccolta di oggetti?

3

Algoritmo 4ed di Sedgewick dice

Several fundamental data types involve collections of objects. Specifically, the set of values is a collection of objects, and the operations revolve around adding, removing, or examining objects in the collection. In this section, we consider three such data types, known as the bag, the queue, and the stack. They differ in the specification of which object is to be removed or examined next.

...

A linked list is a recursive data structure that is either empty (null) or a reference to a node having a generic item and a reference to a linked list.

  • Il concetto di "collezione" è ben definito nella teoria del linguaggio di programmazione generale, o solo nella lingua o nella libreria di Java?

  • Un elenco collegato è una raccolta?

    Il libro non dice che una lista collegata è una raccolta, ma dice che le tre raccolte, vale a dire una borsa, una coda e uno stack, possono essere implementate in termini di liste collegate.

    Ma sembra che una lista collegata abbia alcune caratteristiche di una collezione, ma non sono sicuro che possieda tutte le caratteristiche di una collezione per essere qualificata come collezione.

Grazie.

    
posta Tim 07.10.2016 - 06:22
fonte

2 risposte

5

Per quanto ne so, non esiste una definizione formale di "raccolta" nel calcolo. È un termine impreciso per qualsiasi costrutto in un linguaggio o libreria di programmazione che raggruppa (di solito) elementi arbitrari che (di solito) condividono un tipo comune. Con questa definizione, una lista collegata è assolutamente una collezione.

In alcune lingue (in particolare Java e nel libro di testo a cui si fa riferimento), i programmatori pensano che le collezioni siano definite dalla loro API o in Java, la loro interfaccia. In questo mondo, la struttura dei dati dietro l'interfaccia è un dettaglio di implementazione e alcune raccolte potrebbero avere più implementazioni che utilizzano strutture di dati differenti.

In questo mondo una coda è una coda e tutte le implementazioni di una coda obbediscono ai contratti di quell'API, ma in base alle caratteristiche delle prestazioni che stai cercando, potresti voler usare la coda che è supportato da un elenco collegato o di un array .

In altri linguaggi (ad esempio, C) questa distinzione non è comunemente fatta, e gli sviluppatori hanno molte più probabilità di programmare direttamente sulla struttura dei dati scelta. In questo mondo una lista collegata è una lista collegata, e se viene usata come una borsa, una pila o una coda è interamente legata al codice che la chiama.

Quindi, in sintesi, sì un elenco collegato è una raccolta , ma in alcune lingue sei incoraggiato a non utilizzarlo direttamente, ma a nasconderlo dietro un livello di astrazione.

    
risposta data 07.10.2016 - 07:51
fonte
3

Bag , coda e stack sono descrizioni delle raccolte. Questo definisce come funzionano. Ad esempio, se si utilizza una coda, è possibile inserire elementi e ottenerli nello stesso ordine ( FIFO - first in, first out).

L'elenco collegato tuttavia non riguarda tanto l'utilizzo, ma l'implementazione . Come vengono cablati gli elementi? Ogni elemento punta al successivo.

Se vuoi essere molto pignolo, puoi dire: le liste collegate possono essere usate come raccolte , ma potrebbero anche essere usate in modo diverso. (Anche se è difficile fare un esempio qui.)

    
risposta data 07.10.2016 - 09:06
fonte