Διαφορά μεταξύ της λίστας συστοιχιών και της συσχέτισης λίστας Διαφορά μεταξύ
Πώς αποθηκεύονται τα δεδομένα;
Η λίστα συστοιχιών και η λίστα συνδέσεων είναι συνηθισμένοι όροι όταν πρόκειται για αποθήκευση και ανάκτηση δεδομένων. Αν και υπάρχουν πολλές συσκευές αποθήκευσης, τελικά εξαρτώνται από τον μηχανισμό αποθήκευσης. Αυτοί οι δύο μηχανισμοί αποθήκευσης τοποθετούν τα δεδομένα σας στις συσκευές αποθήκευσης και τα ανακτούν όταν είναι απαραίτητο. Ας ρίξουμε μια ματιά στο πώς αποθηκεύουν τα δεδομένα στη μνήμη τους. Η λίστα Array χρησιμοποιεί μια διαδοχική αποθήκευση και τα κομμάτια των δεδομένων αποθηκεύονται το ένα μετά το άλλο. Αυτή είναι ίσως μια απλούστερη μορφή αποθήκευσης - αποφεύγει τη σύγχυση. Ναι, μπορούμε να ανακτήσουμε το επόμενο στοιχείο ή δεδομένα από την επόμενη θέση μνήμης της λίστας συστοιχιών. Ωστόσο, αποθηκεύεται με τη βοήθεια των δεικτών στη λίστα "Συνδεδεμένοι". Εδώ χρειάζονται δύο θέσεις μνήμης για αποθήκευση - μία για τα δεδομένα, η άλλη για δείκτη. Ένας δείκτης διευθύνει τη θέση μνήμης των επόμενων δεδομένων. Μπορούμε εύκολα να καταλάβουμε ότι η λίστα συνδέσεων δεν αποθηκεύει ποτέ τα δεδομένα διαδοχικά. Αντίθετα, χρησιμοποιεί έναν μηχανισμό τυχαίας αποθήκευσης. Οι δείκτες είναι τα βασικά στοιχεία για τον εντοπισμό των θέσεων δεδομένων στη μνήμη.
Dynamic Array and Linked List
Έχουμε ήδη συζητήσει πώς οι δύο μηχανισμοί αποθήκευσης βάζουν δεδομένα και μπορούμε να δώσουμε έναν όρο 'δυναμική συστοιχία' για το εσωτερικό σύστημα αποθήκευσης της σειράς Array. Τοποθέτει απλά τα κομμάτια δεδομένων το ένα μετά το άλλο -όπως το όνομα- ενώ η λίστα των συνδεδεμένων χρησιμοποιεί μια εσωτερική λίστα με τη βοήθεια των δεικτών για την παρακολούθηση του επόμενου στοιχείου. Ως εκ τούτου, χρησιμοποιεί μια εσωτερική συνδεδεμένη λίστα, όπως έναν μοναδικό ή διπλά συνδεδεμένο κατάλογο για να μας δείξει τα επόμενα δεδομένα.
Χρήση μνήμης
Καθώς η λίστα Array αποθηκεύει μόνο τα πραγματικά δεδομένα, χρειαζόμαστε χώρο μόνο για τα δεδομένα που αποθηκεύουμε. Αντιστρόφως, στη λίστα "Συνδεδεμένοι", χρησιμοποιούμε επίσης δείκτες. Επομένως, απαιτούνται δύο θέσεις μνήμης και μπορούμε να πούμε ότι η συνδεδεμένη λίστα καταναλώνει περισσότερη μνήμη από τη λίστα Array. Μια πλεονεκτική πλευρά της λίστας "Συνδεδεμένοι" είναι ότι ποτέ δεν απαιτεί συνεχείς θέσεις μνήμης για την αποθήκευση των δεδομένων μας, σε αντίθεση με τη λίστα Array. Οι δείκτες είναι σε θέση να κρατήσουν τη θέση της επόμενης θέσης δεδομένων και μπορούμε ακόμη να χρησιμοποιήσουμε μικρότερες θυρίδες μνήμης που δεν είναι συνεχείς. Όταν πρόκειται για τη χρήση της μνήμης, οι δείκτες παίζουν τον κύριο ρόλο στη λίστα "Συνδεδεμένοι", όπως και η αποτελεσματικότητα αυτών.
Μέγεθος της αρχικής λίστας συστοιχιών και της συνδεδεμένης λίστας
Με τη λίστα πίνακα, ακόμη και μια κενή λίστα απαιτεί μέγεθος 10, αλλά με μια λίστα συνδεδεμένων, δεν χρειαζόμαστε τόσο μεγάλο χώρο. Μπορούμε να δημιουργήσουμε μια κενή λίστα Συνδεδεμένων με μέγεθος 0. Αργότερα, μπορούμε να αυξήσουμε το μέγεθος όπως απαιτείται.
Ανάκτηση δεδομένων
Η ανάκτηση δεδομένων είναι απλούστερη στη λίστα Array καθώς αποθηκεύει διαδοχικά. Το μόνο που κάνει είναι να προσδιορίσει την πρώτη θέση δεδομένων. από εκεί, η επόμενη τοποθεσία είναι προσπελάσιμη διαδοχικά για να ανακτήσει το υπόλοιπο.Υπολογίζει όπως η πρώτη θέση δεδομένων + 'n', όπου 'n' είναι η σειρά των δεδομένων στη λίστα Array. Η συνδεδεμένη λίστα παραπέμπει τον αρχικό δείκτη για να βρει την πρώτη θέση δεδομένων και από εκεί παραπέμπει τον δείκτη που συσχετίζεται με κάθε δεδομένο για να βρει την επόμενη θέση δεδομένων. Η διαδικασία ανάκτησης εξαρτάται κυρίως από τους δείκτες εδώ και μας δείχνουν την επόμενη θέση δεδομένων.
Τέλος δεδομένων
Η λίστα Array χρησιμοποιεί μια μηδενική τιμή για να επισημάνει το τέλος των δεδομένων, ενώ η Linked λίστα χρησιμοποιεί έναν μηδενικό δείκτη για το σκοπό αυτό. Μόλις το σύστημα αναγνωρίσει μηδενικά δεδομένα, η λίστα Array σταματά την επόμενη ανάκτηση δεδομένων. Με παρόμοιο τρόπο, ο μηδενικός δείκτης σταματά το σύστημα να προχωρήσει στην επόμενη ανάκτηση δεδομένων.
Αντίστροφη μετακίνηση
Η λίστα συνδέσμων μας επιτρέπει να διασχίσουμε τις αντίθετες κατευθύνσεις με τη βοήθεια του descendingiterator (). Ωστόσο, δεν έχουμε μια τέτοια εγκατάσταση σε μια λίστα Array - η αντίστροφη μετάβαση γίνεται πρόβλημα εδώ.
Σύνταξη
Ας δούμε τη σύνταξη Java και των δύο μηχανισμών αποθήκευσης.
Δημιουργία λίστας πίνακα:
Λίστα arraylistsample = new ArrayList ();
Προσθήκη αντικειμένων στη λίστα συστοιχιών:
Arraylistample. προσθέστε ("όνομα1");
Arraylistample. προσθέστε ("όνομα2");
Έτσι θα εμφανιστεί η λίστα Array που προκύπτει - [name1, name2].
Δημιουργία συνδεδεμένης λίστας:
Λίστα linkedlistsample = new linkedList ();
Προσθήκη αντικειμένων στη λίστα συνδέσεων:
Linkedlistsample. προσθέστε ("όνομα3");
Linkedlistsample. προσθέστε ("name4");
Με αυτόν τον τρόπο η προκύπτουσα λίστα συνδέσεων θα μοιάζει με - [όνομα3, όνομα4].
Ποιο είναι καλύτερο για τη λειτουργία Get ή Αναζήτηση;
Η λίστα Array παίρνει χρόνο O (1) για να εκτελέσει οποιαδήποτε αναζήτηση δεδομένων, ενώ η Linked List παίρνει u O (n) για την αναζήτηση δεδομένων n . Επομένως, μια λίστα Array χρησιμοποιεί πάντα έναν σταθερό χρόνο για οποιαδήποτε αναζήτηση δεδομένων, αλλά στη λίστα Linked, ο χρόνος που λαμβάνεται εξαρτάται από τη θέση των δεδομένων. Επομένως, οι λίστες πίνακα είναι πάντα μια καλύτερη επιλογή για τις λειτουργίες Get ή Search.
Ποια είναι η καλύτερη για τη λειτουργία εισαγωγής ή προσθήκης;
Και η λίστα Array και η Linked List λαμβάνουν χρόνο O (1) για την προσθήκη δεδομένων. Αλλά αν ο πίνακας είναι γεμάτος, τότε η λίστα Array διαρκεί αρκετό χρόνο για να το αλλάξετε το μέγεθος και να αντιγράψετε τα αντικείμενα στο νεότερο. Σε μια τέτοια περίπτωση, η λίστα συνδέσεων είναι η καλύτερη επιλογή.
Ποια είναι η καλύτερη για τη λειτουργία αφαίρεσης;
Η διαδικασία αφαίρεσης διαρκεί σχεδόν το ίδιο χρονικό διάστημα τόσο στη λίστα Array όσο και στη λίστα Linked. Στη λίστα Array, αυτή η ενέργεια διαγράφει τα δεδομένα και στη συνέχεια μετατοπίζει τη θέση των δεδομένων για να σχηματίσει τη νεότερη σειρά - παίρνει χρόνο O (n). Στη λίστα "Συνδεδεμένοι", αυτή η λειτουργία μετακινείται στα συγκεκριμένα δεδομένα και αλλάζει τις θέσεις δείκτη για να διαμορφώσει τη νεότερη λίστα. Ο χρόνος για το πέρασμα και την απομάκρυνση είναι και O (n) εδώ.
Ποιο είναι ταχύτερο;
Γνωρίζουμε ότι μια λίστα Array χρησιμοποιεί έναν εσωτερικό πίνακα για την αποθήκευση των πραγματικών δεδομένων. Επομένως, εάν διαγραφούν δεδομένα, τότε όλα τα επερχόμενα δεδομένα χρειάζονται αλλαγή της μνήμης.Προφανώς, αυτό απαιτεί σημαντικό χρόνο και επιβραδύνει τα πράγματα. Μια τέτοια μετατόπιση μνήμης δεν απαιτείται στη λίστα "Συνδεδεμένοι", καθώς το μόνο που κάνει είναι να αλλάξει τη θέση του δείκτη. Επομένως, μια λίστα συνδέσεων είναι ταχύτερη από μια λίστα Array σε οποιοδήποτε είδος αποθήκευσης δεδομένων. Ωστόσο, αυτό εξαρτάται αποκλειστικά από τον τύπο της λειτουργίας, i. μι. για τη λειτουργία "Λήψη" ή "Αναζήτηση", η λίστα "Συνδεδεμένοι" διαρκεί πολύ περισσότερο χρόνο από μια λίστα πίνακα. Όταν εξετάζουμε τη συνολική απόδοση, μπορούμε να πούμε ότι η λίστα συνδέσεων είναι ταχύτερη.
Πότε να χρησιμοποιήσετε μια λίστα πίνακα και μια λίστα συνδέσεων;
Μια λίστα Array είναι η πλέον κατάλληλη για μικρότερες απαιτήσεις δεδομένων όπου υπάρχει διαρκής μνήμη. Αλλά όταν ασχολούμαστε με τεράστια ποσά δεδομένων, η διαθεσιμότητα συνεχούς μνήμης υλοποιεί τους μηχανισμούς αποθήκευσης δεδομένων, είτε είναι μικρός είτε τεράστιος. Στη συνέχεια, αποφασίστε ποιος θα επιλέξει - τη λίστα Array ή τη λίστα Linked. Μπορείτε να προχωρήσετε με μια λίστα συστοιχιών όταν χρειάζεστε μόνο αποθήκευση και ανάκτηση δεδομένων. Αλλά μια λίστα μπορεί να σας βοηθήσει πέρα από αυτό με το χειρισμό των δεδομένων. Αφού αποφασίσετε πόσο συχνά απαιτείται χειρισμός δεδομένων, είναι σημαντικό να ελέγξετε τον τύπο ανάκτησης δεδομένων που συνήθως εκτελείτε. Όταν είναι απλά Get ή Search, τότε η λίστα Array είναι η καλύτερη επιλογή. για άλλες λειτουργίες, όπως Εισαγωγή ή Διαγραφή, προχωρήστε με τη λίστα Συνδεδεμένοι.
Ας δούμε τις διαφορές σε μορφή πίνακα.
