Τι είναι μια συνδεδεμένη δομή δεδομένων;

Μια συνδεδεμένη δομή δεδομένων είναι μια συλλογή δεδομένων που είναι διατεταγμένα σε μορφή λίστας. Κάθε κομμάτι αναφοράς στη λίστα αναφέρεται ως κόμβος. Κάθε κόμβος συνδέεται με τον επόμενο στοΛίστα με αναφορά στη διεύθυνση μνήμης αυτού του επόμενου κόμβου.Η εκτέλεση του προγράμματος. Ο πιο συνηθισμένος τύπος συνδεδεμένης δομής δεδομένων ονομάζεται συνδεδεμένη λίστα.Μια αναφορά στα πραγματικά δεδομένα που αποθηκεύονται και μια αναφορά στον επόμενο κόμβο της λίστας. Μια συνδεδεμένη λίστα διασχίζεται ή αναζητείται, περνώντας από κάθε έναν από τους κόμβους δεδομένων, ξεκινώντας από την πρώτη,ή ο επικεφαλής της λίστας. Δεν υπάρχει τρόπος να βρείτε πληροφορίες σε μια συνδεδεμένη λίστα χωρίς να μετακινείτε διαδοχικά μέσω των κόμβων από την αρχή μέχρι το τέλος.

Οι περισσότερες συνδεδεμένες δομές δεδομένων θα χρησιμοποιήσουν όσο το δυνατόν λιγότερη μνήμη κατά τη διάρκεια του προγράμματος κατά τη διάρκεια του προγράμματοςεκτέλεση. Εάν δημιουργηθεί μια συνδεδεμένη λίστα με μόνο έναν κόμβο και δεν προστίθενται άλλοι κόμβοι, αυτή η λίστα θα πάρει τη μνήμη που απαιτείται μόνο για έναν κόμβο. Αυτό είναι στο StarkΣε αντίθεση με μια δομή δεδομένων συστοιχίας στην οποία το μέγεθος ολόκληρης της συστοιχίας πρέπει να δηλωθεί και να διατεθεί στην αρχή του προγράμματος και δεν μπορεί να αλλάξει.περισσότερη υπολογιστική ισχύ. Βρίσκοντας ένα συγκεκριμένο κομμάτι dΤο ATA σε μια συνδεδεμένη λίστα απαιτεί βρόχο σε ολόκληρη τη λίστα κάθε φορά, οπότε μπορεί να είναι πιο αργή για πρόσβαση σε πληροφορίες στη μέση της λίστας. Η αφαίρεση ή η αναδιάταξη δεδομένων σε μια συνδεδεμένη λίστα μπορεί επίσης να είναι πιο υπολογιστικά εντατική από τη διαχείριση ενόςπίνακας στην οποία τα στοιχεία μπορούν να αντικατασταθούν εύκολα.

Μια συνδεδεμένη δομή δεδομένων δεν απαιτείται να έχει μόνο μία αναφορά στον επόμενο κόμβο.μπορεί να έχει αρκετές. Ορισμένες συνδεδεμένες λίστες έχουν δύο αναφορές κόμβων, μία στον επόμενο κόμβο στη λίστα και μία στον προηγούμενο κόμβο. Αυτές είναι γνωστές ως διπλά συνδεδεμένες λίστες. Αυτό μπορεί να κάνει τη μετακίνηση μέσω ενόςκατάλογος σε οποιαδήποτε κατεύθυνση πολύ πιο γρήγορη, αν και σε βάρος της αυξημένης χρήσης μνήμης για τη δομή των δεδομένων.

Είναι δυνατόν οι συνδεδεμένες λίστες να έχουν τρεις ή περισσότερες αναφορές σε άλλους κόμβους στον κατάλογο. Αυτό δημιουργεί μια δομή παρόμοιασε ένα δέντρο με ολόκληρους κλάδους των κόμβων που αναπαράγονται από ένα μόνο. Αυτοί οι τύποι δομών δεδομένων ονομάζονται πολλαπλασιασμένες λίστες.Τα δέντρα αναζήτησης είναι δυνατά σε μεγάλο βαθμό λόγω της χρήσης συνδεδεμένων δομών δεδομένων για τη δημιουργία πολλαπλών κλάδων μεταβλητών μήκους.