1
00:00:00,000 --> 00:00:03,381
>> [MUZYKI]

2
00:00:03,381 --> 00:00:04,604

3
00:00:04,604 --> 00:00:05,520
DOUG LLOYD: Wszystko w porządku.

4
00:00:05,520 --> 00:00:07,860
Więc jeśli właśnie skończył, że
wideo na pojedynczo list przepraszam powiązanych

5
00:00:07,860 --> 00:00:09,568
Zostawiłem cię na zasadzie
trochę cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Ale cieszę się, że tu jesteś, aby zakończyć
historia podwójnie połączonych listach.

7
00:00:12,790 --> 00:00:15,250
>> Więc jeśli pamiętacie z
że film, rozmawialiśmy

8
00:00:15,250 --> 00:00:18,500
o tym, jak pojedynczo-linked
Listy uczęszczają nasze możliwości

9
00:00:18,500 --> 00:00:22,090
do przetwarzania informacji
przy czym liczba elementów

10
00:00:22,090 --> 00:00:24,442
lub liczba elementów w
lista może powiększać lub zmniejszać.

11
00:00:24,442 --> 00:00:26,400
Teraz możemy zająć się
coś w tym stylu, gdzie

12
00:00:26,400 --> 00:00:28,310
nie możemy sobie z tym poradzić z tablicami.

13
00:00:28,310 --> 00:00:30,560
>> Ale oni nie cierpią z powodu jednego
Ograniczenie krytyczne, które

14
00:00:30,560 --> 00:00:33,790
jest, że z pojedynczo-linked
lista, możemy zawsze tylko przenieść

15
00:00:33,790 --> 00:00:36,200
w jednym kierunku przez liście.

16
00:00:36,200 --> 00:00:39,010
I jedynym prawdziwym sytuacja
gdzie, że może stać się problemem

17
00:00:39,010 --> 00:00:41,250
było, gdy staraliśmy się
Usuwanie pojedynczego elementu.

18
00:00:41,250 --> 00:00:46,000
I nawet nie zastanawiać się, jak to zrobić
w pojedynczo-połączonej listy w Pseudokod.

19
00:00:46,000 --> 00:00:48,797
Na pewno jest to wykonalne, ale
może to być trochę kłopotów.

20
00:00:48,797 --> 00:00:50,630
Więc jeśli znajdziesz się
W sytuacji, w której

21
00:00:50,630 --> 00:00:53,175
próbujesz usunąć
pojedyncze elementy z listy

22
00:00:53,175 --> 00:00:55,430
czy to będzie wymagane
że będziesz usuwanie

23
00:00:55,430 --> 00:00:57,970
pojedyncze elementy z
lista, możesz

24
00:00:57,970 --> 00:01:02,090
rozważyć użycie podwójnie-linked
listy, zamiast pojedynczo-połączonej listy.

25
00:01:02,090 --> 00:01:06,320
Ponieważ podwójnie związane listy pozwalają
poruszać zarówno w przód iw tył

26
00:01:06,320 --> 00:01:09,340
listę zamiast
po prostu do przodu przez list--

27
00:01:09,340 --> 00:01:13,950
po prostu dodając jeden dodatkowy element
do naszej definicji struktury

28
00:01:13,950 --> 00:01:16,690
dla węzła podwójnie połączonej listy.

29
00:01:16,690 --> 00:01:19,770
>> Ponownie, jeśli nie zamierzasz
być usunięcie pojedynczych elementów

30
00:01:19,770 --> 00:01:24,810
z list-- ponieważ dodajemy
dodatkowe pole do naszej struktury

31
00:01:24,810 --> 00:01:28,340
definicja, same węzły
dla podwójnie związane list

32
00:01:28,340 --> 00:01:29,550
będą większe.

33
00:01:29,550 --> 00:01:31,600
Zamierzają zabrać
się większej liczby bajtów pamięci.

34
00:01:31,600 --> 00:01:34,160
I tak, jeśli nie jest to coś
masz zamiar trzeba zrobić,

35
00:01:34,160 --> 00:01:36,300
może zdecydować, że to
nie warto kompromis

36
00:01:36,300 --> 00:01:39,360
musiał wydać dodatkowe
bajtów pamięci wymagane

37
00:01:39,360 --> 00:01:43,940
na podwójnie połączonej listy, jeśli nie jesteś
będzie usuwanie pojedynczych elementów.

38
00:01:43,940 --> 00:01:46,760
Ale są też fajne
na inne rzeczy też.

39
00:01:46,760 --> 00:01:51,260
>> Tak jak powiedziałem, musimy po prostu dodać
Jedno pojedyncze pole do naszej struktury

40
00:01:51,260 --> 00:01:55,360
definition-- to pojęcie
poprzedniego wskaźnika.

41
00:01:55,360 --> 00:01:58,620
Więc z pojedynczo-połączonej listy, możemy
mają wartość i następny wskaźnik,

42
00:01:58,620 --> 00:02:02,850
więc podwójnie związany lista ma tylko
sposób, aby przejść do tyłu, jak również.

43
00:02:02,850 --> 00:02:04,960
>> Teraz w pojedynczo-linked
Lista video, rozmawialiśmy

44
00:02:04,960 --> 00:02:07,210
o to pięć z
Najważniejsze rzeczy, które musisz mieć

45
00:02:07,210 --> 00:02:09,449
w stanie zrobić, aby pracować z połączonych listach.

46
00:02:09,449 --> 00:02:12,880
A dla większości z nich, fakt,
że jest to podwójnie połączonej listy

47
00:02:12,880 --> 00:02:14,130
Nie jest to duży skok.

48
00:02:14,130 --> 00:02:17,936
Nadal możemy przeszukiwać tylko przez
do przodu od początku do końca.

49
00:02:17,936 --> 00:02:20,810
Nadal możemy stworzyć węzeł z
rozrzedzone powietrze, prawie w ten sam sposób.

50
00:02:20,810 --> 00:02:23,591
Możemy usuwać list dość
podobny sposób też.

51
00:02:23,591 --> 00:02:25,340
Jedyne rzeczy, które
są nieco inne,

52
00:02:25,340 --> 00:02:28,970
Naprawdę, wstawiasz
nowe węzły na listę,

53
00:02:28,970 --> 00:02:33,722
a my w końcu mówić o usunięcie
pojedynczy element z listy, jak również.

54
00:02:33,722 --> 00:02:35,430
Ponownie, bardzo dużo
pozostałe trzy, jesteśmy

55
00:02:35,430 --> 00:02:37,888
Nie będziemy mówić o nich
właśnie teraz, bo są po prostu

56
00:02:37,888 --> 00:02:43,920
bardzo drobnych poprawek na pomysły dyskutowane
w pojedynczo-połączonej listy wideo.

57
00:02:43,920 --> 00:02:46,292
>> Warto więc wprowadzić nowy węzeł
w podwójnie połączonej listy.

58
00:02:46,292 --> 00:02:48,750
Rozmawialiśmy o tym od
pojedynczo-linked list, jak również,

59
00:02:48,750 --> 00:02:52,020
ale jest kilka dodatkowych
łapie się podwójnie połączonych listach.

60
00:02:52,020 --> 00:02:55,280
Jesteśmy [? przechodzi?] na czele
tu wymieniać, a niektóre dowolna wartość,

61
00:02:55,280 --> 00:02:58,600
i chcemy, aby dostać nową głowę
listy zewnątrz tej funkcji.

62
00:02:58,600 --> 00:03:01,414
Dlatego zwraca gwiazdę dllnode.

63
00:03:01,414 --> 00:03:02,330
Więc jakie są kroki?

64
00:03:02,330 --> 00:03:04,496
Są znowu bardzo podobny
do pojedynczo-linked list

65
00:03:04,496 --> 00:03:05,670
z dodatkowym dodatkiem.

66
00:03:05,670 --> 00:03:08,900
Chcemy przydziela miejsce na nowy
węzeł i sprawdzić, aby upewnić się, że to ważne.

67
00:03:08,900 --> 00:03:11,510
Chcemy, aby wypełnić ten węzeł się
wszelkich informacji, że

68
00:03:11,510 --> 00:03:12,564
chcesz umieścić w nim.

69
00:03:12,564 --> 00:03:15,480
Ostatnią rzeczą, jaką musimy do--
dodatkową rzeczą, jaką musimy zrobić, rather--

70
00:03:15,480 --> 00:03:19,435
to naprawić Poprzedni wskaźnik
starego czele listy.

71
00:03:19,435 --> 00:03:21,310
Pamiętaj, że z powodu
podwójnie związane z listy,

72
00:03:21,310 --> 00:03:23,110
możemy iść do przodu
i backwards-- które

73
00:03:23,110 --> 00:03:27,080
Oznacza to, że każdy węzeł rzeczywiście wskazuje
dwa inne węzły, zamiast tylko jednej.

74
00:03:27,080 --> 00:03:29,110
I tak musimy to naprawić
stary szef listy

75
00:03:29,110 --> 00:03:32,151
do punktu wstecz do nowego szefa
połączona lista, która była czymś

76
00:03:32,151 --> 00:03:33,990
nie mieliśmy do zrobienia przed.

77
00:03:33,990 --> 00:03:37,420
I jak poprzednio, po prostu zwróci
wskaźnik do nowego szefa listy.

78
00:03:37,420 --> 00:03:38,220
>> Więc oto lista.

79
00:03:38,220 --> 00:03:40,144
Chcemy, aby wstawić 12 na tej liście.

80
00:03:40,144 --> 00:03:42,060
Zauważ, że diagram
jest nieco inny.

81
00:03:42,060 --> 00:03:47,710
Każdy węzeł zawiera trzy fields--
danych, a następny wskaźnik w kolorze czerwonym,

82
00:03:47,710 --> 00:03:50,170
a Poprzedni wskaźnik w kolorze niebieskim.

83
00:03:50,170 --> 00:03:54,059
Nic nie przychodzi do węzła 15,
więc jego Poprzedni wskaźnik ma wartość null.

84
00:03:54,059 --> 00:03:55,350
Jest to początek listy.

85
00:03:55,350 --> 00:03:56,560
Nie ma nic przed nim.

86
00:03:56,560 --> 00:04:03,350
I nic nie przychodzi po węźle 10, a
więc Następny wskaźnik jest null, jak również.

87
00:04:03,350 --> 00:04:05,616
>> Warto więc dodać 12 do tej listy.

88
00:04:05,616 --> 00:04:08,070
Musimy [niesłyszalne] przestrzeń dla węzła.

89
00:04:08,070 --> 00:04:11,480
Kładziemy 12 w jej wnętrzu.

90
00:04:11,480 --> 00:04:14,840
I znów, musimy być bardzo
Uważaj, aby nie przerwać łańcuch.

91
00:04:14,840 --> 00:04:17,144
Chcemy przegrupowania
wskaźniki w odpowiedniej kolejności.

92
00:04:17,144 --> 00:04:19,519
I czasem, że może mean--
jak zobaczymy szczególnie

93
00:04:19,519 --> 00:04:24,120
z delete--, że mamy pewne
zbędnych wskazówek, ale to jest OK.

94
00:04:24,120 --> 00:04:25,750
>> Więc to, co chcemy zrobić w pierwszej kolejności?

95
00:04:25,750 --> 00:04:28,290
Polecam
rzeczy powinieneś prawdopodobnie

96
00:04:28,290 --> 00:04:35,350
nie są do wypełnienia wskaźników z 12
węzeł zanim dotkniesz ktokolwiek inny.

97
00:04:35,350 --> 00:04:38,640
Więc co jest 12 będzie wskazywać na następny?

98
00:04:38,640 --> 00:04:39,860
15.

99
00:04:39,860 --> 00:04:42,430
Co jest przed 12?

100
00:04:42,430 --> 00:04:43,640
Nic.

101
00:04:43,640 --> 00:04:46,280
Teraz mamy wypełnił
dodatkowe informacje w 12

102
00:04:46,280 --> 00:04:49,320
więc ma poprzedniej, następnej, i wartość.

103
00:04:49,320 --> 00:04:53,505
>> Teraz możemy mieć 15-- ta dodatkowa
krok rozmawialiśmy about-- my

104
00:04:53,505 --> 00:04:56,590
może mieć 15 punkt z powrotem do 12.

105
00:04:56,590 --> 00:04:59,634
A teraz możemy przejść głowę
połączony lista będzie również 12.

106
00:04:59,634 --> 00:05:02,550
Więc to jest bardzo podobne do tego, co
robią z listy połączonych pojedynczo,

107
00:05:02,550 --> 00:05:06,940
z wyjątkiem dodatkowego kroku
podłączania starego początku listy

108
00:05:06,940 --> 00:05:09,810
Powrót do nowego szefa listy.

109
00:05:09,810 --> 00:05:12,170
>> Teraz wreszcie usuwać
węzeł z innej listy.

110
00:05:12,170 --> 00:05:14,350
Więc powiedzmy, że mamy
inna funkcja

111
00:05:14,350 --> 00:05:18,080
jest znalezienie węzła chcemy usunąć
i dał nam wskaźnik do dokładnie

112
00:05:18,080 --> 00:05:19,710
węzeł, który chcemy usunąć.

113
00:05:19,710 --> 00:05:22,360
My nawet nie need-- powiedzieć
głowa jest wciąż globalnie oświadczył.

114
00:05:22,360 --> 00:05:23,590
Nie potrzebujemy tutaj głową.

115
00:05:23,590 --> 00:05:26,830
Wszystko to funkcja robi to mamy
znaleźć wskaźnik do węzła dokładnie tak my

116
00:05:26,830 --> 00:05:28,090
chcą się pozbyć.

117
00:05:28,090 --> 00:05:28,940
Miejmy się go pozbyć.

118
00:05:28,940 --> 00:05:31,859
To dużo łatwiejsze
podwójnie związany list.

119
00:05:31,859 --> 00:05:33,650
First-- to faktycznie
tylko kilka rzeczy.

120
00:05:33,650 --> 00:05:38,760
Musimy tylko ustalić otoczenie
wskaźniki węzłów ", tak aby przeskoczyć

121
00:05:38,760 --> 00:05:40,240
węzeł chcemy usunąć.

122
00:05:40,240 --> 00:05:43,484
A potem możemy usunąć ten węzeł.

123
00:05:43,484 --> 00:05:45,150
Więc jeszcze raz, po prostu przechodzi tutaj.

124
00:05:45,150 --> 00:05:49,625
Mamy najwyraźniej uznał, że
chcemy usunąć X. węzła

125
00:05:49,625 --> 00:05:51,500
I znowu, co mnie
robi here-- przez way--

126
00:05:51,500 --> 00:05:54,580
jest ogólnym przypadku dla
węzeł, który jest w środku.

127
00:05:54,580 --> 00:05:56,547
Istnieje kilka
dodatkowe zastrzeżenia, że

128
00:05:56,547 --> 00:05:59,380
należy wziąć pod uwagę, gdy usuwasz
samego początku listy

129
00:05:59,380 --> 00:06:01,040
lub bardzo koniec listy.

130
00:06:01,040 --> 00:06:03,730
Istnieje kilka specjalnych
Szafy narożne do czynienia z nie.

131
00:06:03,730 --> 00:06:07,960
>> Tak to działa na usunięcie dowolnego węzła
W środku list-- taki, który

132
00:06:07,960 --> 00:06:11,550
ma uzasadniony wskaźnik do przodu
i uzasadniony wskaźnik do tyłu,

133
00:06:11,550 --> 00:06:14,460
Poprzedni i Następny uzasadnione wskaźnik.

134
00:06:14,460 --> 00:06:16,530
Ponownie, jeśli pracujesz
z końcami, ty

135
00:06:16,530 --> 00:06:18,500
potrzebne do obsługi tych
nieco inaczej,

136
00:06:18,500 --> 00:06:19,570
a my nie będziemy
teraz o tym rozmawiać.

137
00:06:19,570 --> 00:06:21,319
Ale można chyba
dowiedzieć się, co trzeba

138
00:06:21,319 --> 00:06:24,610
do zrobienia, po prostu oglądając ten film.

139
00:06:24,610 --> 00:06:28,910
>> Więc mamy pojedyncze X. X jest węzeł
chcemy usunąć z listy.

140
00:06:28,910 --> 00:06:30,140
Co robimy?

141
00:06:30,140 --> 00:06:32,800
Po pierwsze, musimy zmienić
zewnętrzne wskaźniki.

142
00:06:32,800 --> 00:06:35,815
Musimy zmienić
9 dalej przeskoczyć 13

143
00:06:35,815 --> 00:06:38,030
i wskaż 10-- które
jest to, co właśnie zrobił.

144
00:06:38,030 --> 00:06:41,180
A trzeba też
przestawiać 10 poprzednią

145
00:06:41,180 --> 00:06:44,610
zwrócić do 9 zamiast wskazywać do 13.

146
00:06:44,610 --> 00:06:46,490
>> Więc jeszcze raz, to był
Schemat na początek.

147
00:06:46,490 --> 00:06:47,730
To był nasz łańcuch.

148
00:06:47,730 --> 00:06:51,027
Musimy przeskoczyć 13,
ale musimy również zachowanie

149
00:06:51,027 --> 00:06:52,110
integralność listy.

150
00:06:52,110 --> 00:06:54,680
Nie chcemy stracić żadnej
Informacje zawarte w obu kierunkach.

151
00:06:54,680 --> 00:06:59,620
Musimy więc zmienić
kursory ostrożnie

152
00:06:59,620 --> 00:07:02,240
więc nie przerwać łańcuch w ogóle.

153
00:07:02,240 --> 00:07:05,710
>> Można więc powiedzieć, 9 dalej wskaźnik
Wskazuje to na to samo miejsce

154
00:07:05,710 --> 00:07:08,040
że trzynaście Next
Wskaźnik wskazuje teraz.

155
00:07:08,040 --> 00:07:10,331
Ponieważ jesteśmy w końcu
będzie chciał przeskoczyć 13.

156
00:07:10,331 --> 00:07:13,750
Gdziekolwiek więc 13 punktów Następnie,
chcą dziewięć tam wskazać zamiast.

157
00:07:13,750 --> 00:07:15,200
Więc to jest to.

158
00:07:15,200 --> 00:07:20,370
I wtedy tam, gdzie 13 punktów powrotem
się, co jest przed 13,

159
00:07:20,370 --> 00:07:24,800
chcemy 10 punkt
na tym, że zamiast 13.

160
00:07:24,800 --> 00:07:29,290
Teraz zauważyć, jeśli się
strzałki, możemy upuścić 13

161
00:07:29,290 --> 00:07:32,380
bez faktycznie utraty informacji.

162
00:07:32,380 --> 00:07:36,002
Mamy przechowywane integralności listy,
ruchu do przodu i do tyłu.

163
00:07:36,002 --> 00:07:38,210
A potem możemy właśnie rodzaj
z posprzątać trochę

164
00:07:38,210 --> 00:07:40,930
pociągając za sobą listy.

165
00:07:40,930 --> 00:07:43,270
Więc przekształciła
wskaźniki z każdej strony.

166
00:07:43,270 --> 00:07:46,231
A potem uwolnił X
Węzeł, który zawierał 13,

167
00:07:46,231 --> 00:07:47,480
i nie przerwać łańcuch.

168
00:07:47,480 --> 00:07:50,980
Więc zrobiliśmy dobrze.

169
00:07:50,980 --> 00:07:53,000
>> Ostatnia uwaga tu na połączonych listach.

170
00:07:53,000 --> 00:07:55,990
Tak więc zarówno singly- i podwójnie związane
Listy, jak widzieliśmy,

171
00:07:55,990 --> 00:07:58,959
bardzo efektywne wsparcie wstawiania
i usuwanie elementów.

172
00:07:58,959 --> 00:08:00,750
Bardzo wiele można zrobić
jest w stałym czasie.

173
00:08:00,750 --> 00:08:03,333
Co musimy zrobić, aby usunąć
element po prostu drugi temu?

174
00:08:03,333 --> 00:08:04,440
Przenieśliśmy jeden wskaźnik.

175
00:08:04,440 --> 00:08:05,920
Przenieśliśmy inny wskaźnik.

176
00:08:05,920 --> 00:08:07,915
Mamy uwolnił X-- wziął trzy operacje.

177
00:08:07,915 --> 00:08:14,500
To zawsze trwa trzy operacje na
usunąć ten node-- uwolnić węzeł.

178
00:08:14,500 --> 00:08:15,280
>> Jak możemy włożyć?

179
00:08:15,280 --> 00:08:17,280
Cóż, jesteśmy po prostu zawsze
sklejaniu na początku

180
00:08:17,280 --> 00:08:19,400
jeśli mamy skutecznie włożeniem.

181
00:08:19,400 --> 00:08:21,964
Więc musimy rearrange--
w zależności czy jest to

182
00:08:21,964 --> 00:08:24,380
singly- lub podwójnie związane
Lista może musimy zrobić trzy

183
00:08:24,380 --> 00:08:26,824
lub cztery operacje max.

184
00:08:26,824 --> 00:08:28,365
Ale znowu, to zawsze trzy lub cztery.

185
00:08:28,365 --> 00:08:30,531
Nie ma znaczenia, ile
elementy są w naszej liście,

186
00:08:30,531 --> 00:08:33,549
to zawsze trzy lub cztery operations--
jak usuwanie jest zawsze

187
00:08:33,549 --> 00:08:35,320
trzy lub cztery operacje.

188
00:08:35,320 --> 00:08:36,919
Jest to stała czasowa.

189
00:08:36,919 --> 00:08:38,169
Więc to jest naprawdę wielki.

190
00:08:38,169 --> 00:08:40,620
>> Z tablicami, robimy
coś Sortowanie przez wstawianie.

191
00:08:40,620 --> 00:08:44,739
Prawdopodobnie przypomnieć, że wprowadzenie
sortowania nie jest algorytmem czas stała.

192
00:08:44,739 --> 00:08:46,030
To rzeczywiście dość drogie.

193
00:08:46,030 --> 00:08:48,840
Więc to jest o wiele lepiej do wkładania.

194
00:08:48,840 --> 00:08:51,840
Ale jak już wspomniałem w
pojedynczo-linked listy wideo

195
00:08:51,840 --> 00:08:54,030
mamy wadę tutaj, prawda?

196
00:08:54,030 --> 00:08:57,580
Straciliśmy zdolność do
losowo dostęp elementy.

197
00:08:57,580 --> 00:09:02,310
Nie możemy powiedzieć, chcę elementu numer cztery
lub element numer 10 z połączonej listy

198
00:09:02,310 --> 00:09:04,990
w ten sam sposób, że możemy
zrobić z tablicą

199
00:09:04,990 --> 00:09:08,630
lub możemy po prostu bezpośrednio indeksu
w elemencie naszej tablicy jest.

200
00:09:08,630 --> 00:09:10,930
>> A więc próbuje znaleźć
elementem połączonej list--

201
00:09:10,930 --> 00:09:15,880
jeśli przeszukiwanie jest important--
Może teraz trochę czasu liniowego.

202
00:09:15,880 --> 00:09:18,330
Ponieważ lista wydłuża się, że
może zająć jeden dodatkowy krok

203
00:09:18,330 --> 00:09:22,644
dla każdego elementu na liście w
aby znaleźć to, czego szukamy.

204
00:09:22,644 --> 00:09:23,560
Więc nie ma kompromisów.

205
00:09:23,560 --> 00:09:25,780
Jest trochę pro
i con elementem tutaj.

206
00:09:25,780 --> 00:09:29,110
>> I podwójnie związane listy nie są
ostatnia rodzaju kombinacji struktury danych

207
00:09:29,110 --> 00:09:32,840
że będziemy rozmawiać o,
biorąc wszystkie podstawowe budynku

208
00:09:32,840 --> 00:09:34,865
bloki C układania.

209
00:09:34,865 --> 00:09:37,900
Ponieważ w rzeczywistości, możemy
nawet lepiej niż to

210
00:09:37,900 --> 00:09:41,970
tworzyć strukturę danych, która
może być w stanie przeszukiwać

211
00:09:41,970 --> 00:09:43,360
w stałym czasie zbyt.

212
00:09:43,360 --> 00:09:46,080
Ale o tym w innym filmie.

213
00:09:46,080 --> 00:09:47,150
>> Jestem Doug Lloyd.

214
00:09:47,150 --> 00:09:49,050
To CS50.

215
00:09:49,050 --> 00:09:50,877