>> [MUZYKI]
DOUG LLOYD: Wszystko w porządku.
Więc jeśli właśnie skończył, że wideo na pojedynczo list przepraszam powiązanych
Zostawiłem cię na zasadzie trochę cliffhanger.
Ale cieszę się, że tu jesteś, aby zakończyć historia podwójnie połączonych listach.
>> Więc jeśli pamiętacie z że film, rozmawialiśmy
o tym, jak pojedynczo-linked Listy uczęszczają nasze możliwości
do przetwarzania informacji przy czym liczba elementów
lub liczba elementów w lista może powiększać lub zmniejszać.
Teraz możemy zająć się coś w tym stylu, gdzie
nie możemy sobie z tym poradzić z tablicami.
>> Ale oni nie cierpią z powodu jednego Ograniczenie krytyczne, które
jest, że z pojedynczo-linked lista, możemy zawsze tylko przenieść
w jednym kierunku przez liście.
I jedynym prawdziwym sytuacja gdzie, że może stać się problemem
było, gdy staraliśmy się Usuwanie pojedynczego elementu.
I nawet nie zastanawiać się, jak to zrobić w pojedynczo-połączonej listy w Pseudokod.
Na pewno jest to wykonalne, ale może to być trochę kłopotów.
Więc jeśli znajdziesz się W sytuacji, w której
próbujesz usunąć pojedyncze elementy z listy
czy to będzie wymagane że będziesz usuwanie
pojedyncze elementy z lista, możesz
rozważyć użycie podwójnie-linked listy, zamiast pojedynczo-połączonej listy.
Ponieważ podwójnie związane listy pozwalają poruszać zarówno w przód iw tył
listę zamiast po prostu do przodu przez list--
po prostu dodając jeden dodatkowy element do naszej definicji struktury
dla węzła podwójnie połączonej listy.
>> Ponownie, jeśli nie zamierzasz być usunięcie pojedynczych elementów
z list-- ponieważ dodajemy dodatkowe pole do naszej struktury
definicja, same węzły dla podwójnie związane list
będą większe.
Zamierzają zabrać się większej liczby bajtów pamięci.
I tak, jeśli nie jest to coś masz zamiar trzeba zrobić,
może zdecydować, że to nie warto kompromis
musiał wydać dodatkowe bajtów pamięci wymagane
na podwójnie połączonej listy, jeśli nie jesteś będzie usuwanie pojedynczych elementów.
Ale są też fajne na inne rzeczy też.
>> Tak jak powiedziałem, musimy po prostu dodać Jedno pojedyncze pole do naszej struktury
definition-- to pojęcie poprzedniego wskaźnika.
Więc z pojedynczo-połączonej listy, możemy mają wartość i następny wskaźnik,
więc podwójnie związany lista ma tylko sposób, aby przejść do tyłu, jak również.
>> Teraz w pojedynczo-linked Lista video, rozmawialiśmy
o to pięć z Najważniejsze rzeczy, które musisz mieć
w stanie zrobić, aby pracować z połączonych listach.
A dla większości z nich, fakt, że jest to podwójnie połączonej listy
Nie jest to duży skok.
Nadal możemy przeszukiwać tylko przez do przodu od początku do końca.
Nadal możemy stworzyć węzeł z rozrzedzone powietrze, prawie w ten sam sposób.
Możemy usuwać list dość podobny sposób też.
Jedyne rzeczy, które są nieco inne,
Naprawdę, wstawiasz nowe węzły na listę,
a my w końcu mówić o usunięcie pojedynczy element z listy, jak również.
Ponownie, bardzo dużo pozostałe trzy, jesteśmy
Nie będziemy mówić o nich właśnie teraz, bo są po prostu
bardzo drobnych poprawek na pomysły dyskutowane w pojedynczo-połączonej listy wideo.
>> Warto więc wprowadzić nowy węzeł w podwójnie połączonej listy.
Rozmawialiśmy o tym od pojedynczo-linked list, jak również,
ale jest kilka dodatkowych łapie się podwójnie połączonych listach.
Jesteśmy [? przechodzi?] na czele tu wymieniać, a niektóre dowolna wartość,
i chcemy, aby dostać nową głowę listy zewnątrz tej funkcji.
Dlatego zwraca gwiazdę dllnode.
Więc jakie są kroki?
Są znowu bardzo podobny do pojedynczo-linked list
z dodatkowym dodatkiem.
Chcemy przydziela miejsce na nowy węzeł i sprawdzić, aby upewnić się, że to ważne.
Chcemy, aby wypełnić ten węzeł się wszelkich informacji, że
chcesz umieścić w nim.
Ostatnią rzeczą, jaką musimy do-- dodatkową rzeczą, jaką musimy zrobić, rather--
to naprawić Poprzedni wskaźnik starego czele listy.
Pamiętaj, że z powodu podwójnie związane z listy,
możemy iść do przodu i backwards-- które
Oznacza to, że każdy węzeł rzeczywiście wskazuje dwa inne węzły, zamiast tylko jednej.
I tak musimy to naprawić stary szef listy
do punktu wstecz do nowego szefa połączona lista, która była czymś
nie mieliśmy do zrobienia przed.
I jak poprzednio, po prostu zwróci wskaźnik do nowego szefa listy.
>> Więc oto lista.
Chcemy, aby wstawić 12 na tej liście.
Zauważ, że diagram jest nieco inny.
Każdy węzeł zawiera trzy fields-- danych, a następny wskaźnik w kolorze czerwonym,
a Poprzedni wskaźnik w kolorze niebieskim.
Nic nie przychodzi do węzła 15, więc jego Poprzedni wskaźnik ma wartość null.
Jest to początek listy.
Nie ma nic przed nim.
I nic nie przychodzi po węźle 10, a więc Następny wskaźnik jest null, jak również.
>> Warto więc dodać 12 do tej listy.
Musimy [niesłyszalne] przestrzeń dla węzła.
Kładziemy 12 w jej wnętrzu.
I znów, musimy być bardzo Uważaj, aby nie przerwać łańcuch.
Chcemy przegrupowania wskaźniki w odpowiedniej kolejności.
I czasem, że może mean-- jak zobaczymy szczególnie
z delete--, że mamy pewne zbędnych wskazówek, ale to jest OK.
>> Więc to, co chcemy zrobić w pierwszej kolejności?
Polecam rzeczy powinieneś prawdopodobnie
nie są do wypełnienia wskaźników z 12 węzeł zanim dotkniesz ktokolwiek inny.
Więc co jest 12 będzie wskazywać na następny?
15.
Co jest przed 12?
Nic.
Teraz mamy wypełnił dodatkowe informacje w 12
więc ma poprzedniej, następnej, i wartość.
>> Teraz możemy mieć 15-- ta dodatkowa krok rozmawialiśmy about-- my
może mieć 15 punkt z powrotem do 12.
A teraz możemy przejść głowę połączony lista będzie również 12.
Więc to jest bardzo podobne do tego, co robią z listy połączonych pojedynczo,
z wyjątkiem dodatkowego kroku podłączania starego początku listy
Powrót do nowego szefa listy.
>> Teraz wreszcie usuwać węzeł z innej listy.
Więc powiedzmy, że mamy inna funkcja
jest znalezienie węzła chcemy usunąć i dał nam wskaźnik do dokładnie
węzeł, który chcemy usunąć.
My nawet nie need-- powiedzieć głowa jest wciąż globalnie oświadczył.
Nie potrzebujemy tutaj głową.
Wszystko to funkcja robi to mamy znaleźć wskaźnik do węzła dokładnie tak my
chcą się pozbyć.
Miejmy się go pozbyć.
To dużo łatwiejsze podwójnie związany list.
First-- to faktycznie tylko kilka rzeczy.
Musimy tylko ustalić otoczenie wskaźniki węzłów ", tak aby przeskoczyć
węzeł chcemy usunąć.
A potem możemy usunąć ten węzeł.
Więc jeszcze raz, po prostu przechodzi tutaj.
Mamy najwyraźniej uznał, że chcemy usunąć X. węzła
I znowu, co mnie robi here-- przez way--
jest ogólnym przypadku dla węzeł, który jest w środku.
Istnieje kilka dodatkowe zastrzeżenia, że
należy wziąć pod uwagę, gdy usuwasz samego początku listy
lub bardzo koniec listy.
Istnieje kilka specjalnych Szafy narożne do czynienia z nie.
>> Tak to działa na usunięcie dowolnego węzła W środku list-- taki, który
ma uzasadniony wskaźnik do przodu i uzasadniony wskaźnik do tyłu,
Poprzedni i Następny uzasadnione wskaźnik.
Ponownie, jeśli pracujesz z końcami, ty
potrzebne do obsługi tych nieco inaczej,
a my nie będziemy teraz o tym rozmawiać.
Ale można chyba dowiedzieć się, co trzeba
do zrobienia, po prostu oglądając ten film.
>> Więc mamy pojedyncze X. X jest węzeł chcemy usunąć z listy.
Co robimy?
Po pierwsze, musimy zmienić zewnętrzne wskaźniki.
Musimy zmienić 9 dalej przeskoczyć 13
i wskaż 10-- które jest to, co właśnie zrobił.
A trzeba też przestawiać 10 poprzednią
zwrócić do 9 zamiast wskazywać do 13.
>> Więc jeszcze raz, to był Schemat na początek.
To był nasz łańcuch.
Musimy przeskoczyć 13, ale musimy również zachowanie
integralność listy.
Nie chcemy stracić żadnej Informacje zawarte w obu kierunkach.
Musimy więc zmienić kursory ostrożnie
więc nie przerwać łańcuch w ogóle.
>> Można więc powiedzieć, 9 dalej wskaźnik Wskazuje to na to samo miejsce
że trzynaście Next Wskaźnik wskazuje teraz.
Ponieważ jesteśmy w końcu będzie chciał przeskoczyć 13.
Gdziekolwiek więc 13 punktów Następnie, chcą dziewięć tam wskazać zamiast.
Więc to jest to.
I wtedy tam, gdzie 13 punktów powrotem się, co jest przed 13,
chcemy 10 punkt na tym, że zamiast 13.
Teraz zauważyć, jeśli się strzałki, możemy upuścić 13
bez faktycznie utraty informacji.
Mamy przechowywane integralności listy, ruchu do przodu i do tyłu.
A potem możemy właśnie rodzaj z posprzątać trochę
pociągając za sobą listy.
Więc przekształciła wskaźniki z każdej strony.
A potem uwolnił X Węzeł, który zawierał 13,
i nie przerwać łańcuch.
Więc zrobiliśmy dobrze.
>> Ostatnia uwaga tu na połączonych listach.
Tak więc zarówno singly- i podwójnie związane Listy, jak widzieliśmy,
bardzo efektywne wsparcie wstawiania i usuwanie elementów.
Bardzo wiele można zrobić jest w stałym czasie.
Co musimy zrobić, aby usunąć element po prostu drugi temu?
Przenieśliśmy jeden wskaźnik.
Przenieśliśmy inny wskaźnik.
Mamy uwolnił X-- wziął trzy operacje.
To zawsze trwa trzy operacje na usunąć ten node-- uwolnić węzeł.
>> Jak możemy włożyć?
Cóż, jesteśmy po prostu zawsze sklejaniu na początku
jeśli mamy skutecznie włożeniem.
Więc musimy rearrange-- w zależności czy jest to
singly- lub podwójnie związane Lista może musimy zrobić trzy
lub cztery operacje max.
Ale znowu, to zawsze trzy lub cztery.
Nie ma znaczenia, ile elementy są w naszej liście,
to zawsze trzy lub cztery operations-- jak usuwanie jest zawsze
trzy lub cztery operacje.
Jest to stała czasowa.
Więc to jest naprawdę wielki.
>> Z tablicami, robimy coś Sortowanie przez wstawianie.
Prawdopodobnie przypomnieć, że wprowadzenie sortowania nie jest algorytmem czas stała.
To rzeczywiście dość drogie.
Więc to jest o wiele lepiej do wkładania.
Ale jak już wspomniałem w pojedynczo-linked listy wideo
mamy wadę tutaj, prawda?
Straciliśmy zdolność do losowo dostęp elementy.
Nie możemy powiedzieć, chcę elementu numer cztery lub element numer 10 z połączonej listy
w ten sam sposób, że możemy zrobić z tablicą
lub możemy po prostu bezpośrednio indeksu w elemencie naszej tablicy jest.
>> A więc próbuje znaleźć elementem połączonej list--
jeśli przeszukiwanie jest important-- Może teraz trochę czasu liniowego.
Ponieważ lista wydłuża się, że może zająć jeden dodatkowy krok
dla każdego elementu na liście w aby znaleźć to, czego szukamy.
Więc nie ma kompromisów.
Jest trochę pro i con elementem tutaj.
>> I podwójnie związane listy nie są ostatnia rodzaju kombinacji struktury danych
że będziemy rozmawiać o, biorąc wszystkie podstawowe budynku
bloki C układania.
Ponieważ w rzeczywistości, możemy nawet lepiej niż to
tworzyć strukturę danych, która może być w stanie przeszukiwać
w stałym czasie zbyt.
Ale o tym w innym filmie.
>> Jestem Doug Lloyd.
To CS50.