ArrayList εναντίον LinkedList εναντίον Vector

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

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

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

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

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

Ποια καλύτερη, ArrayList, LinkedList ή Vector;

Λίστα

Πριν απαντήσουμε στην ερώτηση, καλό είναι να γνωρίζουμε τι είναι ο κατάλογος. Η λίστα είναι ένας τύπος αφηρημένου τύπου δεδομένων (ADT) ο οποίος αποθηκεύει τα στοιχεία του σε μια ακολουθία και μας επιτρέπει να προσθέτουμε, να αφαιρούμε και να έχουμε πρόσβαση στα στοιχεία του χρησιμοποιώντας το ευρετήριο. Ο πίνακας είναι μια από τις δομές δεδομένων που υλοποιεί τη λίστα ADT. Στο Array, μπορούμε να προσθέσουμε, να διαγράψουμε και να πάρουμε στοιχείο χρησιμοποιώντας το δείκτη. Το ArrayList, το LinkedList και το Vector είναι ένα άλλο παράδειγμα των δομών δεδομένων που υλοποιούν τη λίστα ADT. Ενώ το Array έχει στατικό μέγεθος μόλις δηλώσει, το ArrayList, το LinkedList και το Vector έχουν ένα δυναμικό μέγεθος (δυνατότητα αλλαγής μεγέθους). Εάν ένας πίνακας δηλωθεί με μήκος 7, τότε θα έχει μήκος 7 μέχρι το τέλος του πεδίου εφαρμογής του. Ενώ οι ArrayList, LinkedList και Vector μπορούν να αποθηκεύουν δεδομένα όσο το δυνατόν περισσότερο, όπου το όριο είναι το σύνολο της διαθέσιμης μνήμης.

Πλαίσιο συλλογής Java. Πηγή: Wikipedia

Στο πλαίσιο συλλογής Java, η λίστα ADT υλοποιείται ως διεπαφή που ονομάζεται λίστα, και το ArrayList, LinkedList & Vector είναι η κατηγορία των συγκεκριμένων που υλοποιεί τη διεπαφή λίστας. Δεδομένου ότι αυτές οι συγκεκριμένες τάξεις εφαρμόζουν την ίδια διεπαφή, αυτές οι κλάσεις πρέπει να έχουν την ίδια λειτουργικότητα επειδή για όλες τις μη αφηρημένες κλάσεις που υλοποιεί μια διεπαφή, απαιτείται να εφαρμόσει όλες τις αφηρημένες μεθόδους που δηλώνονται στη διασύνδεση.

Πώς αποθηκεύονται τα δεδομένα

Η θεμελιώδης διαφορά των τριών δομών δεδομένων παραπάνω είναι ο τρόπος που αποθηκεύουν τα δεδομένα τους και προκαλούν διαφορετικές επιδόσεις για διαφορετικές λειτουργίες. Στην Java (και χρησιμοποιείται επίσης στο Kotlin), το ArrayList και το Vector χρησιμοποιούν ένα Array για την αποθήκευση των στοιχείων του, ενώ το LinkedList αποθηκεύει τα στοιχεία του σε μια διπλά συνδεδεμένη λίστα.

Στην επιστήμη των υπολογιστών, ένας διπλά συνδεδεμένος κατάλογος είναι μια συνδεδεμένη δομή δεδομένων που αποτελείται από ένα σύνολο διαδοχικά συνδεδεμένων αρχείων που ονομάζονται κόμβοι. Κάθε κόμβος περιέχει δύο πεδία, που ονομάζονται συνδέσεις, που είναι αναφορές στον προηγούμενο και στον επόμενο κόμβο στην ακολουθία κόμβων. - Βικιπαίδεια
ArrayList (επάνω) vs LinkedList (κάτω). Πηγή https://dzone.com/storage/temp/895349-arraylist-linkedlistt.png

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

Εδώ είναι το απόσπασμα κώδικα πώς αποθηκεύει το ArrayList τα στοιχεία του στο Array.

/ **
 * Το ρυθμιστικό πίνακα στο οποίο είναι τα στοιχεία του ArrayList
 * αποθηκευμένα. Η χωρητικότητα του ArrayList είναι το μήκος αυτού
 * ρυθμιστικό πίνακα. Οποιοσδήποτε κενός πίνακας ArrayList με στοιχείοData ==
 * DEFAULTCAPACITY_EMPTY_ELEMENTDATA θα επεκταθεί σε
 * DEFAULT_CAPACITY όταν προστεθεί το πρώτο στοιχείο.
 * /
μεταβατικό Αντικείμενο [] στοιχεία στοιχείων; // μη-ιδιωτικό για να απλοποιήσει το ένθετο
                                // πρόσβαση στην τάξη

Και εδώ είναι πώς το Vector αποθηκεύει τα στοιχεία τους επίσης στο Array.

/ **
 * Το buffer ρυθμιστικό στο οποίο τα στοιχεία του φορέα είναι
 * αποθηκευμένα. Η χωρητικότητα του διανύσματος είναι το μήκος αυτής της συστοιχίας
 * buffer, και είναι τουλάχιστον αρκετά μεγάλο για να περιέχει όλα τα διάνυσμα
 * στοιχεία.
 *
 * 

Οποιαδήποτε στοιχεία πίνακα μετά το τελευταίο στοιχείο του Vector  * είναι μηδενικές.  *  * @κατα συρροη  * / προστατευμένο Αντικείμενο [] elementData;

Στο παραπάνω απόσπασμα κώδικα, μπορούμε να δούμε ότι τόσο το ArrayList όσο και ο Vector αποθηκεύουν τα στοιχεία του σε μια μεταβλητή named elementDatawith Object [] ως τον τύπο του. Γιατί αντικειμένων []; Το αντικείμενο είναι μια υπερ-τάξη όλων των κλάσεων της Java. Με τον ορισμό του στοιχείουData ως Αντικείμενο [], τότε το στοιχείοDatData θα μπορούσε να αποθηκεύσει διάφορους τύπους στοιχείων, θα μπορούσε να είναι String, Integer, Double, Float ή προσαρμοσμένη κλάση όπως Pair, TextView και ούτω καθεξής.

Γιατί το ArrayList και το Vector χρησιμοποιούν έναν πίνακα για να αποθηκεύουν τα δεδομένα του; Όπως αναφέρθηκε προηγουμένως, αν και το ArrayList και το Vector χρησιμοποιούν συστοιχίες για την αποθήκευση των δεδομένων του, το ArrayList και το Vector έχουν τη δυνατότητα να έχουν δυναμικά μεγέθη (δυνατότητα αλλαγής μεγέθους). Όταν ο πίνακας που χρησιμοποιείται στα αρχεία ArrayList και Vector είναι γεμάτος, αυτά μπορούν να "αναπτυχθούν" για να διευρύνουν την χωρητικότητά τους. Το ArrayList και το Vector αυξάνουν την χωρητικότητά του δημιουργώντας ένα νέο πίνακα με μέγεθος μεγαλύτερο από το προηγούμενο μέγεθος και στη συνέχεια αντιγράφει όλα τα στοιχεία από την παλιά Array στη νέα Array χρησιμοποιώντας την εντολή Arrays.copyOf. Ακολουθεί ένα απόσπασμα κώδικα του προγράμματος στο ArrayList για να μεγεθύνετε την χωρητικότητά του (πηγή: ArrayList.java).

/ **
  * Αυξάνει την ικανότητα για να εξασφαλίσει ότι μπορεί να κρατήσει τουλάχιστον το
  * αριθμός στοιχείων που καθορίζονται από το επιχείρημα ελάχιστης χωρητικότητας.
  *
  * @param minCapacity την επιθυμητή ελάχιστη χωρητικότητα
  * /
  ιδιωτικό κενό ανάπτυξης (int minCapacity) {
      // κωδικός που έχει συνείδηση ​​υπερχείλισης
      int oldCapacity = elementData.length;
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      αν (newCapacity - minCapacity <0)
          newCapacity = minCapacity;
      αν (newCapacity - MAX_ARRAY_SIZE> 0)
          newCapacity = τεράστια ικανότητα (minCapacity);
      // minCapacity είναι συνήθως κοντά στο μέγεθος, γι 'αυτό είναι μια νίκη:
      στοιχείοData = Arrays.copyOf (στοιχείοΔεδομένα, νέαΚατότητα);
  }}

Και εδώ είναι ο τρόπος με τον οποίο το Vector μεγεθύνει την ικανότητά του (πηγή: Vector.java)

ιδιωτικό κενό ανάπτυξης (int minCapacity) {
    // κωδικός που έχει συνείδηση ​​υπερχείλισης
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((χωρητικότητα> 0);
                                     CapacityIncrement: oldCapacity);
    αν (newCapacity - minCapacity <0)
        newCapacity = minCapacity;
    αν (newCapacity - MAX_ARRAY_SIZE> 0)
        newCapacity = τεράστια ικανότητα (minCapacity);
    στοιχείοData = Arrays.copyOf (στοιχείοΔεδομένα, νέαΚατότητα);
}}

Η υλοποίηση διάνυσμα είναι σχεδόν ίδια με ArrayList, και η μόνη διαφορά είναι όλες οι λειτουργίες στο Vector συγχρονίζονται που κάνει οποιαδήποτε μέθοδο που αγγίζει τα περιεχόμενα του Vector είναι ασφαλές νήμα.

Έτσι ποια είναι η καλύτερη, ArrayList, LinkedList ή Vector; Για να απαντήσετε σε αυτή την ερώτηση, συγκρίνετε την απόδοση για τις συνήθεις λειτουργίες μέσα στο ArrayList και το LinkedList. Δεδομένου ότι η εφαρμογή ArrayList και Vector είναι σχεδόν ίδια, η απόδοσή τους θα ήταν σχεδόν ίδια.

Σύγκριση απόδοσης μεταξύ του ArrayList και του LinkedList

Από τον παραπάνω πίνακα βλέπουμε ότι δεν υπάρχει ασημένια σφαίρα για όλες τις λειτουργίες. Το ArrayList είναι ανώτερο από το LinkedList σε τυχαία πρόσβαση (get). ArrayList καλύτερα από το LinkedList επειδή το ArrayList αποθηκεύει τα στοιχεία του σε μια Array ενώ το LinkedList αποθηκεύει τα στοιχεία του μέσα στον συνδεδεμένο Κόμβο. Για παράδειγμα, για να πάρουμε το 5ο στοιχείο, το ArrayList και το Vector μπορούν να πάρουν απευθείας το στοιχείο τους χρησιμοποιώντας το δείκτη, αφού το ArrayList και το Vector ουσιαστικά είναι ένας πίνακας, ενώ το LinkedList πρέπει να επαναληφθεί για να βρει το πέμπτο στοιχείο, επειδή στο LinkedList, και το τελευταίο στοιχείο μόνο.

Για το insertFirst και το deleteFirst, το LinkedList είναι ανώτερο από το ArrayList. Το ArrayList απαιτεί μεγάλη προσπάθεια να προσθέσετε ένα στοιχείο στην αρχή (πρώτο ευρετήριο) ή να διαγράψετε το πρώτο στοιχείο επειδή το ArrayList πρέπει να μετατοπίσει τα ακόλουθα στοιχεία μετά την προσθήκη ή τη διαγραφή. Ενώ το LinkedList χρειάζεται μόνο να αντικαταστήσει / θέσει τους δείκτες του. Όσο για άλλες λειτουργίες, τόσο το ArrayList όσο και το LinkedList έχουν σχετικά την ίδια απόδοση.

Έτσι ποια είναι η καλύτερη, ArrayList, LinkedList ή Vector; Ανάλογα με τις ανάγκες σας. Εάν χρησιμοποιείτε τυχαία πρόσβαση (get) συχνότερα, τότε το ArrayList και το Vector είναι μια καλή επιλογή. Επιλέξτε Vector εάν χρειάζεστε μια συλλογή ασφαλών με νήματα. Αλλά αν κάνετε συχνά προσθήκες ή διαγραφές στην πρώτη θέση (ευρετήριο), το LinkedList είναι μια καλύτερη επιλογή.

Υπάρχει ένα άλλο ADT που χρησιμοποιείται συνήθως κατά την ανάπτυξη εφαρμογών όπως το Set, Map και PriorityQueue. Για να γνωρίζετε πώς αποθηκεύουν τα δεδομένα τους, πώς λειτουργούν και πότε πρέπει να χρησιμοποιείτε, κρατήστε μείνετε συντονισμένοι στο Medium μου.