[Мусиц плаиинг] Давид Ј. Малан: У реду. Ово је ЦС50. То је пет недеље наставили, а ми имају неке добре вести и лоше вести. Тако добра вест је да је ЦС50 покреће овај петак. Уколико желите да нам се придружите, главе до уобичајеног УРЛ овде. Чак и боље вести, нема предавање То долази у понедељак 13.. Нешто мање боље вести, Куиз нула је следеће среде. Више детаља може бити наћи на овом УРЛ овде. И у наредних неколико дана ћемо попуњавања празнине у вези са собама да смо задржана. Боље вест је да тамо неће бити курс-широк преглед сессион то долази Понедељак увече. Пратите курс је Сајт за локацију и детаље. Секције, иако је Холидаи, такође ће се састати као добро. Најбоља вест, предавање следећег петка. Дакле, ово је традиција да имају, по градиву. Само-- да ће бити невероватно. Видећете ствари као што су структуре података Цонстант време и хасх табеле и дрвеће и покушава. Па ћемо разговарати о проблемима рођендан. Цела гомила ствари чека следећег петка. У реду. У сваком случају. Тако подсетити да смо били фокусирајући се на овој слици онога што је унутар меморије нашег рачунара. Па меморија или РАМ-а је где програми постоје док сте их користите. Ако двапут кликнете икона за покретање неки програм или двапут кликните икону да бисте отворили неку датотеку, то је напуњен са вашег хард диска или ССД диск у РАМ, Рандом Аццесс Мемори, где је она живи све док нестане струја, лаптоп поклопац затвара, или сте прекинули програм. 

Сада када сећање, од које вероватно имате 1 ГИГАБИТЕ ових дана, 2 гигабајта, или чак много више, се генерално постављен за датом програму у овој врсти правоугаоника Концептуални модел чиме имамо стек на дну и гомила других ствари на врху. Ствар у самом врху Видели смо на овој слици и раније, али никада није причао о је тзв сегмент текста. Сегмент текст је само фенси начин да се каже нула и јединица које саставити своју стварну саставио програм. 

Дакле, када двапут кликнете Мицрософт Ворд на вашем Мац или ПЦ, или када покренете тачка сласх Марио на Линук компјутер на вашем прозору терминала, нуле и они који сачињавају Реч или Марио се привремено чувају у РАМ рачунара у тзв сегмент текст за одређени програм. Испод тога иде инитиализед и неиницијализованој података. То је слично глобалних променљивих, да ми нисмо користили многе, али понекад имамо Имао глобалних променљивих или статички дефинисано жице које је фиксирана речи као што су "здраво" који нису узети у од корисника да се тешко кодирани у свој програм. 

Сада, на дну смо имају тзв стек. И стек, до сада, били смо користи за Какве сврхе? Шта је стек се користи за? Да? 

Публика: Функције. 

Давид Ј. Малан: За функције? У ком смислу за функције? 

Публика: Када позовете функцију, аргументи се копирају на стек. 

Давид Ј. Малан: Тачно. Када позовете функцију, његов аргументи се копирају на стек. Тако да било који Кс је или И-а или је или Б је да сте пролази у функцију се привремено ставити на тзв стацк, као један од Анненберг трпезарија тацне, али и ствари попут локалних променљивих. Ако је ваш Фоо функција или ваш Свап Функција имају локалне променљиве, попут Темп, она двојица завршити на стек. Сада нећемо говорити превише о их, али ови променљиве окружења на дну смо видели малопре, када Ја сам стално притискате на тастатури једног дана и почео сам да приступ ствари као аргв 100 или аргв 1000, Управо елементс-- сам заборавио нумберс-- али да Није требало да се приступи од мене. Почели смо видели неке функи симболи на екрану. То су били такозвани променљиве окружења као глобалним поставкама Фор Ми програма или за мој рачунару, а не нема везе са недавном Буг да смо разговарали, Схеллсхоцк, која је била отежава доста компјутера. 

Сада на крају, у данашњем фокусу ћемо на крају ћемо бити на гомили. Ово је још један комад меморије. И све то у основи меморија је иста ствар. То је исти хардвер. Ми смо само врста лечење различитих кластера бајтова за различите намене. Куча такође ће бити тамо где променљиве и меморије које сте тражили од оперативног система се привремено складишти. 

Али постоји нека врста проблема овде, као слика подразумева. Ми имамо два врста бродови око да се сударају. Јер, као што користе све више и више стека, а као што видимо данас па надаље, док користите више и више хеап, сигурно лоше ствари може да се деси. И заиста, можемо изазвати да намерно или ненамерно. Тако да на последњем Цлиффхангер време је овај програм, који нису служили било функционална другу сврху него да покаже Како ви као лош момак може заправо да Предност буг у нечијем програму и да преко програма или чак цео рачунарски систем или сервер. Па само да поглед укратко, хвала приметити да је главни на дну узима у командној линији аргументи, као по аргв. И има позив на функцију ф, суштини безимени функцију која се зове Ф, а то је доношење у аргв [1]. 

Дакле, шта год речју корисник укуцава у линији после назива овог програма, а онда произвољна функција горе топ, Ф, узима у низу, звани цхар *, као што смо почели да разговарају, и то само назива "Бар". Али смо могли назвати нешто. И онда се прогласи, изнутра ф, низ знакова позвао ц-- 12 таквих знакова. 

Сада, по причи сам говорио малопре, где у меморији је Ц, или су они 12 Цхарс ће се завршити? Само да буде јасно. Да? 

ПУБЛИКА: на стек. 

Давид Ј. Малан: на стек. Дакле, ц је локална променљива. Ми тражимо 12 карактера или 12 бајтова. Они ће завршити на тзв стек. Коначно је ово друга функција То је заправо прилично корисна, али ми не смо заиста користи то сами, стрнцопи. То значи стринг копију, али Само н слова, н знакова. Тако да је н знакова ће бити копиран из Бара у ц. И колико? Дужина бара. Дакле, другим речима, да је једна линија, стрнцопи, ће за копирање ефективно бар у до ц. 

Сада, само да некако предвиди Поука ове приче, оно што је потенцијално проблематичан овде? Иако смо проверу дужину Бар и то пролази у стрнцопи, шта је ваш стомак вам говорим још брокен о овом програму? Да? 

ПУБЛИКА: Не обухвата Соба за нулл карактер. Давид Ј. Малан: Не укључује Соба за нулл карактер. Потенцијално, за разлику од ранија пракса ми чак и не има толико као плус 1 до прими ту нулл карактер. Али је још горе од тога. Шта друго ми не успева да урадимо? Да? 

ПУБЛИКА: [неразумљиво] Давид Ј. Малан: Савршено. Тешко смо кодирана 12 прилично произвољно. То није толико проблем, али чињеница да нисмо ни проверу када Дужина бар мањи од 12, у ком случају ће то бити безбедно да се стави у меморију звали Ц које смо додељена. Заиста, ако је бар је као 20 знакова, изгледа ова функција буде копирање 20 карактера из Бара у Ц, тиме узимање најмање 8 бајтова да не би требало да буде. То је импликација овде. 

Дакле, у кратком, сломљеном програм. Није тако велика ствар. Можда сте добили сегментационе грешке. Ми смо сви имали грешке у програмима. Ми сви можда има бубе у програмима сада. Али, шта је импликација? Па, ево зумира-у верзија та слика меморије мог рачунара. То је дно мог стека. И заиста, на самом дну је оно што је зове родитељ рутина стек, фенси начин каже да је главни. Тако да ко год се зове функција Ф да говоримо о томе. Дакле, ово је дно стека. Повратна адреса је нешто ново. То је увек био ту, увек била у тој слици. Само смо никада није позвао пажњу на то. Јер испада пут Ц радова је да када једна функција зове другог, не само да аргументе за то Функција се гурнуо на стек, не само да локална функција је варијабле се гурнуо на стек, нешто што се зове повратна адреса такође добија ставити на стек. Посебно, уколико главни позиви Фоо, главни је своју адресу у меморији, вола нешто, ефективно добија стави на стек тако да када ф врши га извршава зна где да се вратите у тексту сегмент у циљу наставка извршења. 

Дакле, ако смо овде концептуално, у главни, а затим Ф добија се зове. Како Ф зна ко контроли предају? Па, ово мало бреадцрумб у црвено овде, зове повратна адреса, то је само чекови, шта је то повратак адреса? Ох, да вратите на главни овде. И то је мало једног поједностављења, јер су нула и јединица за магистралне су технички овде у техничком сегменту. Али то је идеја. Ф само мора да зна шта где контрола на крају се враћа. 

Али начин на који рачунари одавно изнео ствари попут локалних променљивих и аргумената је овако. Дакле, у врху ове слике у Плава је стек оквир за Ф, тако да су сви меморије ф посебно користи. Дакле сходно томе, приметићете да бар на овој слици. Бар је његов аргумент. И тврдили смо да аргументи за Функције се гурнула на стек. И Ц, наравно, такође у овој слици. 

И само за нотног сврхе, приметити у горњем левом углу је шта би било Ц носач 0 и онда мало доле на десно је Ц Брацкет 11. Другим речима, можете да замислите да постоји решетка бајтова Ето, од којих први је горе лево, дно од којих је последњи од тих 12 бајтова. 

Али сада покушавају да брзо напред. Шта ће се десити ако се прође у бару стринг који је дуже од ц? А ми не проверавамо да ли то је заиста више од 12 је. Који део ове слике ће се се преписани од бајта 0, 1, 2, 3, дот дот дот, 11, а затим лоше, 12, 13 до 19? Оно што се дешава да се деси овде, ако закључи са наручивање да је ц 0 носач је на врху ц носач 11 је некако доле у праву? Да? 

Публика: Па, то ће да замени знак * Бар. 

Давид Ј. Малан: Да, изгледа идете да препишете цхар * бар. И још горе, ако сте послати заиста дуг стринг, можда чак препишете шта? Повратна адреса. Што опет, баш као бреадцрумб да кажем програм у коме да се вратим када Ф врши се зове. 

Дакле, шта лоши момци обично радим је ако дођу преко програма да су они радознали да ли је експлоатиłу бугги на такав начин да он или она може да Предност тог буг, углавном не добију ово право први пут. Они само започели слање, на пример, Рандом Стрингс у програм, било на тастатури, или искрено вероватно напише мали програм само аутоматски генерише Стрингс, и почети лупање на програму од слање у много различитих инпута на различитим дужинама. 

Чим свој програм судара, То је невероватна ствар. Јер то значи да он или она је открила оно што је вероватно заиста Буг. И онда они могу добити више паметнији и почети фокусирајући се више уско како да искористи ту грешку. Конкретно, оно што он или она можда урадите је да пошаљете, у најбољем случају, здраво. Ништа страшно. То је стринг који је довољно кратак. Али шта ако он или она шаље, и ми ћемо га генерализовати као, Аттацк бројеве-- тако нула и оне који раде ствари као РМ-РФ, то ремове све са хард диска или послати спам или некако нападну машину? 

Дакле, ако сваки од њих слова само представља, концептуално, напад, напад, напад, напад, неке лоше код да је неко други написао, али је ако је то лице довољно паметан не само да садржи све од оних РМ-РФС, али и имају своје последње неколико бајтова бити број који одговара на адресу његовог или њена напад код да он или она прошао у само обезбеђујући га на линији, можете ефикасно да преварите рачунар у приметивши кад Ф врши извршавање, Ох, то је време за мене да скочи Назад на црвеном повратка адресу. Већ зато што он или она некако има преклапају ту повратну адресу са својим бројем, и они су довољно паметни да је конфигурисан да број се односи, као и ти види у Супер Топ леви угао тамо, Стварна адреса у рачунара сећање на неке од својих напада кода, лош момак може преварити рачунар у вршењу своје сопствено код. 

И да је код, опет, може бити било шта. То се обично назива схелл код, што је само начин да се каже да то није генерално нешто тако једноставно као РМ-РФ. То је заправо нешто као Басх, или стварни програм који му даје или њен програмско контроле да изврши још нешто да они желе да. Дакле, у Укратко, све ово проистиче из просте чињенице да ово није грешка укључени проверу границе вашег низа. И због начина Компјутери рад је да они користе штос из ефикасно, концептуално, дно на горе, али онда су елементи притиснете на стек расте одозго, ово је невероватно проблематично. Сада, постоје начини да се ради око овога. И искрено, постоје језици са којима се ради око овога. Јава није имуна, на пример, на овом питању. Јер они не дају савете. Они те не дам директни меморијске адресе. Дакле, са овим моћи да имамо да ништа дирати у меморији Желимо долази, додуше, велики ризик. 

Тако да би на оку. Ако је, искрено, у наредним месецима или година да дођу, било када читате о неком експлоатацији програма или сервера, Ако сте икада видели наговештај нечега као буффер оверфлов напад, или стек прекорачење један тип напада, слични по духу, колико инспирише Сајт је име, ако га знате, то је све само говори о преливање величину неког карактера низ или неки низ уопште. Сва питања, дакле, на ово? Не покушавајте ово код куће. 

У реду. Па маллоц до сада је наша нова пријатељ у да можемо доделити меморију да не нужно знати унапред да желимо да немамо на хард коду у нашу програм бројеви као 12. Када корисник нам говори колико Подаци он или она жели да улаз, можемо маллоц толико меморије. 

Па маллоц се испоставило, да мери смо да га користите, експлицитно последњи пут, а потом сте се да га користите за гетстринг несвесно за неколико недеља, сви меморије маллоц а долази из тзв гомили. И то је зато гетстринг, на пример, може доделити меморију динамички не знајући шта си ће да куцате унапред, предајте вас назад показивач на ту меморију, и да је меморија је још увек твој да, чак и након гетстринг повратак. Јер Подсетимо, након свега тога стек се стално иде горе и доле, горе и доле. И чим иде доле, то значи све меморије Ова функција се користи треба да се не користи било кога другог. То је вредност за смеће сада. 

Али гомила се овде. И шта је лепо у вези маллоц је то када маллоц алоцира меморију овде, то није утицао, јер Највећи дио, од стека. И тако Свака функција може приступити Меморија која је маллоц'д, чак функцију као гетстринг, чак и након што је враћен. 

Сада, обрнуто од маллоц је слободан. И заиста, вам правило треба да почну доношење је било, било, сваки пут када користите маллоц Морате се користити бесплатно, на крају, на истом показивачу. Све ово време смо писали Бугги, Бугги код, из много разлога. Али један од којих је користећи ЦС50 библиотеку, која Сама је намерно Бугги, цури меморију. Сваки пут када сте звали гетстринг током протеклих неколико недеља ми пита радом систем, Линук, за меморију. А ви сте га ни једном враћен. И то није у пракси, добра ствар. 

И Валгринд, један од Алати уведени у Псет 4, је све о да вам помогнемо сада наћи такве грешке. Али на срећу екипе Псет 4 не морате да користи ЦС50 библиотеку или гетстринг. Тако да било који бугова везаних за меморије на крају ће бити свој. 

Па маллоц је више него само погодан за ову сврху. Ми смо заправо сада реши фундаментално различите проблеме, и фундаментално решавају проблеме више ефикасно као недељно ЗЕРО обећања. До сада је ово најсекси структура података смо имали. И структуре података само мислим начин размишљања меморије на начин који превазилази само кажем, Ово је инт, ово је знак. Можемо почети да кластера ствари заједно. 

Па низ изгледао овако. А каква је била кључна у око Низ је да вам даје бацк-то-бацк ​​комади меморије, од којих свака ће бити истог типа, инт, инт, инт, инт или цхар, цхар, знак, знак. Али постоји неколико недостатака. Ово је за пример, низ величине шест. Претпоставимо да попуните овај низ са шест бројеви и онда, из било ког разлога, ваш корисник жели да пружи ви седми број. Где си га ставио? 

Шта је решење ако имате створио низ на стеку, на пример, само са недељи Две нотација које смо увели, квадратних заграда са бројем унутра? Па, имаш шест Бројеви у овим кутијама. Шта би твој инстикт бити? Где би желео да га ставите? 

ПУБЛИКА: [неразумљиво] 

Давид Ј. Малан: Жао ми је? 

Публика: Ставите га на крају. 

Давид Ј. Малан: Ставите то на крају. Па само у десно, изван ове кутије. Што би било лепо, али је Испада да не могу то да урадим. Јер ако не сте питао за комад меморије, то може бити случајно да ово се користе неку другу променљиву укупно. Размислите уназад недељу дана или тако, када смо положили оут анд Замила Давин и Габе именима у меморији. Они су буквално били Назад на бацк то бацк. Тако да не можемо увек Поверење које Шта год да је овде је на располагању за мене да користе. 

Па шта би још могао да радиш? Па, када сте схватајући потребан низ величине седам, можете само да креирате низ величине седам затим користите за петљу или вхиле петље, копирајте га у нови низ, и онда некако само отарасити Овај низ или само престати да га користите. Али то није нарочито ефикасно. Укратко, низови не дозволите ти динамички величину. 

Дакле, с једне стране добијате Рандом приступа, што је невероватно. Зато што нам омогућава да радимо ствари попут завади па владај, бинарни Сеарцх, од којих сви имамо говорио је о на екрану овде. Али си се сликам у углу. Чим ударио крај вашег низа, морате да урадите веома скупа операција или пишите гомилу кода до сада се баве тим проблемом. 

Па шта ако уместо тога смо имали нешто што се зове листу, или листе повезани посебно? Шта ако уместо правоугаоника бацк то бацк то бацк, имамо правоугаоника мало тога остављају мало виггле просторије између њих? И иако сам извући ово слика или прилагођени ову слику из једног од текстова овде да се врати у бацк то бацк веома уредно, у стварности, један од тих правоугаоника може бити овде у меморији. Један од њих би могао да буде овде. Један од њих би могао да буде овде, овде, и тако даље. 

Али шта ако нацртао, у овом случају, стреле да некако повеже ове Рецтанглес заједно? Заиста, ми смо видели технички инкарнацију стрелом. Шта смо користили у недавном дана да, испод хаубе, је представник стрелом? Поинтер, зар не? 

Па шта ако, уместо само складиштење бројева, као 9, 17, 22, 26, 34, Шта ако се не чувају само број већ показивач сваком таквом број поред? Тако да слично као што би навој Неедле кроз гомилу тканина, некако Тиинг ствари заједно, на сличан начин може ми смо са тројке, као инкарнирана стрелицама овде, врста ткају заједно Ови индивидуални правоугаоника ефективно коришћење показивач сваког броја Следећа да указује на неки следећи број, то указује на, заузврат, неки следећи број? Другим речима, оно што ако смо заиста желели да спроведе нешто овако? Па нажалост, ови правоугаоника, Најмање једно са 9, 17, 22, и тако даље, су не више Нице квадрата са једним бројем. Дно, правоугаоник испод 9, на пример, Шта би требало да представља бити показивач, 32 бита. Сад, нисам још познато било које врсте података у Ц који вам даје не само инт али показивач сасвим. 

Дакле, шта је решење, ако желимо да измисле сопствени одговор на ово? Да? 

ПУБЛИКА: [неразумљиво] 

Давид Ј. Малан: Шта је то? 

Публика: Нова структура. 

Давид Ј. Малан: Да, па зашто не бисмо креирали нову структуру, или Ц, струцт? Видели смо Структуре раније, ако је кратко, где смо се бавили са студентом структуром овако, који је имао име и кућу. У Псет 3 пробој сте користили цео гомила струцтс-- ГРецт и ГОвалс да Станфорд створена да Кластер информације заједно. Па шта ако узмемо ово исто идеју кључне речи "типедеф" и "строги," а онда неки ученик специфичне ствари, и развијају ово у следеће: типедеф струцт ноде-- и чвор је само веома генерички информатике израз за нешто у структури података, контејнер у структури података. Чвор Тврдим ће имати инт н, потпуно јасан, а онда мало више загонетно, Ова друга линија, струцт ноде * следећи. Али, у мање техничком смислу, Шта је то друга линија кода унутар заграда? Да? 

ПУБЛИКА: [неразумљиво] Давид Ј. Малан: показивач на други чвор. Дакле признајем, синтакса мало загонетан. Али ако сте то прочитали дословно, Следеће је име променљиве. Шта је њен тип података? То је мало опсирније овај пут, али је типа струцт чвора *. Сваки пут када смо видели нешто звезда, то значи да је показивач на тај тип података. Дакле, следећи је очигледно показивач на структуру чвор. 

Сада, шта је Структ чвор? Па, приметићете видиш оне исте речи у горњем десном углу. И заиста, ви видети реч "Чвор" овде у доњем левом. И ово је у ствари само погодност. Обратите пажњу да у нашој дефиницији студентском ту је реч "студент" само једном. А то је зато што студент Циљ није био самореферентне. Нема ништа унутар студента који треба да укаже на другом студенту, персаи. То би било врста чудно у стварном свету. 

Али са чвор у повезана Листа, радимо желимо чвор да буде референтна на сличан објекат. Па приметити промена овде није Управо оно што је унутар заграда. Али смо додали реч "чвор" на врху, као и додавања до дна уместо "Студент". И ово је само техничка детаљ тако да је, опет, ваша структура података могу бити самореферентна, тако да чвор може да укаже на другом таквом чвору. 

Дакле, шта је то на крају ће да значи за нас? Па, један, ове ствари унутра је садржина наше чвора. Ова ствар овде, горњем десном углу, је тако то, опет, можемо да се односи на себе. А онда спољни ствари, иако чвор је нови термин, можда, још увек је исто као студент и шта била испод хаубе у СПЛ. 

Дакле, ако ми сада желели да почне спровођења овог повезане листе, како бисмо могли превести нешто овако да се код? Па, хајде да видимо Пример програма који заправо користи повезане листе. Међу данашњим дистрибуције кода је програм под називом Листа Нула. И ако сам покренути ово сам створио супер Симпле ГУИ, графички кориснички интерфејс, али то је заиста само принтф. И сад сам се дао неколико мени опције-- Делете, Инсерт, Сеарцх, и Траверсе. И отказ. Ово су само уобичајене операције на Структура података познат као списак линк. 

Сада, Делете ће обрисати број из листе. Инсерт ће додати број на листу. Тражи ће да изгледа за број на листи. И померајте је само фенси начин каже, хода кроз листу, одштампате га, али то је то. Немојте га променити у било који начин. 

Па хајде да пробамо ово. Идемо напред и типа 2. А онда ћу да убаците број, кажу 9. Ентер. И сада мој програм је само програмирани да кажем, листа је сада 9. Сада, ако само напред и Не опет Инсерт, нека ја само напред и умањили и унесите у 17. Сада је мој списак је 9, а затим 17. Ако ја убаци опет, хајде да прескочимо једну. Уместо 22, по слици ми смо гледали овде, пусти ме да скочи напред и убаците 26 Следећа. Па ћу да куцате 26. Листа је, као што сам очекивао. Али сада, само да видим да ли овом коду ће бити флексибилан, нека ме одмах типа 22, који најмање концептуално, ако смо Имајући ово поредани, што је заиста ће бити још један циљ сада, треба да иду између 17. и 26.. Па сам ударио Ентер. Заиста, то ради. Па сад дај да убаците Ласт, по слици, 34. 

У реду. Дакле, за сада дозволите ми да је предвиђено да Брисање и Траверсе и Сеарцх уради, у ствари, ради. У ствари, ако ја покренути Сеарцх, хајдемо потражите број 22, Ентер. Је нашао 22. Дакле, то је оно што ова Програм Листа Зеро ради. 

Али шта се заправо дешава на то имплементира ово? Па, прво сам можда има, и заиста Ја немам, датотека се зове лист0.х. И негде тамо је ово линије, типедеф, струцт чвор, онда имам витичасте заграде, инт н, и тада струцт-- шта је дефиниција? Струцт чвор следећи. Тако да морамо звезду. Сада технички добијамо у навика је цртање овде. Можда ћете видети уџбенике и онлајн референце то раде тамо. То је функционално једнак. У ствари, то је мало више типичан. Али ја ћу бити у складу са оним ми смо прошли пут и уради то. И онда на крају, ја ћу да урадим ово. 

Дакле, у заглављу датотеци негде у лист0.х Данас је то дефиниција строги, и можда неке друге ствари. У међувремену, у лист0ц има ће бити неколико ствари. Али ћемо само почети и не заврши ово. Лист0.х је датотека желим да се у мојој Ц фајлу. А онда у неком тренутку сам ће имати ИНТ, главни, поништити. А онда ћу да имају неке Обавеза је овде. Такође ћу имати прототип, као празнина, претрага, инт, н, чији је циљ у животу је да тражи за елемент. А онда овде тврдим у данашња код, празнина, Сеарцх, инт, н, Но зарез али отворене цурли протезе. А сада желим да некако претрагу за елемент у овој листи. Али немамо довољно информације на екрану још. Нисам стварно представљао саму листу. Дакле, један начин бисмо могли имплементирати повезане листе у програму је да сам некако желим да радим нешто Као изјављујем листу повезано овде. Ради једноставности, ја ћу направити ова глобална, иако у општем и ми Не би требало да то превише. Али, то ће поједноставити овај пример. Зато желим да се изјасни повезан списак овде. Сада, како да урадим то? 

Ево слика повезане листе. И ја стварно не познато у овом тренутку како Идем да иду о заступање толико много ствари са само једном променљиве у меморији. Али мислим назад тренутак. Све ово време смо имали Стрингс, што смо тада открила да су низови карактера, које смо тада открила да само буде показивач првом карактеру у низ знакова то је нулл раскинут. Тако се тој логици, и са овим слика врста сетве своје мисли, Шта треба нам заправо пише у нашем код да представља повезану листу? Колико ове информације су нам потребни за снимање у Ц коду, би ти рекао? Да? 

ПУБЛИКА: Треба нам показивач на чвор. Давид Ј. Малан: показивач на чвор. Конкретно, што чвор би ваши инстинкти бити да задржи показивач на? 

ПУБЛИКА: Први чвор. 

Давид Ј. Малан: Да, Вероватно је само први. И приметите, први чвор је другачији облик. То је само половина величина строги, јер је заиста само показивач. Дакле, оно што заиста можете да урадите је прогласити повезан списак бити типа чвора *. И хајде да прво зову и иницијализовати га нулл. Дакле нулл, опет, долази у слику овде. Не само да се користи као нула као посебан Повратна вредност за ствари као што гетстринг и маллоц, нулл је нула Поинтер, недостатак показивача, ако хоћете. То само значи да ништа није још увек овде. Сада прво, могао сам звали ништа. Могао сам га назвао "листа" или било који број других ствари. Али ја то зовем "први", тако да ИТ линије са овом сликом. Па као низа могу бити представљени са адресом свог првог бајта, тако да може повезана листа. Па ћемо видети друге податке структуре бити заступљене са само једним показивачем, 32-битни стрелица, показујући на први чвор у структури. 

Али сада хајде да предвиди проблем. Да сам само ја сећајући у мом програму адресе првог чвора, први правоугаоник у овој структури података, оно што је боље да буде случај у вези имплементација остатак мог списка? Шта је кључ детаљ који иде да се обезбеди ово стварно ради? И "заправо ради" Ја Мислим, слично као низа, нам омогућава да идемо од првог карактера у Давин име према другом, до треће, да Четврто, до самог краја, како да знамо када смо на крају повезаног листе која изгледа овако? Када је нулл. И ја сам представља ову врсту као као електроинжењер снагом, са мало уземљење симбол, неке врсте. Али то само значи нулл у овом случају. Можете да га извући било који број начине, али овај аутор десило да користите овај симбол овде. 

Докле год смо низање све ове чворова заједно, само памћење где Прво је, тако дуго као што смо ставили посебан симбол на последња чвор у листи, а ми ћемо користити нулл, јер је то оно што имамо на располагању за нас, Ова листа је завршена. А чак и ако само да ти дам показивач на први елемент, ви, програмер, свакако могу да приступе остало. Али хајде да дозволите да ваш ум лутају мало, ако нису већ сасвим вандеред-- шта је ће бити покренут време проналажење ништа на овој листи? Проклетство, то је Биг О Н, што није лоше, у правичност. Али је линеарна. Ми смо дали оно што функција низова померањем више према овој слици динамички ткани заједно или повезани чворова? Ми смо одустали случајан приступ. Низ је лепо, јер математички све се враћа у леђа уз леђа у леђа. Иако овој слици изгледа прилично, па чак и мада изгледа ових чворова су лепо распоређени поред, у стварности они могу бити било где. ОКС1, Ок50, Ок123, Ок99, ови чворова може бити било где. Јер маллоц не издвоји меморију из гомиле, али је било где у гомили. Не нужно знају да је то ће се вратити у леђа уз леђа. Па ова слика у стварност је неће бити прилично ова лепа. 

Тако да ће се мало раде на имплементацији ову функцију. Па хајде да спроведе претрагу сада. Па ћемо видети какав паметан начин да то урадите. Дакле, ако сам функција претраживања и Ја сам дао променљива, број н да траже, морам да знам Нови Синтакса за гледа унутра структуре која'С указао на, да пронађу н. Па хајде да урадимо ово. 

Дакле, прво ћу да одем напред и прогласи чвор *. И ја ћу да га зову Поинтер, само конвенцијом. И ја ћу да га иницијализује прво. И сад ја могу да урадим ово на више начина. Али ја ћу да се заједнички приступ. Док је показивач није једнак нулл, а то је важећа синтаксе. И то само значи урадите следеће, па док ти не показујући на ништа. Оно што желим да урадим? 

Ако Поинтер дот н, пусти ме да се вратим томе, екуалс-- једнако шта? Коју вредност тражим? Стварни н који је усвојен у. Дакле, овде је још једна од карактеристика за Ц и многим језицима. Иако се структура зове чвора има вредност Н, потпуно легитимни да имају локалну аргумент или променљива зове н. Јер чак и ми, са људске очи, може да разликује да је ово н је вероватно разликује од ове н. Јер синтакса је другачија. Имаш тачку и показивач, а овај нема такве ствари. Дакле, то је у реду. То је у реду да их позовем исте ствари. 

Ако ја пронађете ово, ја сам хтети да уради нешто као најавити да смо нашли Н. А ми ћемо оставити да као коментар или Псеудокод код. Друго, и ево интересантан део, што желим да радим ако тренутни чвор Не садржи н да ми је стало? Како да се постигне следеће? Ако мој прст на тренутак је ПТР, и то је показујући на год Први је показујући на, како да померим прст на следећи чвор у шифрама? Па, шта је бреадцрумб смо ће пратити у овом случају? ПУБЛИКА: [неразумљиво]. Давид Ј. Малан: Да, тако следећи. Дакле, ако се вратим на мој код овде, заиста, ја сам ићи напред и рећи показивач, који је само привремени вариабле-- је чудно име, ПТР, али то је исто као темп-- Идем поставити показивач једнако било показивача је-- И опет, то ће бити мало Бугги за тренутак-- тачку следећег. Другим речима, ја ћу узети мој прст која се показује у овом чвору овде и ја ћу да кажем, знаш Шта, погледајте следеће поље и померите прстом шта год да је показујући на. И то ће се Понављам, понављање, поновити. Али када ради мој прст престати да раде ништа уопште? Чим шта линија кода удараца у? ПУБЛИКА: [неразумљиво] Давид Ј. Малан: Ако тачка а показивач није једнак нулл. У неком тренутку Прст ми је ће бити показујући на нулл а ја ћу да схвате то је крај ове листе. Дакле, ово је мало Вхите Лие за једноставност. Испоставило се да, иако смо Управо сам сазнао ову дот нотацију за објекте, показивач није Струцт. ПТР је шта? Само да буде изненадило. То је показивач на чвор. То није сама чвор. Ако сам имао звезда овде, Поинтер апсолутно-- је чвор. То је као Веек Оне Декларација варијабле, иако реч "чвор" је ново. 

Али чим уводимо звезда, сада је показивач на чвор. И нажалост не можете да користите дот нотација за показивач. Морате да користите стрелице нотација, што, упадљиво, је први пут сваки комад синтаксе изгледа интуитивно. То буквално изгледа као стрела. И то је добра ствар. И овде буквално изгледа као стрела. Тако да мислим да је то ла-- ја не Мислим да сам преко-починили овде-- И Мислим да је последњи нови комад синтаксе идемо да видимо. И срећом, то је заиста је мало више интуитивно. 

Сада, за оне од вас који Можда воле стари начин, још увек можете да користите дот нотацију. Али, као по понедељак разговор, прво треба да иде тамо, иди на то адресу, а затим приступите поље. Дакле, ово је такође тачно. И искрено, ово је мало педантан. Ви буквално говорите, дереференце показивач и идите тамо. Затим зграби .Н, поље се зове н. Али искрено, нико не жели да куцате или прочита. Па свет измислио стрелица нотација, која је еквивалентна, идентичан, то је само синтаксичких шећер. Па Фанци начин да се каже ово изгледа боље, или изгледа једноставније. 

Па сад ћу да урадим још једну ствар. Идем да кажем "бреак" Једном сам сам Установљено је тако да се не би у потрази за њега. Али ово је суштина на функцију претраге. Али то је много лакше, у крај, да се не хода кроз кода. То је заиста формална примена претраге у данашњем дистрибуције кода. Усуђујем се да кажем да је уметак није посебно забавно да хода кроз визуелно, нити је обрисати, чак и мада на крају дана они се своде на правично једноставне хеуристике. 

Па хајде да урадимо ово. Ако ћете хумор ме овде, ја сам донети гомилу стреса лопти. Донела сам гомилу бројева. И можемо да добијемо само неколико волонтера да представља 9, 17, 20, 22, 29 и 34? У суштини сви ко је овде данас. То је један, два, три, четири, пет, шест људи. И ја сам био тражио да иде-- видим, нема један у леђа подиже руке. У реду, један, два, три, четири, фиве-- дозволите ми да се учита баланце-- шест. ОК, шест хајде горе. Ми ћемо морати друге људе. Донели смо екстра стрес лоптице. И ако може, само тренутак, линија сами горе само као што је овај слику овде. 

У реду. Да видимо, како се зовеш? 

Публика: Андрев. 

Давид Ј. Малан: Андрев, ти си број 9. Драго ми је да вас упознам. Изволи. Публика: Јен. Давид Ј. Малан: Јен. Дејвид. Број 17. Да? 

ПУБЛИКА: Ја сам Јулиа. 

Давид Ј. Малан: Јулија, Дејвид. Број 20. Публика: Кристијан. Давид Ј. Малан: Кристијан, Дејвид. Број 22. И? 

Публика: ЈП. Давид Ј. Малан: ЈП. Број 29. Зато само напред и да у-- Ух ох. Ух ох. Стандби. 20. Да ли неко има маркер? ПУБЛИКА: Имам Схарпие. Давид Ј. Малан: Имаш Схарпие? У реду. И да ли неко има парче папира? Саве тхе предавање. Хајде. ПУБЛИКА: Имамо га. Давид Ј. Малан: Имамо га? У реду, хвала. Идемо. Да ли је ово од тебе? Управо си спасио дан. Тако 29. У реду. Ја погрешно 29, али је у реду. Само напред. У реду, ја ћу вам дати твоја оловка тренутак. Дакле, имамо ове људе овде. Хајде да се један. Гејб, хоћеш да играте први елемент овде? Ми ћемо вам је потребно да истакнемо на овим финим људима. Дакле 9, 17, 20, 22, сортирање од 29, а затим 34. Да ли смо изгубили некога? Имам 34. Где дид-- ОК, ко жели да буде 34? ОК, хајде горе, 34. У реду, то ће бити добро вреди врхунац. Како се зовеш? 

Публика: Питер. 

Давид Ј. Малан: Питер, хајде горе. У реду, ево Цела гомила чворова. Свака од вас представља једна од ових правоугаоника. И Габе, благо Одд Ман Оут, први представља. Дакле, његов показивач је мало мањи на екрану од свих осталих. И у овом случају, свака од ваше леве стране руке ће или тачку доле, чиме представља нулл, тако да само одсуство показивача, или ће то бити указујући у чвор поред себе. 

Дакле, сада, ако украшавају сами као на слици Овде, само напред и тачка једни на друге, са Габе посебно указујући на број 9 да представља листу. ОК, и број 34, твоја лева рука треба само да се показује у под. 

У реду, тако да је ово повезано листа. Дакле, ово је сценарио у питању. И заиста, ово је представник класе проблема да ћете можда покушати да реши са кодом. Желите да на крају убаците нови елемент у листу. У овом случају, идемо у покушајте да убаците број 55. Али постоји ће бити различити случајеви да се размотри. И заиста, ово ће бити један од Биг-Пицтуре Такеаваис овде, јесте, шта су различити случајеви. Које су различите, ако то услови, или гране које ваш програм може имати? 

Па, број који покушавате да Инсерт, што сада знамо да будемо 55, али ако нисте знали унапред, Усуђујем се да кажем спада у најмање три могуће ситуације. Где би нови елемент бити? ПУБЛИКА: А крај или средњи. Давид Ј. Малан: На ​​крају, у Миддле, или на почетку. Па сам тврдим има најмање три проблема морамо да решимо. Хајде да бирају шта је можда вероватно најједноставнији један, где нови елемент припада на почетку. Па ћу имати шифру сасвим као и претраживање, што сам написао. И ја ћу имати ПТР, која Ја ћу представљати овде са мојим прстом, као и обично. 

И запамтите, коју вредност смо инитиализе ПТР да? Па смо га на почетку иницијализовани нулл. Али онда шта радимо када смо били у нашој функцији за претрагу? Поставили смо да једнако прво, што не значи то уради. Ако ја први сет птр једнак, шта Треба ми рука заиста бити показујући на? Десно. Дакле, ако Гејб и ја идемо да буду равноправни вредности овде, морамо да како тачке на број 9. 

Дакле, то је био почетак наше приче. А сада ово је само једноставан, иако синтакса је нова. Концептуално ово је само линеарна претрагу. Је 55 једнако 9? Или боље речено, рецимо мање од 9. Јер ја покушавам да схватим где да стави 55. Мање од 9, мање од 17, мање од 20, мање од 22, мање од 29, мање од 34, бр. Дакле, сада смо у случају један од најмање три. 

Ако желим да убаците 55 овамо, шта линија кода треба да се изврши? Како ово слику људи треба да се промени? Шта да радим са мојом левом руком? Ово би требало да буде нулл почетку, зато што сам на крају листе. И шта треба да се деси овде са Петром, зар не? Он очигледно ће указати на мени. Па сам тврдим постоје најмање две линије кода у узорку коду од данас која ће за спровођење овог сценарио додавања 55 на репу. И може да имам некога хоп горе и само представљају 55? У реду, ви сте нови 55. 

Па сад шта ако следећа сценарио долази заједно, и желимо да убаците у почетак или руководилац ове листе? А како се ти зовеш, број 55? 

Публика: Џек. 

Давид Ј. Малан: Џек? У реду, драго ми је да смо се упознали. Добродошлицу. Дакле, сада ћемо убаците, рецимо, број 5. Ево други случај три дошли смо са раније. Дакле, ако 5 припада на почетку, хајде да видимо како можемо да сазнам. Ја инитиализе мој птр показивач на број 9 поново. И схватио сам, ох, 5 је мање од 9. Тако поправити ову слику за нас. Чије руке, Гејб је или Дејвид или-- шта је број 9 Име? 

Публика: Јен. 

Давид Ј. Малан: Јен је хандс-- који од наших руку треба да се промени? У реду, тако да Гејб указује на шта сад? На мене. Ја сам нови чвор. Па ћу некако потез овде да видите визуелно. А у међувремену шта ја указују да? Ипак где ти показујем. Дакле, то је то. Тако да стварно једна линија кода исправки ово конкретно питање, рекло би се. У реду, тако да је то добро. И може неко да буде чувар места за 5? Дођи горе. Ми ћемо ти следећи пут. 

У реду, тако и сада-- Као страну, имена Ја не правим изричито помињање права Сада, пред Поинтер, претходник Поинтер и нови показивач, то је само имена дата у узорку код на тројке или моје руке То је мало указују около. Како се зовеш? 

Публика: Цхристине. 

Давид Ј. Малан: Цхристине. Добродошлицу. У реду, хајде да сада размотрити мало нервира сценарио, чиме желим да убаците нешто 26 у ово. 20? Шта? Ови аре-- добру ствар коју имамо ову оловку. У реду, 20. Ако неко могао да добије још једно парче Папир спремни, само у цасе-- реду. Ох, интересантно. Па ово је пример од буба предавања. У реду, тако што је зовеш? Публика: Јулиа. Давид Ј. Малан: Јулија, да ли поп напоље и претварати да никада нису били тамо? ОК, ово се никада није десило. Хвала вам. Ваљда желимо убацити Јулија у овај повезане листе. Она је број 20. И наравно да је ће да припадају у бегин-- не указују на још ништа. Тако да ваша рука може да буде врста доле нулл или неке вредности смеће. Хајде да кажем брзо причу. Ја указујући на броју 5 овај пут. Онда сам проверим 9. Онда сам проверим 17. Онда сам проверим 22. И схватам, Оох, Јулиа мора да иде пред 22. Дакле, шта треба да се догоди? Чије руке треба да промените? Јулиа, Мине, или-- Како се оно зовеш? 

Публика: Кристијан. 

Давид Ј. Малан: Кристијан или? 

Публика: Енди. 

Давид Ј. Малан: Енди. Кристијан или Енди? Анди треба да укаже на? Јулиа. У реду. Дакле Енди, хоћеш да укаже на Јулија? Али чекај мало. У причи до сада, Ја сам врста једног задужен, у смислу да показивач је ствар која је креће кроз листу. Можда имамо име за Анди, али нема променљива зове Енди. Једина друга променљива ми имамо је Прво, ко заступа Габе. 

Дакле, ово је заправо зато тако сада нисмо ми је то требало. Али сада на екрану је спомињи од пред показивачем. Дакле, да будем јаснији. Ако је ово показивач, имао сам боље добити мало интелигентнији о мом итерацији. Ако вам не смета мој иде овуда Опет, показујући ту, указујући овде. Али, дозволите ми да има пред показивач, претходник Поинтер, то је врста показујући на елеменат сам био у. Дакле, када одем одавде, одмах Ми Лефт Ханд исправке. Када сам овде идем левој руци исправке. И сада имам не само показивач на елемент који се после Јулиа, Још увек имам показивач на Анди, елемент раније. Тако да имају приступ, у суштини, презле, ако хоћете, свим потребним показивача. 

Дакле, ако сам показујући на Енди и ја такође указујући на Цхристиан, чији руке Сада треба указати на неком другом месту? Тако да сада могу да указују Анди на Јулиа. Јулиа сада може да укаже на хришћанина. Јер она може да копира мој Поинтер десна рука екипе. Као и да ефикасно вас ставља назад на ово место овде. Дакле укратко, иако је то нас води врста Форевер да се заиста ажурирање листе повезани, схватају да су операције су релативно једноставни. То је један, два, три линија кода крају. Али замотан око оних линија кода претпоставља је мало логике да ефикасно поставља питање, где смо? Да ли смо на почетку, Средњи, или крај? 

Сада, сигурно постоје и неке друге операција можемо имплементирати. А ове слике овде само приказују оно што смо управо урадили са људима. Шта је са уклањањем? Ако желим да, на пример, уклоните број 34 или 55, Ја можда има исту врсту кода, али ја ћу морати један или два корака. Јер оно што је ново? Ако сам некога уклонити на крају, као број 55, а потом 34, ста има да се промени, као што сам то да урадим? Морам да не евицт-- Како се оно зовеш? 

Публика: Џек. 

Давид Ј. Малан: Џек. Морам да не само да евицт-- слободан Џек, па буквално позовите бесплатни Јацк, или барем показивач тамо, али сада шта треба да се мења са Петром? Његова рука је боље почети окренут надоле. Јер чим сам зовем бесплатно на Џек, ако Питер и даље показујући на Јацк и ја стога задржати попречно листе и приступа ово Поинтер, То је када је наш стари пријатељ Сегментатион грешке могу заиста ударац у. Јер смо дали Меморија Назад на Џека. 

Можете остати тамо неспретно за тренутак. Јер ми имамо само пар завршне операције да се размотри. Уклањање врху листе, или бегиннинг-- и овај је мало досадан. Јер ми морамо да знамо да Габе је врста посебно у овом програму. Јер заиста, он има свој показивач. Он не само што је указао на, као што је скоро сви остали овде. 

Дакле, када је шеф листе је уклоњена, чије руке треба сада да промените? Како се оно зовеш? 

Публика: Цхристине. 

Давид Ј. Малан: Ја сам ужасно на имена, очигледно. Тако и Цхристине Габе, чије руке треба да промените када покушате да уклоните Цхристине, број 5, са слике? У реду, хајде да урадимо Габе. Гејб ће до тачке, По свој прилици, на броју 9. Али шта треба да се деси следећег? ПУБЛИКА: Цхристине треба бити нулл [неразумљиво]. Давид Ј. Малан: ОК, вероватно би требало да маке-- Чуо сам "нулл" негде. ПУБЛИКА: Нулл и слободан је. Давид Ј. Малан: НУЛЛ шта? ПУБЛИКА: Нулл и слободан је. Давид Ј. Малан: Нулл и слободан је. Дакле, ово је врло лако. И то је савршено да си сада Сорт од стајао, не припада. Јер си био одвојено са листе. Ви сте били ефективно сироче са листе. Па смо боље да зовемо бесплатно сада Цхристине да дају ту меморију назад. У супротном сваки пут када избрисали чвор са листе можемо правити листу краће, али не и у ствари смањује величине у меморији. Па ако држимо додавање и додавање, додајући ствари на листу, Мој рачунар може добити спорије и спорије и спорије, јер ја понестаје Меморија, чак и ако нисам у ствари користећи Кристинина бајтова меморије више. 

Дакле, на крају постоје и друге сценарија, од цоурсе-- уклањања у средини, уклањање на крају, као што смо видели. Али још интересантније Цхалленге сада ће бити тачно размотри које приказују време. Дакле, не само да можете да задржите комада папира, ако је, Габе, ти не би сметало давање свако стрес лопта. Хвала вам толико на нашу повезане листе Овде волонтера, ако можеш. 

[АППЛАУСЕ] 

Давид Ј. Малан: У реду. Па пар аналитичког Питања Онда, ако сам могао. Видели смо овом запису раније, Биг О и Омега, горње границе и ниже границе на руннинг време неког алгоритма. Дакле, хајде да само размотри пар питања. 

Један, и ми је рекао пре, шта је Трчање време тражења списак у смислу Биг О? Шта је горња граница на трчању време претраживања повезане листе имплементиран од стране наших волонтера овде? То је Биг О Н, линеарна. Јер, у најгорем случају, елемент, као 55, можемо бити у потрази за можда, где Џек је, скроз на крају. И нажалост, за разлику од низа не можемо добити фенси овај пут. Иако сви наши људи били сортиране од малих елемената, 5, све до већег елемент, 55, то је обично добра ствар. Али шта то претпоставку више не дозвољавају нам да радимо? ПУБЛИКА: [неразумљиво] Давид Ј. Малан: Понови? Публика: Рандом приступа. Давид Ј. Малан: Рандом приступа. А за узврат што значи да не може да дуже користе слабу нуле, интуицију, и очигледности бинарним тражи и завади па владај. Јер иако смо људи могао очигледно видим да Енди или хришћанска су отприлике у средини листе, Ми само знамо да је рачунар тако љигави листу од самог почетка. Тако да смо одустали да случајни приступ. 

Толико велика о н сада је горња везан на наше време за претрагу. Шта је са омега нашој потрази? Шта је доња граница за претраживање за неке више у овој листи? ПУБЛИКА: [неразумљиво] Давид Ј. Малан: Понови? Публика: Један. Давид Ј. Малан: Један. Тако Цонстант време. У најбољем случају, Цхристине је заиста на почетку листе. И ми смо у потрази за број 5, па смо нашли је. Тако да није велика ствар. Али она мора бити у почетак листе у овом случају. Шта о нечему као што Делете? Шта ако желите да избришете елемента? Шта је горња граница и доња граница о брисању нешто од повезана список? ПУБЛИКА: [неразумљиво] Давид Ј. Малан: Понови? Публика: н. Давид Ј. Малан: н заиста горњу границу. Јер је у најгорем случају да покушамо за брисање Јацк, као што смо управо урадили. Он је скроз на крају. Води нас заувек, или н кораке да га пронађе. Дакле, то је горња граница. То је линеарна, сигурно. А најбољи случај времена рада, или доњи границе, у најбољем случају би бити константно време. Јер можда ћемо покушати да обришете Кристин, а ми смо само да среће Она је на почетку. Чекај мало. Габе је такође на почетку, а имали смо да ажурирате Габе. Тако да није био само један корак. Тако да је заиста константан време, у најбољем случају, да се уклони најмањи елемент? То је, иако то може бити два, три, или чак 100 линија кода, ако је исти број линије, а не у неком петљи, и независно од величине листе, апсолутно. Брисање елемент у почетак листе, чак и ако морамо да се баве Габе, је и даље Цонстант времена. 

Тако да је ово изгледа као велики корак уназад. А шта је губљење времена Ако је, у недељу једном и недељу нула смо имали не само да Псеудокод код али стварни број да спроведе нешто што дневник н база, или лог, односно, Н, база 2, у смислу његове време рада. Па зашто би дођавола желимо да започнете користите нешто као повезане листе? Да. 

ПУБЛИКА: Дакле, можете да додате елемената у низу. Давид Ј. Малан: Па можеш додати елементе низа. И ово је такође тематски. И ми ћемо наставити да видимо Овај, овај компромис, много као што смо видели траде-офф са стапања врсте. Могли смо да стварно убрзати претрагу или сортирање, боље речено, Ако трошимо мало више простора и имају додатни комад меморије или низ за стапања врсте. Али трошимо више простор, али смо уштедели на времену. У овом случају, ми смо одустајање времена, али смо стицање флексибилност, динамичност ако хоћете, што је вероватно позитивна особина. 

Такође смо троше простор. У ком смислу је повезан список скупље у смислу простору него низа? Где је додатни простор долази? Да? 

ПУБЛИКА: [неразумљиво] Поинтер. 

Давид Ј. Малан: Да, ми смо такође имају показивач. Дакле, ово је минорли нервира у који више не ам Ја само складиштење инт да представља инт. Ја складиштење инт а показивач, што је такође 32 бита. Тако да буквално сам дуплирањем количина простора укључени. Тако да је то компромис, али је То је у случају Инт. Претпоставимо да нисте складиштење ИНТ, али замисли сваки од ових правоугаоника или сваки од ових људи је представљао реч, енглески реч која Можда пет знакова, 10 карактера, можда чак и више. Затим додајући само 32 више бита може бити мање велика ствар. 

Шта ако сваки од ученика у демонстрацијама су буквално Студент Структуре које имају имена и куће, а можда бројеве телефона и Твиттер ручке и слично. Тако да сва поља смо почели говори о другом дану, много мање велика ствар, као Наши чворови добити више интересантно и велики да потрошите, а, додатни показивач само да их повезују. Али заиста, то је компромис. И заиста, код сложенији, као што ћете види по љигави кроз то конкретно пример. Али шта ако је било нека Свети Грал овде. Шта ако не предузмемо корак уназад, али је велики корак напред и спроведу податке структуру преко које смо можете пронаћи елементе као Јацк или Цхристине или било који други елементи у овом низ у истинском константном времену? Тражи је константна. Делете је константна. Убаците је константна. Све ове операције су константни. То би био наш свети грал. А то је место где се ће покупити следећи пут. Видимо се онда.