1 00:00:00,000 --> 00:00:03,381 >> [Παίζει μουσική] 2 00:00:03,381 --> 00:00:04,604 3 00:00:04,604 --> 00:00:05,520 DOUG LLOYD: Εντάξει. 4 00:00:05,520 --> 00:00:07,860 Έτσι, αν έχετε μόλις τελειώσει η βίντεο σε μεμονωμένα-συνδεδεμένες λίστες συγγνώμη 5 00:00:07,860 --> 00:00:09,568 Σου άφησα έξω από μια λίγο δραματική στιγμή. 6 00:00:09,568 --> 00:00:12,790 Αλλά είμαι χαρούμενος που είστε εδώ για να ολοκληρώσετε η ιστορία του διπλά συνδεδεμένες λίστες. 7 00:00:12,790 --> 00:00:15,250 >> Έτσι, αν θυμάστε από ότι το βίντεο, μιλήσαμε 8 00:00:15,250 --> 00:00:18,500 σχετικά με τον τρόπο που συνδέονται με μεμονωμένα πίνακες αυτοί παρακολουθούν την ικανότητά μας 9 00:00:18,500 --> 00:00:22,090 να ασχοληθεί με πληροφορίες όπου ο αριθμός των στοιχείων 10 00:00:22,090 --> 00:00:24,442 ή ο αριθμός των αντικειμένων στο μια λίστα μπορεί να αυξηθεί ή να συρρικνωθεί. 11 00:00:24,442 --> 00:00:26,400 Μπορούμε τώρα να ασχοληθεί με κάτι τέτοιο, όπου 12 00:00:26,400 --> 00:00:28,310 Εμείς δεν θα μπορούσε να ασχοληθεί με το θέμα με συστοιχίες. 13 00:00:28,310 --> 00:00:30,560 >> Αλλά πάσχουν από μία κρίσιμος περιορισμός οποία 14 00:00:30,560 --> 00:00:33,790 είναι ότι με ένα μεμονωμένα-συνδεδεμένο λίστα, δεν μπορούμε παρά ποτέ κινηθεί 15 00:00:33,790 --> 00:00:36,200 σε μία μόνο κατεύθυνση μέσω του καταλόγου. 16 00:00:36,200 --> 00:00:39,010 Και η μόνη πραγματική κατάσταση όπου αυτό μπορεί να γίνει ένα πρόβλημα 17 00:00:39,010 --> 00:00:41,250 ήταν όταν προσπαθούσαμε να διαγράψετε ένα στοιχείο. 18 00:00:41,250 --> 00:00:46,000 Και δεν είχαμε καν συζητήσει πώς να το κάνουμε σε μεμονωμένα-συνδεδεμένη λίστα με ψευδοκώδικα. 19 00:00:46,000 --> 00:00:48,797 Είναι σίγουρα εφικτό, αλλά μπορεί να είναι ένα κομμάτι από μια ταλαιπωρία. 20 00:00:48,797 --> 00:00:50,630 Έτσι, αν βρείτε τον εαυτό σας σε μια κατάσταση όπου 21 00:00:50,630 --> 00:00:53,175 προσπαθείτε να διαγράψετε ενιαία στοιχεία από τη λίστα 22 00:00:53,175 --> 00:00:55,430 ή πρόκειται να απαιτείται ότι θα πρέπει να διαγράψετε 23 00:00:55,430 --> 00:00:57,970 ενιαία στοιχεία από η λίστα, ίσως να θέλετε 24 00:00:57,970 --> 00:01:02,090 να εξετάσει τη χρήση ενός διπλά συνδεδεμένο λίστα αντί για μεμονωμένα-συνδεδεμένη λίστα. 25 00:01:02,090 --> 00:01:06,320 Επειδή διπλά συνδεδεμένες λίστες σας επιτρέπουν να κινηθούν τόσο προς τα εμπρός και προς τα πίσω 26 00:01:06,320 --> 00:01:09,340 στη λίστα αντί ακριβώς μπροστά από την list-- 27 00:01:09,340 --> 00:01:13,950 μόνο με την προσθήκη ενός επιπλέον στοιχείου τον ορισμό δομή μας 28 00:01:13,950 --> 00:01:16,690 για το διπλά συνδεδεμένη λίστα κόμβων. 29 00:01:16,690 --> 00:01:19,770 >> Και πάλι, αν είστε δεν πρόκειται να να διαγραφή ενιαία στοιχεία 30 00:01:19,770 --> 00:01:24,810 από την list-- επειδή είμαστε προσθέτοντας ένα επιπλέον πεδίο στη δομή μας 31 00:01:24,810 --> 00:01:28,340 ορισμό, οι ίδιοι οι κόμβοι για διπλά συνδεδεμένες λίστες 32 00:01:28,340 --> 00:01:29,550 πρόκειται να είναι μεγαλύτερο. 33 00:01:29,550 --> 00:01:31,600 Θα πάμε να ρίξουμε περισσότερο bytes της μνήμης. 34 00:01:31,600 --> 00:01:34,160 Και έτσι, αν αυτό δεν είναι κάτι εσείς πρόκειται να πρέπει να κάνουμε, 35 00:01:34,160 --> 00:01:36,300 μπορείτε να αποφασίσετε ότι είναι Δεν αξίζει το εμπόριο off 36 00:01:36,300 --> 00:01:39,360 να πρέπει να δαπανήσει τα επιπλέον bytes μνήμης που απαιτείται 37 00:01:39,360 --> 00:01:43,940 για μια διπλά συνδεδεμένη λίστα, αν δεν είστε πρόκειται να διαγραφή ενιαία στοιχεία. 38 00:01:43,940 --> 00:01:46,760 Αλλά είναι επίσης δροσερό για άλλα πράγματα. 39 00:01:46,760 --> 00:01:51,260 >> Έτσι, όπως είπα, εμείς απλά πρέπει να προσθέσουμε ένα ενιαίο πεδίο στη δομή μας 40 00:01:51,260 --> 00:01:55,360 definition-- αυτή την ιδέα του προηγούμενου δείκτη. 41 00:01:55,360 --> 00:01:58,620 Έτσι, με απλά-συνδεδεμένη λίστα, εμείς έχουν την τιμή και το επόμενο δείκτη, 42 00:01:58,620 --> 00:02:02,850 έτσι ώστε η διπλά συνδεδεμένη λίστα έχει μόνο ένας τρόπος για να κινηθεί προς τα πίσω, καθώς και. 43 00:02:02,850 --> 00:02:04,960 >> Τώρα, στην μεμονωμένα που συνδέονται με λίστα βίντεο, μιλήσαμε 44 00:02:04,960 --> 00:02:07,210 γι 'αυτές είναι πέντε από τα βασικά πράγματα που πρέπει να 45 00:02:07,210 --> 00:02:09,449 είναι σε θέση να κάνει για να συνεργαστεί με συνδεδεμένες λίστες. 46 00:02:09,449 --> 00:02:12,880 Και για τα περισσότερα από αυτά, το γεγονός ότι είναι μια διπλά συνδεδεμένη λίστα 47 00:02:12,880 --> 00:02:14,130 Δεν είναι πραγματικά ένα μεγάλο άλμα. 48 00:02:14,130 --> 00:02:17,936 Μπορούμε ακόμα να αναζητήσετε μέσα από απλά κινείται προς τα εμπρός από την αρχή μέχρι το τέλος. 49 00:02:17,936 --> 00:02:20,810 Μπορούμε ακόμα να δημιουργήσουμε ένα κόμβο από αέρα κοπανιστό, λίγο πολύ με τον ίδιο τρόπο. 50 00:02:20,810 --> 00:02:23,591 Μπορούμε να διαγράψετε τις λίστες αρκετά Με τον ίδιο τρόπο πάρα πολύ. 51 00:02:23,591 --> 00:02:25,340 Τα μόνα πράγματα που είναι ελαφρά διαφορετική, 52 00:02:25,340 --> 00:02:28,970 Πραγματικά, τοποθετείτε νέων κόμβων στη λίστα, 53 00:02:28,970 --> 00:02:33,722 και θα μιλήσουμε επιτέλους για διαγραφή ένα μόνο στοιχείο από τη λίστα, καθώς και. 54 00:02:33,722 --> 00:02:35,430 Και πάλι, λίγο πολύ οι άλλοι τρεις, είμαστε 55 00:02:35,430 --> 00:02:37,888 Δεν πρόκειται να μιλήσω γι 'αυτούς τώρα επειδή είναι ακριβώς 56 00:02:37,888 --> 00:02:43,920 πολύ μικρές tweaks για τις ιδέες που συζητούνται σε μεμονωμένα-συνδεδεμένη λίστα βίντεο. 57 00:02:43,920 --> 00:02:46,292 >> Ας προστεθεί ένα νέο κόμβο σε μια διπλά-συνδεδεμένη λίστα. 58 00:02:46,292 --> 00:02:48,750 Μιλήσαμε για να γίνει αυτό για μεμονωμένα, συνδεδεμένες λίστες, καθώς και, 59 00:02:48,750 --> 00:02:52,020 αλλά υπάρχει μια-δυο επιπλέον πιάνει με διπλά συνδεδεμένες λίστες. 60 00:02:52,020 --> 00:02:55,280 Είμαστε [? περνώντας?] στο κεφάλι της απαριθμήσω εδώ και κάποια αυθαίρετη τιμή, 61 00:02:55,280 --> 00:02:58,600 και θέλουμε να πάρει το νέο επικεφαλής του καταλόγου έξω από αυτή τη λειτουργία. 62 00:02:58,600 --> 00:03:01,414 Γι 'αυτό επιστρέφει ένα αστέρι dllnode. 63 00:03:01,414 --> 00:03:02,330 Έτσι, ποια είναι τα βήματα; 64 00:03:02,330 --> 00:03:04,496 Πρόκειται, και πάλι, πολύ παρόμοιες σε μεμονωμένα-συνδεδεμένες λίστες 65 00:03:04,496 --> 00:03:05,670 με ένα επιπλέον προσθήκη. 66 00:03:05,670 --> 00:03:08,900 Θέλουμε να διαθέτει χώρο για ένα νέο κόμβου και έλεγχο για να βεβαιωθείτε ότι είναι έγκυρο. 67 00:03:08,900 --> 00:03:11,510 Θέλουμε να γεμίσουν αυτόν τον κόμβο μέχρι με ό, τι πληροφορίες που 68 00:03:11,510 --> 00:03:12,564 θέλετε να βάλετε σε αυτό. 69 00:03:12,564 --> 00:03:15,480 Το τελευταίο πράγμα που χρειαζόμαστε για να το do-- επιπλέον πράγμα που πρέπει να κάνουμε, rather-- 70 00:03:15,480 --> 00:03:19,435 είναι να καθορίσει το δείκτη Προηγούμενο του παλαιού επικεφαλής της λίστας. 71 00:03:19,435 --> 00:03:21,310 Να θυμάστε ότι επειδή διπλά-συνδεδεμένες λίστες, 72 00:03:21,310 --> 00:03:23,110 μπορούμε να προχωρήσουμε προς τα εμπρός και η οποία backwards-- 73 00:03:23,110 --> 00:03:27,080 σημαίνει ότι κάθε κόμβος δείχνει πραγματικά σε δύο άλλους κόμβους αντί για ένα. 74 00:03:27,080 --> 00:03:29,110 Και γι 'αυτό πρέπει να καθοριστεί το παλιό επικεφαλής της λίστας 75 00:03:29,110 --> 00:03:32,151 να επισημάνει προς τα πίσω με το νέο επικεφαλής της η συνδεδεμένη λίστα, η οποία ήταν κάτι 76 00:03:32,151 --> 00:03:33,990 δεν είχαμε να κάνουμε πριν. 77 00:03:33,990 --> 00:03:37,420 Και όπως και πριν, εμείς απλά να επιστρέψει μια δείκτη στη νέα επικεφαλής της λίστας. 78 00:03:37,420 --> 00:03:38,220 >> Έτσι, εδώ είναι μια λίστα. 79 00:03:38,220 --> 00:03:40,144 Θέλουμε να εισάγετε 12 σε αυτή τη λίστα. 80 00:03:40,144 --> 00:03:42,060 Παρατηρήστε ότι το διάγραμμα είναι ελαφρώς διαφορετική. 81 00:03:42,060 --> 00:03:47,710 Κάθε κόμβος περιέχει τρεις fields-- δεδομένων, και ένα επόμενο δείκτη στο κόκκινο, 82 00:03:47,710 --> 00:03:50,170 και ένα προηγούμενο δείκτη στο μπλε. 83 00:03:50,170 --> 00:03:54,059 Τίποτα δεν έρχεται πριν από την 15 κόμβων, Προηγούμενο έτσι ο δείκτης του είναι μηδενική. 84 00:03:54,059 --> 00:03:55,350 Είναι η αρχή της λίστας. 85 00:03:55,350 --> 00:03:56,560 Δεν υπάρχει τίποτα ενώπιόν του. 86 00:03:56,560 --> 00:04:03,350 Και τίποτα δεν έρχεται μετά από το 10 κόμβων και έτσι είναι επόμενο δείκτη είναι μηδενική, καθώς και. 87 00:04:03,350 --> 00:04:05,616 >> Ας προσθέσουμε λοιπόν 12 σε αυτή τη λίστα. 88 00:04:05,616 --> 00:04:08,070 Χρειαζόμαστε [δεν ακούγεται] χώρο για τον κόμβο. 89 00:04:08,070 --> 00:04:11,480 Βάλαμε 12 στο εσωτερικό του. 90 00:04:11,480 --> 00:04:14,840 Και πάλι, θα πρέπει να είναι πραγματικά Προσέξτε να μην σπάσει η αλυσίδα. 91 00:04:14,840 --> 00:04:17,144 Θέλουμε να αλλάξετε το δείκτες με τη σωστή σειρά. 92 00:04:17,144 --> 00:04:19,519 Και μερικές φορές αυτό μπορεί να mean-- όπως θα δούμε ιδιαίτερα 93 00:04:19,519 --> 00:04:24,120 με delete-- που έχουμε κάποια περιττή δείκτες, αλλά αυτό είναι εντάξει. 94 00:04:24,120 --> 00:04:25,750 >> Έτσι, αυτό που θέλουμε να κάνουμε πρώτα; 95 00:04:25,750 --> 00:04:28,290 Θα ήθελα να συστήσω το τα πράγματα μάλλον θα πρέπει να 96 00:04:28,290 --> 00:04:35,350 κάνετε είναι να συμπληρώσετε τις υποδείξεις του 12 κόμβο πριν αγγίξετε οποιονδήποτε άλλον. 97 00:04:35,350 --> 00:04:38,640 Έτσι, αυτό είναι 12 πρόκειται να επισημάνω το επόμενο βήμα; 98 00:04:38,640 --> 00:04:39,860 15. 99 00:04:39,860 --> 00:04:42,430 Αυτό που έρχεται πριν από τις 12; 100 00:04:42,430 --> 00:04:43,640 Τίποτα. 101 00:04:43,640 --> 00:04:46,280 Τώρα έχουμε γεμίσει το επιπλέον πληροφορίες σε 12 102 00:04:46,280 --> 00:04:49,320 έτσι ώστε να έχει προηγούμενο, επόμενο, και την αξία. 103 00:04:49,320 --> 00:04:53,505 >> Τώρα μπορούμε να έχουμε αυτό το επιπλέον 15-- βήμα μιλούσαμε about-- μας 104 00:04:53,505 --> 00:04:56,590 μπορεί να έχει 15 στοιχείο πίσω στο 12. 105 00:04:56,590 --> 00:04:59,634 Και τώρα μπορούμε να προχωρήσουμε στο κεφάλι του η συνδεδεμένη λίστα με επίσης 12. 106 00:04:59,634 --> 00:05:02,550 Έτσι είναι αρκετά παρόμοιο με αυτό που έκαναν με μεμονωμένα-συνδεδεμένες λίστες, 107 00:05:02,550 --> 00:05:06,940 εκτός από το επιπλέον βήμα της που συνδέει την παλιά κεφαλή της λίστας 108 00:05:06,940 --> 00:05:09,810 πίσω στο νέο επικεφαλής της λίστας. 109 00:05:09,810 --> 00:05:12,170 >> Τώρα ας επιτέλους να διαγράψετε ένας κόμβος από μια συνδεδεμένη λίστα. 110 00:05:12,170 --> 00:05:14,350 Ας πούμε ότι έχουμε κάποια άλλη λειτουργία που 111 00:05:14,350 --> 00:05:18,080 είναι να βρει έναν κόμβο που θέλετε να διαγράψετε και μας έχει δώσει ένα δείκτη ακριβώς 112 00:05:18,080 --> 00:05:19,710 ο κόμβος που θέλετε να διαγράψετε. 113 00:05:19,710 --> 00:05:22,360 Εμείς δεν χρειάζεται καν να πούμε το need-- κεφαλή εξακολουθεί να είναι σε παγκόσμιο επίπεδο δηλωθεί. 114 00:05:22,360 --> 00:05:23,590 Δεν χρειαζόμαστε το κεφάλι εδώ. 115 00:05:23,590 --> 00:05:26,830 Όλη αυτή η λειτουργία είναι να κάνει έχουμε βρήκε ένα δείκτη ακριβώς εμείς κόμβο 116 00:05:26,830 --> 00:05:28,090 θέλουν να ξεφορτωθούν. 117 00:05:28,090 --> 00:05:28,940 Ας απαλλαγούμε από αυτό. 118 00:05:28,940 --> 00:05:31,859 Είναι πολύ πιο εύκολο με διπλά συνδεδεμένες λίστες. 119 00:05:31,859 --> 00:05:33,650 First-- είναι πραγματικά μόλις δύο πράγματα. 120 00:05:33,650 --> 00:05:38,760 Εμείς το μόνο που χρειάζεται για να καθορίσει τη γύρω δείκτες κόμβοι », έτσι ώστε να υπερπηδήσει 121 00:05:38,760 --> 00:05:40,240 ο κόμβος που θέλετε να διαγράψετε. 122 00:05:40,240 --> 00:05:43,484 Και τότε μπορούμε να διαγράψετε αυτόν τον κόμβο. 123 00:05:43,484 --> 00:05:45,150 Έτσι και πάλι, είμαστε απλά να περάσει από εδώ. 124 00:05:45,150 --> 00:05:49,625 Έχουμε προφανώς αποφάσισε ότι θέλουμε να διαγράψετε τον κόμβο Χ 125 00:05:49,625 --> 00:05:51,500 Και πάλι, αυτό που είμαι κάνει here-- από την τρόπο-- 126 00:05:51,500 --> 00:05:54,580 είναι μια γενική περίπτωση για ένα κόμβου που είναι στη μέση. 127 00:05:54,580 --> 00:05:56,547 Υπάρχουν μια-δυο επιπλέον προειδοποιήσεις που εσείς 128 00:05:56,547 --> 00:05:59,380 πρέπει να ληφθούν υπόψη όταν είστε διαγραφή η ίδια η αρχή της λίστας 129 00:05:59,380 --> 00:06:01,040 ή το τέλος της λίστας. 130 00:06:01,040 --> 00:06:03,730 Υπάρχει ένα ζευγάρι ειδικών περιπτώσεις εστία του για να ασχοληθεί με τα εκεί. 131 00:06:03,730 --> 00:06:07,960 >> Έτσι, αυτό λειτουργεί για τη διαγραφή κάθε κόμβο στη μέση της μιας list-- ότι 132 00:06:07,960 --> 00:06:11,550 έχει έννομο δείκτη προς τα εμπρός και μια νόμιμη δείκτη προς τα πίσω, 133 00:06:11,550 --> 00:06:14,460 νόμιμο Προηγούμενο και Επόμενο δείκτη. 134 00:06:14,460 --> 00:06:16,530 Και πάλι, αν εργάζεστε με τα άκρα, θα 135 00:06:16,530 --> 00:06:18,500 πρέπει να χειριστούν εκείνες λίγο διαφορετικά, 136 00:06:18,500 --> 00:06:19,570 και εμείς δεν πρόκειται να μιλήσουμε γι 'αυτό τώρα. 137 00:06:19,570 --> 00:06:21,319 Αλλά μπορείτε πιθανώς να καταλάβω τι χρειάζεται 138 00:06:21,319 --> 00:06:24,610 πρέπει να γίνει μόνο από αυτό το βίντεο. 139 00:06:24,610 --> 00:06:28,910 >> Έτσι έχουμε απομονωθεί Χ Χ είναι ο κόμβος που θέλετε να διαγράψετε από τη λίστα. 140 00:06:28,910 --> 00:06:30,140 Τι κάνουμε? 141 00:06:30,140 --> 00:06:32,800 Κατ 'αρχάς, θα πρέπει να αναδιατάξετε οι εξωτερικοί δείκτες. 142 00:06:32,800 --> 00:06:35,815 Πρέπει να αναδιατάξετε 9, δίπλα στο υπερπηδήσει 13 143 00:06:35,815 --> 00:06:38,030 και το σημείο στο οποίο 10-- είναι ό, τι έχουμε κάνει ακριβώς. 144 00:06:38,030 --> 00:06:41,180 Και πρέπει επίσης να αναδιάταξη του 10 Προηγούμενη 145 00:06:41,180 --> 00:06:44,610 να επισημάνει 9 αντί για 13 δείχνουν. 146 00:06:44,610 --> 00:06:46,490 >> Έτσι και πάλι, αυτή ήταν η διάγραμμα για να αρχίσει με. 147 00:06:46,490 --> 00:06:47,730 Αυτή ήταν η αλυσίδα μας. 148 00:06:47,730 --> 00:06:51,027 Πρέπει να υπερπηδήσει 13, αλλά πρέπει να διατηρήσουμε επίσης 149 00:06:51,027 --> 00:06:52,110 η ακεραιότητα του καταλόγου. 150 00:06:52,110 --> 00:06:54,680 Δεν θέλουμε να χάσουμε οποιοδήποτε πληροφορίες σε οποιαδήποτε κατεύθυνση. 151 00:06:54,680 --> 00:06:59,620 Πρέπει, λοιπόν, να αναδιατάξετε οι δείκτες προσεκτικά 152 00:06:59,620 --> 00:07:02,240 έτσι ώστε να μην σπάσει την αλυσίδα καθόλου. 153 00:07:02,240 --> 00:07:05,710 >> Έτσι μπορούμε να πούμε 9 του δείκτη Επόμενο επισημαίνει στο ίδιο μέρος 154 00:07:05,710 --> 00:07:08,040 ότι δεκατρία του Επόμενη δείκτης δείχνει αυτή τη στιγμή. 155 00:07:08,040 --> 00:07:10,331 Επειδή είμαστε τελικά πρόκειται να θέλουν να υπερπηδήσει 13. 156 00:07:10,331 --> 00:07:13,750 Έτσι, όπου κι 13 πόντους επόμενο, θα θέλω να επισημάνω εννέα εκεί αντ 'αυτού. 157 00:07:13,750 --> 00:07:15,200 Έτσι, αυτό είναι αυτό. 158 00:07:15,200 --> 00:07:20,370 Και στη συνέχεια, όπου με 13 βαθμούς πίσω σε, ό, τι έρχεται πριν από τις 13, 159 00:07:20,370 --> 00:07:24,800 θέλουμε να επισημάνω 10 να ότι αντί 13. 160 00:07:24,800 --> 00:07:29,290 Τώρα παρατηρήσετε, αν ακολουθήσετε τα βέλη, μπορούμε να πέσει 13 161 00:07:29,290 --> 00:07:32,380 χωρίς να χάνει καμία πληροφορία. 162 00:07:32,380 --> 00:07:36,002 Έχουμε διατηρήσει την ακεραιότητα της λίστας, κινείται προς τα εμπρός και προς τα πίσω. 163 00:07:36,002 --> 00:07:38,210 Και τότε μπορούμε ακριβώς το είδος από το καθαρίσει λίγο 164 00:07:38,210 --> 00:07:40,930 τραβώντας τον κατάλογο μαζί. 165 00:07:40,930 --> 00:07:43,270 Γι 'αυτό και η αναδιατάσσεται δείκτες και στις δύο πλευρές. 166 00:07:43,270 --> 00:07:46,231 Και τότε θα απελευθερωθεί το Χ κόμβο που περιείχε 13, 167 00:07:46,231 --> 00:07:47,480 και δεν είχαμε σπάσει την αλυσίδα. 168 00:07:47,480 --> 00:07:50,980 Έτσι κάναμε καλή. 169 00:07:50,980 --> 00:07:53,000 >> Τελική σημείωση εδώ για συνδεδεμένες λίστες. 170 00:07:53,000 --> 00:07:55,990 Έτσι, τόσο μονο-ή διπλο-συνδεδεμένο καταλόγους, όπως έχουμε δει, 171 00:07:55,990 --> 00:07:58,959 υποστήριξη πραγματικά αποτελεσματική εισαγωγή και τη διαγραφή των στοιχείων. 172 00:07:58,959 --> 00:08:00,750 Μπορείτε να το κάνετε λίγο πολύ το σε σταθερό χρόνο. 173 00:08:00,750 --> 00:08:03,333 Τι είπε πρέπει να κάνουμε για να διαγράψετε ένα στοιχείο ακριβώς πριν από ένα δευτερόλεπτο; 174 00:08:03,333 --> 00:08:04,440 Προχωρήσαμε ένα δείκτη. 175 00:08:04,440 --> 00:08:05,920 Κινηθήκαμε άλλο δείκτη. 176 00:08:05,920 --> 00:08:07,915 Έχουμε απελευθερωθεί X-- πήρε τρεις πράξεις. 177 00:08:07,915 --> 00:08:14,500 Παίρνει πάντα τρεις επιχειρήσεις να διαγράψετε αυτό node-- να ελευθερώσει έναν κόμβο. 178 00:08:14,500 --> 00:08:15,280 >> Πώς εισάγουμε; 179 00:08:15,280 --> 00:08:17,280 Λοιπόν, είμαστε απλά πάντα στερέωση κατά την έναρξη 180 00:08:17,280 --> 00:08:19,400 αν είμαστε αποτελεσματικά την εισαγωγή. 181 00:08:19,400 --> 00:08:21,964 Πρέπει, λοιπόν, να rearrange-- ανάλογα με το αν είναι 182 00:08:21,964 --> 00:08:24,380 ένα μονο-ή ή διπλά συνδεδεμένη λίστα, ίσως χρειαστεί να κάνετε τρεις 183 00:08:24,380 --> 00:08:26,824 ή τέσσερις πράξεις max. 184 00:08:26,824 --> 00:08:28,365 Αλλά και πάλι, είναι πάντα τρεις ή τέσσερις. 185 00:08:28,365 --> 00:08:30,531 Δεν έχει σημασία πόσες στοιχεία είναι στη λίστα μας, 186 00:08:30,531 --> 00:08:33,549 είναι πάντα τρεις ή τέσσερις operations-- ακριβώς όπως διαγραφή είναι πάντα 187 00:08:33,549 --> 00:08:35,320 τρεις ή τέσσερις πράξεις. 188 00:08:35,320 --> 00:08:36,919 Είναι σταθερά χρόνου. 189 00:08:36,919 --> 00:08:38,169 Έτσι, αυτό είναι πραγματικά μεγάλη. 190 00:08:38,169 --> 00:08:40,620 >> Με συστοιχίες, κάναμε κάτι σαν είδος εισαγωγής. 191 00:08:40,620 --> 00:08:44,739 Πιθανόν να υπενθυμίσει ότι η εισαγωγή του είδους δεν είναι ένα σταθερό χρόνο αλγόριθμος. 192 00:08:44,739 --> 00:08:46,030 Είναι πραγματικά αρκετά ακριβό. 193 00:08:46,030 --> 00:08:48,840 Έτσι, αυτό είναι πολύ καλύτερο για την εισαγωγή. 194 00:08:48,840 --> 00:08:51,840 Αλλά όπως ανέφερα στην μεμονωμένα-συνδεδεμένη λίστα βίντεο, 195 00:08:51,840 --> 00:08:54,030 έχουμε ένα μειονέκτημα εδώ, σωστά; 196 00:08:54,030 --> 00:08:57,580 Έχουμε χάσει την ικανότητα να τυχαία πρόσβαση σε στοιχεία. 197 00:08:57,580 --> 00:09:02,310 Δεν μπορούμε να πούμε, θέλω αριθμός στοιχείου τεσσάρων ή τον αριθμό στοιχείο 10 από μία συνδεδεμένη λίστα 198 00:09:02,310 --> 00:09:04,990 με τον ίδιο τρόπο που μπορούμε το κάνουμε αυτό με μια σειρά 199 00:09:04,990 --> 00:09:08,630 ή μπορούμε απλά άμεσα δείκτη στο στοιχείο του πίνακα μας. 200 00:09:08,630 --> 00:09:10,930 >> Και έτσι προσπαθούν να βρουν μια στοιχείο σε συνδεδεμένη list-- 201 00:09:10,930 --> 00:09:15,880 αν η αναζήτηση είναι important-- μπορεί να λάβει τώρα γραμμικό χρόνο. 202 00:09:15,880 --> 00:09:18,330 Όπως ο κατάλογος παίρνει περισσότερο, θα μπορούσε να λάβει ένα επιπλέον βήμα 203 00:09:18,330 --> 00:09:22,644 για κάθε στοιχείο στον κατάλογο Για να βρείτε αυτό που ψάχνετε. 204 00:09:22,644 --> 00:09:23,560 Έτσι υπάρχει συμβιβασμούς. 205 00:09:23,560 --> 00:09:25,780 Υπάρχει ένα κομμάτι από ένα pro και con στοιχείο εδώ. 206 00:09:25,780 --> 00:09:29,110 >> Και διπλά συνδεδεμένες λίστες δεν είναι η τελευταίο είδος του συνδυασμού δομής δεδομένων 207 00:09:29,110 --> 00:09:32,840 ότι θα μιλήσουμε για, λαμβάνοντας όλα τα βασικά δομικά 208 00:09:32,840 --> 00:09:34,865 μπλοκ C μια θέση μαζί. 209 00:09:34,865 --> 00:09:37,900 Διότι, στην πραγματικότητα, μπορούμε κάνει ακόμη καλύτερα από ό, τι αυτό 210 00:09:37,900 --> 00:09:41,970 να δημιουργήσουν μια δομή δεδομένων που να είστε σε θέση να αναζητήσετε μέσα 211 00:09:41,970 --> 00:09:43,360 σε σταθερό χρόνο πάρα πολύ. 212 00:09:43,360 --> 00:09:46,080 Αλλά περισσότερα για αυτό σε ένα άλλο βίντεο. 213 00:09:46,080 --> 00:09:47,150 >> Είμαι ο Νταγκ Lloyd. 214 00:09:47,150 --> 00:09:49,050 Αυτό είναι CS50. 215 00:09:49,050 --> 00:09:50,877