>> [Παίζει μουσική]
DOUG LLOYD: Εντάξει.
Έτσι, αν έχετε μόλις τελειώσει η βίντεο σε μεμονωμένα-συνδεδεμένες λίστες συγγνώμη
Σου άφησα έξω από μια λίγο δραματική στιγμή.
Αλλά είμαι χαρούμενος που είστε εδώ για να ολοκληρώσετε η ιστορία του διπλά συνδεδεμένες λίστες.
>> Έτσι, αν θυμάστε από ότι το βίντεο, μιλήσαμε
σχετικά με τον τρόπο που συνδέονται με μεμονωμένα πίνακες αυτοί παρακολουθούν την ικανότητά μας
να ασχοληθεί με πληροφορίες όπου ο αριθμός των στοιχείων
ή ο αριθμός των αντικειμένων στο μια λίστα μπορεί να αυξηθεί ή να συρρικνωθεί.
Μπορούμε τώρα να ασχοληθεί με κάτι τέτοιο, όπου
Εμείς δεν θα μπορούσε να ασχοληθεί με το θέμα με συστοιχίες.
>> Αλλά πάσχουν από μία κρίσιμος περιορισμός οποία
είναι ότι με ένα μεμονωμένα-συνδεδεμένο λίστα, δεν μπορούμε παρά ποτέ κινηθεί
σε μία μόνο κατεύθυνση μέσω του καταλόγου.
Και η μόνη πραγματική κατάσταση όπου αυτό μπορεί να γίνει ένα πρόβλημα
ήταν όταν προσπαθούσαμε να διαγράψετε ένα στοιχείο.
Και δεν είχαμε καν συζητήσει πώς να το κάνουμε σε μεμονωμένα-συνδεδεμένη λίστα με ψευδοκώδικα.
Είναι σίγουρα εφικτό, αλλά μπορεί να είναι ένα κομμάτι από μια ταλαιπωρία.
Έτσι, αν βρείτε τον εαυτό σας σε μια κατάσταση όπου
προσπαθείτε να διαγράψετε ενιαία στοιχεία από τη λίστα
ή πρόκειται να απαιτείται ότι θα πρέπει να διαγράψετε
ενιαία στοιχεία από η λίστα, ίσως να θέλετε
να εξετάσει τη χρήση ενός διπλά συνδεδεμένο λίστα αντί για μεμονωμένα-συνδεδεμένη λίστα.
Επειδή διπλά συνδεδεμένες λίστες σας επιτρέπουν να κινηθούν τόσο προς τα εμπρός και προς τα πίσω
στη λίστα αντί ακριβώς μπροστά από την list--
μόνο με την προσθήκη ενός επιπλέον στοιχείου τον ορισμό δομή μας
για το διπλά συνδεδεμένη λίστα κόμβων.
>> Και πάλι, αν είστε δεν πρόκειται να να διαγραφή ενιαία στοιχεία
από την list-- επειδή είμαστε προσθέτοντας ένα επιπλέον πεδίο στη δομή μας
ορισμό, οι ίδιοι οι κόμβοι για διπλά συνδεδεμένες λίστες
πρόκειται να είναι μεγαλύτερο.
Θα πάμε να ρίξουμε περισσότερο bytes της μνήμης.
Και έτσι, αν αυτό δεν είναι κάτι εσείς πρόκειται να πρέπει να κάνουμε,
μπορείτε να αποφασίσετε ότι είναι Δεν αξίζει το εμπόριο off
να πρέπει να δαπανήσει τα επιπλέον bytes μνήμης που απαιτείται
για μια διπλά συνδεδεμένη λίστα, αν δεν είστε πρόκειται να διαγραφή ενιαία στοιχεία.
Αλλά είναι επίσης δροσερό για άλλα πράγματα.
>> Έτσι, όπως είπα, εμείς απλά πρέπει να προσθέσουμε ένα ενιαίο πεδίο στη δομή μας
definition-- αυτή την ιδέα του προηγούμενου δείκτη.
Έτσι, με απλά-συνδεδεμένη λίστα, εμείς έχουν την τιμή και το επόμενο δείκτη,
έτσι ώστε η διπλά συνδεδεμένη λίστα έχει μόνο ένας τρόπος για να κινηθεί προς τα πίσω, καθώς και.
>> Τώρα, στην μεμονωμένα που συνδέονται με λίστα βίντεο, μιλήσαμε
γι 'αυτές είναι πέντε από τα βασικά πράγματα που πρέπει να
είναι σε θέση να κάνει για να συνεργαστεί με συνδεδεμένες λίστες.
Και για τα περισσότερα από αυτά, το γεγονός ότι είναι μια διπλά συνδεδεμένη λίστα
Δεν είναι πραγματικά ένα μεγάλο άλμα.
Μπορούμε ακόμα να αναζητήσετε μέσα από απλά κινείται προς τα εμπρός από την αρχή μέχρι το τέλος.
Μπορούμε ακόμα να δημιουργήσουμε ένα κόμβο από αέρα κοπανιστό, λίγο πολύ με τον ίδιο τρόπο.
Μπορούμε να διαγράψετε τις λίστες αρκετά Με τον ίδιο τρόπο πάρα πολύ.
Τα μόνα πράγματα που είναι ελαφρά διαφορετική,
Πραγματικά, τοποθετείτε νέων κόμβων στη λίστα,
και θα μιλήσουμε επιτέλους για διαγραφή ένα μόνο στοιχείο από τη λίστα, καθώς και.
Και πάλι, λίγο πολύ οι άλλοι τρεις, είμαστε
Δεν πρόκειται να μιλήσω γι 'αυτούς τώρα επειδή είναι ακριβώς
πολύ μικρές tweaks για τις ιδέες που συζητούνται σε μεμονωμένα-συνδεδεμένη λίστα βίντεο.
>> Ας προστεθεί ένα νέο κόμβο σε μια διπλά-συνδεδεμένη λίστα.
Μιλήσαμε για να γίνει αυτό για μεμονωμένα, συνδεδεμένες λίστες, καθώς και,
αλλά υπάρχει μια-δυο επιπλέον πιάνει με διπλά συνδεδεμένες λίστες.
Είμαστε [? περνώντας?] στο κεφάλι της απαριθμήσω εδώ και κάποια αυθαίρετη τιμή,
και θέλουμε να πάρει το νέο επικεφαλής του καταλόγου έξω από αυτή τη λειτουργία.
Γι 'αυτό επιστρέφει ένα αστέρι dllnode.
Έτσι, ποια είναι τα βήματα;
Πρόκειται, και πάλι, πολύ παρόμοιες σε μεμονωμένα-συνδεδεμένες λίστες
με ένα επιπλέον προσθήκη.
Θέλουμε να διαθέτει χώρο για ένα νέο κόμβου και έλεγχο για να βεβαιωθείτε ότι είναι έγκυρο.
Θέλουμε να γεμίσουν αυτόν τον κόμβο μέχρι με ό, τι πληροφορίες που
θέλετε να βάλετε σε αυτό.
Το τελευταίο πράγμα που χρειαζόμαστε για να το do-- επιπλέον πράγμα που πρέπει να κάνουμε, rather--
είναι να καθορίσει το δείκτη Προηγούμενο του παλαιού επικεφαλής της λίστας.
Να θυμάστε ότι επειδή διπλά-συνδεδεμένες λίστες,
μπορούμε να προχωρήσουμε προς τα εμπρός και η οποία backwards--
σημαίνει ότι κάθε κόμβος δείχνει πραγματικά σε δύο άλλους κόμβους αντί για ένα.
Και γι 'αυτό πρέπει να καθοριστεί το παλιό επικεφαλής της λίστας
να επισημάνει προς τα πίσω με το νέο επικεφαλής της η συνδεδεμένη λίστα, η οποία ήταν κάτι
δεν είχαμε να κάνουμε πριν.
Και όπως και πριν, εμείς απλά να επιστρέψει μια δείκτη στη νέα επικεφαλής της λίστας.
>> Έτσι, εδώ είναι μια λίστα.
Θέλουμε να εισάγετε 12 σε αυτή τη λίστα.
Παρατηρήστε ότι το διάγραμμα είναι ελαφρώς διαφορετική.
Κάθε κόμβος περιέχει τρεις fields-- δεδομένων, και ένα επόμενο δείκτη στο κόκκινο,
και ένα προηγούμενο δείκτη στο μπλε.
Τίποτα δεν έρχεται πριν από την 15 κόμβων, Προηγούμενο έτσι ο δείκτης του είναι μηδενική.
Είναι η αρχή της λίστας.
Δεν υπάρχει τίποτα ενώπιόν του.
Και τίποτα δεν έρχεται μετά από το 10 κόμβων και έτσι είναι επόμενο δείκτη είναι μηδενική, καθώς και.
>> Ας προσθέσουμε λοιπόν 12 σε αυτή τη λίστα.
Χρειαζόμαστε [δεν ακούγεται] χώρο για τον κόμβο.
Βάλαμε 12 στο εσωτερικό του.
Και πάλι, θα πρέπει να είναι πραγματικά Προσέξτε να μην σπάσει η αλυσίδα.
Θέλουμε να αλλάξετε το δείκτες με τη σωστή σειρά.
Και μερικές φορές αυτό μπορεί να mean-- όπως θα δούμε ιδιαίτερα
με delete-- που έχουμε κάποια περιττή δείκτες, αλλά αυτό είναι εντάξει.
>> Έτσι, αυτό που θέλουμε να κάνουμε πρώτα;
Θα ήθελα να συστήσω το τα πράγματα μάλλον θα πρέπει να
κάνετε είναι να συμπληρώσετε τις υποδείξεις του 12 κόμβο πριν αγγίξετε οποιονδήποτε άλλον.
Έτσι, αυτό είναι 12 πρόκειται να επισημάνω το επόμενο βήμα;
15.
Αυτό που έρχεται πριν από τις 12;
Τίποτα.
Τώρα έχουμε γεμίσει το επιπλέον πληροφορίες σε 12
έτσι ώστε να έχει προηγούμενο, επόμενο, και την αξία.
>> Τώρα μπορούμε να έχουμε αυτό το επιπλέον 15-- βήμα μιλούσαμε about-- μας
μπορεί να έχει 15 στοιχείο πίσω στο 12.
Και τώρα μπορούμε να προχωρήσουμε στο κεφάλι του η συνδεδεμένη λίστα με επίσης 12.
Έτσι είναι αρκετά παρόμοιο με αυτό που έκαναν με μεμονωμένα-συνδεδεμένες λίστες,
εκτός από το επιπλέον βήμα της που συνδέει την παλιά κεφαλή της λίστας
πίσω στο νέο επικεφαλής της λίστας.
>> Τώρα ας επιτέλους να διαγράψετε ένας κόμβος από μια συνδεδεμένη λίστα.
Ας πούμε ότι έχουμε κάποια άλλη λειτουργία που
είναι να βρει έναν κόμβο που θέλετε να διαγράψετε και μας έχει δώσει ένα δείκτη ακριβώς
ο κόμβος που θέλετε να διαγράψετε.
Εμείς δεν χρειάζεται καν να πούμε το need-- κεφαλή εξακολουθεί να είναι σε παγκόσμιο επίπεδο δηλωθεί.
Δεν χρειαζόμαστε το κεφάλι εδώ.
Όλη αυτή η λειτουργία είναι να κάνει έχουμε βρήκε ένα δείκτη ακριβώς εμείς κόμβο
θέλουν να ξεφορτωθούν.
Ας απαλλαγούμε από αυτό.
Είναι πολύ πιο εύκολο με διπλά συνδεδεμένες λίστες.
First-- είναι πραγματικά μόλις δύο πράγματα.
Εμείς το μόνο που χρειάζεται για να καθορίσει τη γύρω δείκτες κόμβοι », έτσι ώστε να υπερπηδήσει
ο κόμβος που θέλετε να διαγράψετε.
Και τότε μπορούμε να διαγράψετε αυτόν τον κόμβο.
Έτσι και πάλι, είμαστε απλά να περάσει από εδώ.
Έχουμε προφανώς αποφάσισε ότι θέλουμε να διαγράψετε τον κόμβο Χ
Και πάλι, αυτό που είμαι κάνει here-- από την τρόπο--
είναι μια γενική περίπτωση για ένα κόμβου που είναι στη μέση.
Υπάρχουν μια-δυο επιπλέον προειδοποιήσεις που εσείς
πρέπει να ληφθούν υπόψη όταν είστε διαγραφή η ίδια η αρχή της λίστας
ή το τέλος της λίστας.
Υπάρχει ένα ζευγάρι ειδικών περιπτώσεις εστία του για να ασχοληθεί με τα εκεί.
>> Έτσι, αυτό λειτουργεί για τη διαγραφή κάθε κόμβο στη μέση της μιας list-- ότι
έχει έννομο δείκτη προς τα εμπρός και μια νόμιμη δείκτη προς τα πίσω,
νόμιμο Προηγούμενο και Επόμενο δείκτη.
Και πάλι, αν εργάζεστε με τα άκρα, θα
πρέπει να χειριστούν εκείνες λίγο διαφορετικά,
και εμείς δεν πρόκειται να μιλήσουμε γι 'αυτό τώρα.
Αλλά μπορείτε πιθανώς να καταλάβω τι χρειάζεται
πρέπει να γίνει μόνο από αυτό το βίντεο.
>> Έτσι έχουμε απομονωθεί Χ Χ είναι ο κόμβος που θέλετε να διαγράψετε από τη λίστα.
Τι κάνουμε?
Κατ 'αρχάς, θα πρέπει να αναδιατάξετε οι εξωτερικοί δείκτες.
Πρέπει να αναδιατάξετε 9, δίπλα στο υπερπηδήσει 13
και το σημείο στο οποίο 10-- είναι ό, τι έχουμε κάνει ακριβώς.
Και πρέπει επίσης να αναδιάταξη του 10 Προηγούμενη
να επισημάνει 9 αντί για 13 δείχνουν.
>> Έτσι και πάλι, αυτή ήταν η διάγραμμα για να αρχίσει με.
Αυτή ήταν η αλυσίδα μας.
Πρέπει να υπερπηδήσει 13, αλλά πρέπει να διατηρήσουμε επίσης
η ακεραιότητα του καταλόγου.
Δεν θέλουμε να χάσουμε οποιοδήποτε πληροφορίες σε οποιαδήποτε κατεύθυνση.
Πρέπει, λοιπόν, να αναδιατάξετε οι δείκτες προσεκτικά
έτσι ώστε να μην σπάσει την αλυσίδα καθόλου.
>> Έτσι μπορούμε να πούμε 9 του δείκτη Επόμενο επισημαίνει στο ίδιο μέρος
ότι δεκατρία του Επόμενη δείκτης δείχνει αυτή τη στιγμή.
Επειδή είμαστε τελικά πρόκειται να θέλουν να υπερπηδήσει 13.
Έτσι, όπου κι 13 πόντους επόμενο, θα θέλω να επισημάνω εννέα εκεί αντ 'αυτού.
Έτσι, αυτό είναι αυτό.
Και στη συνέχεια, όπου με 13 βαθμούς πίσω σε, ό, τι έρχεται πριν από τις 13,
θέλουμε να επισημάνω 10 να ότι αντί 13.
Τώρα παρατηρήσετε, αν ακολουθήσετε τα βέλη, μπορούμε να πέσει 13
χωρίς να χάνει καμία πληροφορία.
Έχουμε διατηρήσει την ακεραιότητα της λίστας, κινείται προς τα εμπρός και προς τα πίσω.
Και τότε μπορούμε ακριβώς το είδος από το καθαρίσει λίγο
τραβώντας τον κατάλογο μαζί.
Γι 'αυτό και η αναδιατάσσεται δείκτες και στις δύο πλευρές.
Και τότε θα απελευθερωθεί το Χ κόμβο που περιείχε 13,
και δεν είχαμε σπάσει την αλυσίδα.
Έτσι κάναμε καλή.
>> Τελική σημείωση εδώ για συνδεδεμένες λίστες.
Έτσι, τόσο μονο-ή διπλο-συνδεδεμένο καταλόγους, όπως έχουμε δει,
υποστήριξη πραγματικά αποτελεσματική εισαγωγή και τη διαγραφή των στοιχείων.
Μπορείτε να το κάνετε λίγο πολύ το σε σταθερό χρόνο.
Τι είπε πρέπει να κάνουμε για να διαγράψετε ένα στοιχείο ακριβώς πριν από ένα δευτερόλεπτο;
Προχωρήσαμε ένα δείκτη.
Κινηθήκαμε άλλο δείκτη.
Έχουμε απελευθερωθεί X-- πήρε τρεις πράξεις.
Παίρνει πάντα τρεις επιχειρήσεις να διαγράψετε αυτό node-- να ελευθερώσει έναν κόμβο.
>> Πώς εισάγουμε;
Λοιπόν, είμαστε απλά πάντα στερέωση κατά την έναρξη
αν είμαστε αποτελεσματικά την εισαγωγή.
Πρέπει, λοιπόν, να rearrange-- ανάλογα με το αν είναι
ένα μονο-ή ή διπλά συνδεδεμένη λίστα, ίσως χρειαστεί να κάνετε τρεις
ή τέσσερις πράξεις max.
Αλλά και πάλι, είναι πάντα τρεις ή τέσσερις.
Δεν έχει σημασία πόσες στοιχεία είναι στη λίστα μας,
είναι πάντα τρεις ή τέσσερις operations-- ακριβώς όπως διαγραφή είναι πάντα
τρεις ή τέσσερις πράξεις.
Είναι σταθερά χρόνου.
Έτσι, αυτό είναι πραγματικά μεγάλη.
>> Με συστοιχίες, κάναμε κάτι σαν είδος εισαγωγής.
Πιθανόν να υπενθυμίσει ότι η εισαγωγή του είδους δεν είναι ένα σταθερό χρόνο αλγόριθμος.
Είναι πραγματικά αρκετά ακριβό.
Έτσι, αυτό είναι πολύ καλύτερο για την εισαγωγή.
Αλλά όπως ανέφερα στην μεμονωμένα-συνδεδεμένη λίστα βίντεο,
έχουμε ένα μειονέκτημα εδώ, σωστά;
Έχουμε χάσει την ικανότητα να τυχαία πρόσβαση σε στοιχεία.
Δεν μπορούμε να πούμε, θέλω αριθμός στοιχείου τεσσάρων ή τον αριθμό στοιχείο 10 από μία συνδεδεμένη λίστα
με τον ίδιο τρόπο που μπορούμε το κάνουμε αυτό με μια σειρά
ή μπορούμε απλά άμεσα δείκτη στο στοιχείο του πίνακα μας.
>> Και έτσι προσπαθούν να βρουν μια στοιχείο σε συνδεδεμένη list--
αν η αναζήτηση είναι important-- μπορεί να λάβει τώρα γραμμικό χρόνο.
Όπως ο κατάλογος παίρνει περισσότερο, θα μπορούσε να λάβει ένα επιπλέον βήμα
για κάθε στοιχείο στον κατάλογο Για να βρείτε αυτό που ψάχνετε.
Έτσι υπάρχει συμβιβασμούς.
Υπάρχει ένα κομμάτι από ένα pro και con στοιχείο εδώ.
>> Και διπλά συνδεδεμένες λίστες δεν είναι η τελευταίο είδος του συνδυασμού δομής δεδομένων
ότι θα μιλήσουμε για, λαμβάνοντας όλα τα βασικά δομικά
μπλοκ C μια θέση μαζί.
Διότι, στην πραγματικότητα, μπορούμε κάνει ακόμη καλύτερα από ό, τι αυτό
να δημιουργήσουν μια δομή δεδομένων που να είστε σε θέση να αναζητήσετε μέσα
σε σταθερό χρόνο πάρα πολύ.
Αλλά περισσότερα για αυτό σε ένα άλλο βίντεο.
>> Είμαι ο Νταγκ Lloyd.
Αυτό είναι CS50.